|
Эта публикация цитируется в 1 научной статье (всего в 1 статье)
Информатика
О числе дополнительных ребер минимального вершинного 1-расширения сверхстройного дерева
М. Б. Абросимов Саратовский государственный университет, кафедра теоретических основ компьютерной безопасности и криптографии
Аннотация:
Граф $G^*$ называется вершинным 1-расширением графа $G$, если граф $G$ можно вложить в каждый граф, получающийся из графа $G^*$ удалением любой его вершины вместе с инцидентными ребрами. Вершинное 1-расширение $G^*$ графа $G$ называется минимальным, если граф $G^*$ имеет на одну вершину больше, чем граф $G$, а среди всех вершинных 1-расширений графа $G$ с тем же числом вершин граф $G^*$ имеет минимальное число ребер. Дерево называется сверхстройным (звездоподобным), если только одна его вершина имеет степень больше двух. В работе дается нижняя и верхняя оценки числа дополнительных ребер минимального вершинного 1-расширения произвольного сверхстройного дерева и указываются семейства деревьев, на которых эти оценки достигаются.
Ключевые слова:
минимальное вершинное расширение, сверхстройное дерево, звездоподобное дерево, отказоустойчивая реализация.
Образец цитирования:
М. Б. Абросимов, “О числе дополнительных ребер минимального вершинного 1-расширения сверхстройного дерева”, Изв. Сарат. ун-та. Нов. сер. Сер.: Математика. Механика. Информатика, 12:2 (2012), 103–113
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/isu303 https://www.mathnet.ru/rus/isu/v12/i2/p103
|
Статистика просмотров: |
Страница аннотации: | 344 | PDF полного текста: | 97 | Список литературы: | 46 | Первая страница: | 1 |
|