Эта публикация цитируется в
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