RUS  ENG
Полная версия
ЖУРНАЛЫ // Известия Саратовского университета. Новая серия. Серия: Математика. Механика. Информатика // Архив

Изв. Сарат. ун-та. Нов. сер. Сер.: Математика. Механика. Информатика, 2012, том 12, выпуск 2, страницы 103–113 (Mi isu303)

Эта публикация цитируется в 1 статье

Информатика

О числе дополнительных ребер минимального вершинного 1-расширения сверхстройного дерева

М. Б. Абросимов

Саратовский государственный университет, кафедра теоретических основ компьютерной безопасности и криптографии

Аннотация: Граф $G^*$ называется вершинным 1-расширением графа $G$, если граф $G$ можно вложить в каждый граф, получающийся из графа $G^*$ удалением любой его вершины вместе с инцидентными ребрами. Вершинное 1-расширение $G^*$ графа $G$ называется минимальным, если граф $G^*$ имеет на одну вершину больше, чем граф $G$, а среди всех вершинных 1-расширений графа $G$ с тем же числом вершин граф $G^*$ имеет минимальное число ребер. Дерево называется сверхстройным (звездоподобным), если только одна его вершина имеет степень больше двух. В работе дается нижняя и верхняя оценки числа дополнительных ребер минимального вершинного 1-расширения произвольного сверхстройного дерева и указываются семейства деревьев, на которых эти оценки достигаются.

Ключевые слова: минимальное вершинное расширение, сверхстройное дерево, звездоподобное дерево, отказоустойчивая реализация.

УДК: 519.17

DOI: 10.18500/1816-9791-2012-12-2-103-113



Реферативные базы данных:


© МИАН, 2024