On a counterexample to a minimal vertex -extension of starlike trees.pdf Связный граф без циклов называется деревом. Дерево называется сверхстройным(звездообразным), если в точности одна его вершина имеет степень больше 2. Эту вер-шину будем называть корнем сверхстройного дерева. Вектор степеней сверхстройногодерева может быть записан в виде (k, 2m, 1k).Сверхстройное дерево можно рассматривать как объединение k цепей с общей кон-цевой вершиной. При этом дерево можно закодировать вектором, состоящим из длинцепей в порядке невозрастания: ( m i , . . . , m^), где mi ^ . . . ^ m^. Очевидно, что такоекодирование сверхстройных деревьев при k > 2 является взаимно однозначным.Граф G* = (V*,а*) называется минимальным вершинным 1-расширением n-вер-шинного графа G = (V, а), если выполняются следующие условия:1) граф G* является вершинным 1-расширением графа G, то есть граф G вкла-дывается в каждый подграф графа G*, получающийся удалением любой еговершины;2) граф G* содержит n + 1 вершин, то есть |V*| = |V| + 1;3) а* имеет минимальную мощность при выполнении условий 1 и 2.В работе [1] доказано следующее утверждение.Теорема 1. Пусть T - сверхстройное дерево вида (m1 , . . . , mk) и k > 2. Дерево Tтогда и только тогда имеет минимальное вершинное 1-расширение с k + 1 дополни-тельным ребром и вектором степеней ((k + 1)2, 2m+fc), когда выполняется условие(Vi = 1 , . . . , k : mi > 1) (Vj = 2 , . . . , mi) (3 1 ^ l ^ k) (m^ = j - 1 V m^ = mi - j ) .Схема построения минимального вершинного 1-расширения сверхстройного деревапо теореме 1 состоит в добавлении одной вершины, соединением её со всеми листьями икорнем. В работе [2] высказано более сильное утверждение по сравнению с теоремой 1.Прежде чем его сформулировать, дадим одно определение. Вершина vi j сверхстрой-ного дерева T называется сложной, если среди длин цепей дерева T нет цепи длиныj - 1 или mi - j. В теореме 1 рассматриваются сверхстройные деревья без сложныхвершин. Например, сверхстройное дерево (5, 1, 1) имеет одну сложную вершину.Утверждение 1 [2]. Минимальное вершинное 1-расширение сверхстройного де-рева с k цепями и p сложными вершинами содержит в точности k + p + 1 дополнитель-ных ребер.При p = 0 приведенное утверждение совпадает с теоремой 1. Однако при p > 0 схе-ма доказательства в работе [2] исследует вариацию вершинного 1-расширения с векто-ром степеней ((k + 1)2, 2m+fc) из теоремы 1. Пусть vi j - сложная вершина, тогда пред-лагается добавить ребро из вершины старшей степени в вершину vi(j - 1). Далее ав-торы статьи утверждают, что построенный граф является минимальным вершинным1-расширением заданного сверхстройного дерева. Однако в общем случае построенныйграф является вершинным 1-расширением, но не обязательно минимальным.Из 67 сверхстройных деревьев с числом вершин до 10 есть деревья, которые не по-падают под действие теоремы 1, но имеют k+1 дополнительное ребро [3]. Оказывается,что все они являются контрпримерами к утверждению 1.Сверхстройное дерево (5, 1, 1) имеет одну сложную вершину, но имеет единственноеминимальное вершинное 1-расширение вида (k2, 32, 2m+k - 2 ) c четырьмя дополнитель-ными рёбрами.Сверхстройное дерево (3, 2, 2) также имеет одну сложную вершину, но име-ет два минимальных вершинных 1-расширения вида (k2, 3 2,2m+k - 2 ) и одно вида((k + 1), k, 3, 2m+k - 1 ) с четырьмя дополнительными рёбрами.Наконец, сверхстройное дерево (4, 3, 2) имеет одну сложную вершину, но имеет4 минимальных вершинных 1-расширения вида (k2, 32, 2m+k - 2 ) с четырьмя дополни-тельными рёбрами.Ещё один интересный пример представляет собой сверхстройное дерево (5, 2, 2).Можно заметить, что оно имеет две сложные вершины, но его 37 минимальных вер-шинных 1-расширений имеют 5, а не 6 дополнительных ребер. Аналогичная ситуацияс деревьями (6, 1, 1) и (3, 3, 2), у которых также по две сложные вершины, но мини-мальные вершинные 1-расширения имеют 5 дополнительных рёбер.Самое большое отклонение среди всех сверхстройных деревьев с числом вершин до10 наблюдается на сверхстройном дереве (7, 1, 1). Непосредственной проверкой можноубедиться, что оно имеет три сложные вершины, но его 8 минимальных вершинных1-расширений имеют 5, а не 7 дополнительных рёбер. Можно предположить, что насверхстройных деревьях вида (t, 1, 1) (количество сложных вершин в таких деревьяхсоставляет t - 3 при t > 3) при увеличении t отклонение будет возрастать.Каждый из этих контрпримеров показывает ошибочность утверждения 1 в общемслучае.

Скачать электронную версию публикации