Исследование количества максимальных и наибольших независимых множеств в некоторых классах деревьев тема диссертации и автореферата по ВАК РФ 01.01.09, кандидат наук Талецкий Дмитрий Сергеевич

• Талецкий Дмитрий Сергеевич
• кандидат наук
• 2019

Оглавление диссертации кандидат наук Талецкий Дмитрий Сергеевич

1.3.3 Случай (=

1.4 Структура (хг, 4, п) —максимальных 2-гусениц

2 Деревья без листьев-дубликатов с минимальным количеством максимальных независимых множеств

2.1 Предварительные результаты

2.1.1 Преобразования деревьев и их свойства

2.1.2 Дополнительные определения и обозначения

2.2 Структура минимальных деревьев

2.2.1 Некоторые ограничения на крайние подграфы

2.2.2 Некоторые ограничения на крайние вершины

2.2.3 Отделимость минимальных деревьев

2.3 Класс минимальных деревьев

2.3.1 Вполне разделимые деревья и их свойства

2.3.2 Описание минимальных деревьев

3 О количестве максимальных независимых множеств в полных д—арных деревьях

3.1 Асимптотика количества м.н.м. в полных д-арных деревьях

3.1.1 Вывод рекуррентного соотношения для количества м.н.м. в полных д—арных деревьях

3.1.2 Частичное решение полученного рекуррентного уравнения

3.2 Случай д =

3.3 Случай больших д

3.3.1 Разрешимость одной системы нелинейных уравнений

3.3.2 Случай больших д

3.4 Численно-аналитическое исследование решения рекуррентного уравнения при малых д

3.4.1 Расходимость последовательности а(д,п) при д ^

3.4.2 Численно-аналитическое обоснование отсутствия при малых д периодических точек периода

3.5 Вычислительные эксперименты

3.5.1 Эксперимент

3.5.2 Эксперимент

Заключение

Литература

Введение

1. Актуальность, степень разработанности темы исследований и формулировки основных результатов диссертации

Химические соединения часто рассматриваются в форме так называемых молекулярных графов, где атомам соответствуют вершины графа, а связям между ними — ребра графа. При этом рассматриваемые свойства химических соединений описываются в терминах инвариантов их молекулярных графов, такие свойства называются топологическими индексами. Иными словами, топологические индексы — некоторые инварианты графов относительно переобозначения вершин и они позволяют аналитически исследовать некоторые аспекты химической структуры вещества. Например, значение винеровского индекса, который определяется как сумма длин кратчайших путей между всеми парами вершин заданного графа, задает точки кипения алканов [49]. В работе Хосойи [24] был представлен другой топологический индекс — количество всех паросочетаний заданного графа, который сейчас известен как ^-индекс или индекс Хосойи. В той же работе было показано, что значение этого индекса коррелирует с точками кипения и другими свойствами алка-нов. Третий пример — индекс Меррифилда и Симмонса [39], определяемый как количество независимых множеств графа, значения которого влияют на некоторые свойства углеводородов.

Поскольку топологические индексы определяют «энергию» химических соединений, то интересна задача по выявлению графов из заданных классов с экстремальным (минимальным или максимальным) значением того или иного топологического индекса. Существует множество такого рода и близких к ним результатов. Например, известно, что для многих классов одни и те же графы максимизируют значение индекса Меррифилда-Симмонса и минимизируют значение индекса Хосойи, и наоборот. В 2009 году была доказана известная гипотеза о том, что для любого натурального числа (за исключе-

нием заданных 49 чисел) существует дерево, винеровский индекс которого равен этому числу [46]. Графы с экстремальным значением топологических индексов могут быть полезны, например, при разработке новых лекарств.

В данной диссертационной работе рассматриваются обобщения индекса Меррифилда-Симмонса (количества независимых множеств графа) — количества максимальных и наибольших независимых множеств в графах. Далее в тексте используются сокращения «н.м.», «м.н.м.» и «н.н.м.» для терминов «независимое множество», «максимальное независимое множество» и «наибольшее независимое множество», соответственно.

На сегодняшний день получено множество результатов, посвященных перечислению всех н.м. в различных классах графов. Для многих классов известны точные нижние и верхние оценки количества всех н.м., которое может содержать граф из этого класса. Для класса всех п-вершинных графов и всех п-вершинных деревьев эти оценки тривиальны. Известны достижимые верхние оценки количества всех н.м. для класса деревьев фиксированного диаметра [43] и для класса к-регулярных графов [54].

Перечислению м.н.м. в различных типах графов также посвящена обширная литература, в последние годы появляется большое количество работ по данной теме, в которых рассматриваются всё новые классы графов. Ниже приведены некоторые наиболее интересные результаты в данной области.

В 1965 году Мун и Мозер в известной статье [41] отыскали максимальное количество м.н.м. в классе всех п-вершинных графов (этот результат был также независимо получен Миллером и Мюллером [40]). Кроме того, ими были найдены все соответствующие экстремальные графы. Несколько лет назад стали известны значительно более простые доказательства этого результата. Одно из них содержится в работе [52].

В 1984 году Коэн [15] привел некоторые оценки количества м.н.м. в деревьях. Два года спустя достижимая верхняя оценка количества м.н.м. в п-вершинных деревьях была доказана Вильфом [50]. Предложенное им доказательство носило алгебраический характер и было достаточно слож-

ным для понимания. Еще через два года Саган предложил более простое теоретико-графовое доказательство [45], а также описал все соответствующие экстремальные деревья.

Достижимая верхняя оценка количества м.н.м. в связных графах была найдена Фюреди в 1987 году [21] для графов, содержащих 50 и более вершин. Независимо от него год спустя этот же факт в работе [22] доказали Григгс, Гринстед и Гишар и описали все соответствующие экстремальные графы. В 1993 году Лю получил достижимую верхнюю оценку количества м.н.м. для класса двудольных графов и описал все соответствующие экстремальные графы, которые оказались лесами специального вида [38]. В этом же году Гуйтер и Тужа решили аналогичную задачу для класса п-вершинных графов без треугольников [26].

Имеются работы, посвященные графам, имеющим заданное число циклов. В 1997 году была получена достижимая верхняя оценка для класса уницик-лических графов [30], т.е. графов, имеющих в точности один цикл. В 2006 году решена аналогичная задача для класса п-вершинных графов, содержащих в точности г циклов [53], причем параметр г может принимать любое натуральное значение от 1 до |_п/3_|.

В последнее время появляются работы, посвященные вычислению второго и третьего по величине максимального количества м.н.м. в графах заданного класса. Обычно в таких работах также перечисляются все экстремальные графы, на которых полученная оценка достигается. В 2008 году Джин и Ли нашли второе максимальное значение количества м.н.м. в классе всех п-вершинных графов [27]. В 2009 году были найдены второе [33] и третье [28] максимальные значения для класса деревьев. В 2012 году было найдено второе максимальное значение для класса связных графов с не более, чем одним циклом [29], а в 2013 году было найдено второе максимальное значение для класса двудольных графов хотя бы с одним циклом [37].

Работы, посвященные перечислению н.н.м. в графах, встречаются значительно реже. Связано это с тем, что для многих классов графов (например,

всех п-вершинных графов, связных графов, графов без треугольников) верхняя оценка числа н.н.м. совпадает с верхней оценкой числа м.н.м., а для некоторых других классов (в основном, заданных параметрически) эта оценка является тривиальной (например, в классе плоских прямоугольных решеток каждый граф содержит не более 2 различных н.н.м.). В работе Зито [55] была найдена достижимая верхняя оценка числа н.н.м. в деревьях и описаны все соответствующие экстремальные деревья. Обзор [31] содержит несколько других результатов подобного рода, в частности, приведена достижимая верхняя оценка числа н.н.м. в классе всех лесов и описаны все соответствующие экстремальные графы.

Верхняя оценка количества всех н.м. в классе деревьев тривиальна, поскольку она достигается на графе-звезде [44]. В 2007 году для любого к ^ 3 для подкласса деревьев со степенями всех вершин не более чем к были описаны все соответствующие экстремальные деревья, но при этом из-за сложной структуры таких деревьев значения количества н.м. на них найдены не были. В первой главе диссертации данный результат обобщается на случай н.н.м. Также там описаны все 2-гусеницы со степенями всех вершин не более чем четыре, имеющие максимальное количество н.н.м.

Достижимые нижние оценки количества н.м. и м.н.м. в различных классах графов изучены гораздо хуже, поскольку во многих случаях они являются тривиальными и соответствующие экстремальные графы устроены очень просто. Так, нижняя оценка количества н.м. в классе всех деревьев явлет-ся тривиальной и достигается на простом пути. А. Б. Дайняк в работе [16] описал все деревья фиксированного диаметра, имеющие минимальное количество м.н.м. Такие деревья представляют собой простые пути, к одному из концов которых присоединено некоторое количество листовых вершин, и они содержат листья-дубликаты. В связи с этим интересно рассмотреть класс деревьев, не содержащих листьев-дубликатов, и вычислить для него нижнюю оценку числа максимальных независимых множеств. Во второй главе диссертации эта задача была решена и все соответствующие экстремальные деревья

«распадаются» на поддеревья одного из четырех типов и количество м.н.м. всего дерева равняется произведению количеств м.н.м. таких поддеревьев.

На сегодняшний день известно большое количество работ, посвященных перечислению н.м. в графах, заданных параметрически. Одним из наиболее интересных таких классов графов является класс прямоугольных решеток. В 1988 году К. Вебер доказал существование конечного предела корня тп-ой степени из количества всех н.м. плоской прямоугольной решетки размера тхп, значение которого обычно обозначается символом п. Известно, что константа 1п(п) находит применение в статистической физике [13]. Существует несколько работ, посвященных приближенной оценке величины п, например, статья К. Энгеля [18] и статья Н. Калкина и Г. Вильфа [34]. Позднее, в 2016 году в работе [42] был предложено значительно более простое доказательство существования двойного предела. В 2017 году Д. С. Талецкий доказал существование двойного предела корня тп-ой степени из количества максимальных независимых множеств в прямоугольных, цилиндрических и тороидальных решетках размера т х п. Выяснилось, что эти пределы равны одной и той же константе к, которая также известна в статистической физике [48]. При этом вид асимптотики для случая максимальных н.м. никак принципиально не отличался от вида асимптотики в случае всех н.м. плоской прямоугольной решетки. Как оказалось, это верно далеко не для всех параметрически заданных классов графов.

В 1983 году группой австрийских математиков в работе [35] была найдена асимптотика количества всех н.м. в полных д-арных деревьях. Выяснилось, что вид асимптотики при д € {2,3,4} отличается от вида асимптотики при д ^ 5, в этом случае он зависит от четности высоты дерева. В третьей главе диссертации показано, что в случае м.н.м. ситуация принципильно другая. А именно, при д = 2 вид асимптотики такой же, как и в случае всех н.м. при малых д, а при всех достаточно больших значениях д (по-видимому, при д > 10) вид асимптотики зависит от остатка при делении на 3 высоты дерева. Кроме того, численно-аналитически было показано, что при 3 ^ д ^ 10 вид

асимптотики отличается от всех описанных выше случаев.

2. Цели и задачи работы

Целью диссертационного исследования является решение нескольких задач экстремальной и перечислительной комбинаторики, связанных с максимальными и наибольшими независимыми множествами в некоторых классах деревьев.

Задачи диссертационного исследования состоят в следующем:

1. Описать все деревья с экстремальным количеством наибольших (максимальных) независимых множеств среди деревьев с заданными ограничениями.

2. Исследовать количество максимальных независимых множеств в полных д-арных деревьях при стремлении высоты деревьев к бесконечности.

Введение диссертации (часть автореферата) на тему «Исследование количества максимальных и наибольших независимых множеств в некоторых классах деревьев»

3. Научная новизна работы

В диссертационной работе при помощи известных и оригинальных (таких, как новые преобразования и разложения деревьев) приемов решается несколько ранее открытых задач экстремальной и перечислительной комбинаторики независимых множеств в деревьях. Все основные результаты диссертации являются новыми.

4. Теоретическая и практическая значимость работы

Работа носит теоретический характер. Результаты диссертации могут найти применение в исследованиях по теории графов и комбинаторике. Они также могут использоваться при разработке спецкурсов по дискретной математике.

5. Методология и методы диссертационного исследования

В диссертации использованы методы теории графов, комбинаторики, математического и численного анализа.

6. Положения, выносимые на защиту и личный вклад соискателя

На защиту выносятся следующие результаты диссертации:

1. Для любых п и ( выявлены все деревья с максимальным количеством наибольших независимых множеств среди п-вершинных деревьев со степеня-

ми всех вершин не более чем

2. Для любого п полностью описаны все деревья с наименьшим количеством максимальных независимых множеств среди п-вершинных деревьев без листьев-дубликатов.

3. Получен вид асимптотики количества максимальных независимых множеств в полных д-арных деревьях при стремлении их высоты к бесконечности.

Все основные результаты диссертации получены лично соискателем. Научному руководителю принадлежит общее руководство при подготовке диссертации и предложения по редактуре текста.

7. Объем и структура работы

Диссертация состоит из введения, трех глав, заключения и списка литературы, включающего 55 наименований. Общий объем диссертации составляет 100 страниц и включает 20 рисунков. Нумерация всех теорем и лемм ведется независимо внутри каждой главы, причем номер каждого такого утверждения состоит из трех частей, первая из которых соответствует номеру главы, вторая номеру раздела, а третья порядковому номеру внутри раздела. Точно так же нумеруются рисунки. Нумерация теорем, лемм, следствий ведется независимо.

Во введении обосновывается актуальность диссертационной работы, представлены обзор литературы по теме исследований, цели и задачи работы, научная новизна диссертации, теоретическая и практическая значимость работы, методы диссертационного исследования, основные результаты диссертации, структура работы, а также представлены степень достоверности результатов работ, апробации результатов работ и публикации по теме диссертации.

Первая глава посвящена выявлению для любых п и ё, всех п-вершинных деревьев со степенями всех вершин не более чем имеющих максимально возможное количество наибольших независимых множеств среди всех таких деревьев. Показывается, что при всех четных п экстремальное дерево един-

ственно, а при нечетных n единственность может и не иметь места, причем для d = 3 и любого нечетного n ^ 7 имеется в точности [n-3] + 1 экстремальных деревьев. Кроме того, для любых n и d £ {3,4} выявляются все 2-гусеницы с максимальной степенью вершин d, имеющие максимально возможное количество наибольших независимых множеств среди всех такого рода деревьев.

Во второй главе для любого n описываются все деревья с n вершинами без листьев-дубликатов, имеющие минимально возможное количество максимальных независимых множеств среди такого рода деревьев.

В третьей главе исследуется асимптотика количества максимальных независимых множеств в полных q-арных деревьях в зависимости от значения параметра q. Получен вид этой асимптотики при q = 2 и всех достаточно больших q. Там же численно-аналитическим образом установливается область справедливости этого утверждения (в терминах q) и приближенно вычисляются некоторые параметры асимптотик.

В заключении подводится итог к проделанной работе и обсуждаются перспективы дальнейшего развития тематики диссертационного исследования.

8. Достоверность результатов и апробация работы

Все результаты, выносимые на защиту, являются новыми и достоверными. Это подтверждается наличием строгих математических доказательств, опубликованных в изданиях из перечня Министерства науки и высшего образования РФ рецензируемых научных изданий, в которых должны быть опубликованы основные научные результаты на соискание ученой степени кандидата наук. Результаты диссертационного исследования прошли апробацию на следующих конференциях и семинарах:

1. The 7th International Conference on Network Analysis (Нижний Новгород, 2017).

2. Финал второго конкурса студенческих работ по теоретической информатике и дискретной математике имени Алана Тьюринга (Санкт-Петербург,

2017).

3. Workshop on graphs, networks, and their applications (Москва, 2018, 2019).

4. X международная конференция «Дискретные модели в теории управляющих систем» (Красновидово, 2018).

5. XXV и XXVI международные конференции студентов, аспирантов и молодых ученых «Ломоносов» (Москва, 2018, 2019).

6. Семинар международной лаборатории теоретической информатики НИУ ВШЭ.

7. Семинар кафедры теоретических основ компьютерной безопасности и криптографии Саратовского государственного университета имени Н.Г. Чернышевского.

8. Общегородские семинары г. Н. Новгорода по дискретной математике.

9. Семинары лаборатории алгоритмов и технологий анализа сетевых структур НИУ ВШЭ НН.

По теме диссертации имеется 4 следующие публикации в изданиях из перечня Министерства науки и высшего образования РФ рецензируемых научных изданий, в которых должны быть опубликованы основные научные результаты на соискание ученой степени кандидата наук:

1. Талецкий Д. С., Малышев Д. С. О количестве максимальных независимых множеств в полных q-арных деревьях // Дискретная математика. — 2016. — Т. 28, No 4. — С. 139-149.

2. Талецкий Д. С., Малышев Д. С. О деревьях ограниченной степени с максимальным количеством наибольших независимых множеств // Дискретный анализ и исследование операций. — 2018. — Т. 25, No 2. — С. 101-123.

3. Талецкий Д. С. О свойствах решения рекуррентного уравнения, перечисляющего максимальные независимые множества в полных деревьях // Журнал Средневолжского математического общества — 2018. — Т. 20, N0 1. - С. 46-54.

4. Талецкий Д. С., Малышев Д. С. Деревья без листьев-дубликатов с наименьшим количеством максимальных независимых множеств // Дискретная математика. — 2018. — Т. 30, N0 4. — С. 115-133.

Автор работы выражает глубокую признательность своему научному руководителю д.ф.-м.н., доц. Дмитрию Сергеевичу Малышеву за постоянное внимание к работе, полезные советы и замечания.

Терминология и основные обозначения

Графы

В настоящей диссертации рассматриваются обыкновенные непомеченные неориентированные графы без петель и кратных ребер. Через V(С) обозначается множество вершин графа С, а через Е(С) его множество ребер. Размер графа — количество его вершин.

Также используются следующие обозначения для некоторых стандартных графов:

• Через Рп обозначается п-путь, т.е. путь, содержащий п вершин

• Через Кр,д обозначается полный двудольный граф с размерами долей р и д, соответственно

• С\ и С2 — дизъюнктное объединение графов С\ и С2 с непересекающимися множествами вершин

• кС — дизъюнктное объединение к экземпляров графа С

Для подмножества V' С V(С) через С\V' обозначается результат удаления вершин подмножества V' из графа С.

Через deg(ж) обозначается степень вершины х.

Деревья

Деревом называется связный граф без циклов. Четное (соответственно, нечетное) дерево — дерево, имеющее четное (соответственно, нечетное) количество вершин. Вершина степени один дерева называется листом. Вершина, смежная с листом леса, называется предлистовой или предлистом. Деревом максимальной степени й называется дерево, степень каждой вершины которого не превосходит й. Два листа называются листьями-дубликатами, если

они имеют общего соседа. Вершина дерева смежна с поддеревом, если она имеет соседа в этом поддереве.

Дерево называется к-гусеницей, если все его вершины расположены на расстоянии не более чем к от некоторого его простого пути. Этот путь называется хребтом к-гусеницы. Будем говорить, что вершина к-гусеницы находится на в-ом ярусе, если расстояние от нее до хребта к-гусеницы равно в.

Полным д-арным деревом высоты п называется корневое дерево, все листья которого находятся на расстоянии п от корня, степень корня равна д, а степень остальных нелистовых вершин равна д + 1. Обозначим такое дерево через Т?;П. Будем говорить, что вершина дерева Тд,п находится на к-том ярусе, если расстояние от нее до корня равно к.

Независимые множества

Независимым множеством графа называется произвольное подмножество попарно несмежных его вершин. Независимое множество графа называется максимальным, если оно максимально по включению, и наибольшим, если оно максимально по мощности. Мощность наибольшего независимого множества графа С обозначается через а (С) и называется числом независимости графа С. Количество всех, максимальных и наибольших независимых множеств графа С обозначается через ¿(С), тг(С) и жг(С), соответственно. Кроме того, используются сокращения «н.м.», «м.н.м.» и «н.н.м.» для терминов «независимое множество», «максимальное независимое множество» и «наибольшее независимое множество», соответственно.

Через г+(С,^) (соответственно, через г-(С,^)) обозначим количество н.м. графа С, содержащих (соответственно, не содержащих) некоторую его вершину V. Аналогично определим величины (С,^) и тг-(С,^) для случая м.н.м., а также величины жг+(С,^) и жг-(С,^) для случая н.н.м. Легко видеть, что для любого графа С и любой его вершины V верны соотношения г+(С^) + г_(С^) = ¿(С), тг+(С^) + тг_(С^) = тг(С) и (С^) + жг_(С^) = жг(С). Через тг+(д,п) (соответственно, че-

рез тг_(д,п)) обозначается количество м.н.м. дерева Т?;П, содержащих (соответственно, не содержащих) его корень.

Через I(С) (соответственно, через XI(С)) обозначается множество всех н.м. (соответственно, множество всех н.н.м.) графа С.

Максимально возможное количество н.м. (соответственно, н.н.м.) в п-вершинных деревьях максимальной степени й обозначается через г^(п) (соответственно, через жг^(п)). Дерево Т с п вершинами максимальной степени й называется (г, й, п)-максимальным (соответственно, (жг, й, п)-максимальным), если г(Т) = г^(п) (соответственно, жг(Т) = жг^(п)). Аналогично, для любого к ^ 1, к-гусеница называется (г, й, п)-максимальной (соответственно, (жг,й,п)-максимальной), если она содержит максимально возможное количество н.м. (соответственно, н.н.м.) среди всех п-вершинных к-гусениц максимальной степени й. Минимальным называется п-вершинное дерево Т без листьев-дубликатов, содержащее наименьшее число м.н.м. среди всех таких деревьев.

Глава 1

Деревья ограниченной степени с максимальным количеством наибольших независимых множеств

В данной главе для любых п и ё выявляются все (жг, ё, п)-максимальные деревья. Показывается, что при всех четных п экстремальное дерево единственно, а при нечетных п единственность может и не иметь места, причем для ё = 3 и любого нечетного п ^ 7 имеется в точности [п__3] + 1 экстремальных деревьев. Кроме того, для любых п и ё £ {3,4} выявляются все (жг, ё, п)-максимальные 2-гусеницы.

Результаты этой главы опубликованы в работе [9].

1.1 Предварительные результаты

1.1.1 Операция расширения

Для графа С через вж^(С) обозначим граф, полученный добавлением листа к каждой вершине графа С. Граф вж^(С) будем называть расширением графа С.

Лемма 1.1.1 Для любого графа С и его расширения вж^(С) имеет место равенство г(С) = жг(вж^(С)).

Доказательство. Очевидно, что жг(вж£(С)) = IV(С)|. Для заданного мно-

• • •

• : • 4=1

Рис. 1.1: Дерево и его расширение

жества I' € I(О) добавим к нему все элементы множества V(втЛ(О)) \ V(О), соседи которых не входят в I'. Ясно, что полученное множество вершин будет н.н.м. графа О. При этом разным элементам множества I(О) соответствуют разные элементы множества XI(втЛ(О)). Обратно, удалив все элементы множества V(вх1(О)) \ V(О) из любого элемента множества XI(вх1(О)), мы получим некоторое н.н.м. графа О. Тем самым, между I(О) и XI(вхЛ(О)) существует биекция. Отсюда следует справедливость данной леммы. ■

1.1.2 Операция разрастания

Напомним, что два листа графа называются листьями-дубликатами, если они имеют общего соседа. Набором листьев-дубликатов графа назовем множество всех его листьев-дубликатов, смежных с некоторой общей вершиной. Отметим, что каждый такой набор содержит не менее двух элементов. Очевидно, что справедливо следующее утверждение.

Лемма 1.1.2 Если в графе О удалить все вершины, кроме одной, из каждого набора листьев-дубликатов, то для полученного графа О' верно неравенство хА(О) ^ тА(О').

Назовем побегом дерева Т его подграф, состоящий из вершины степени два и смежного с ней листа. Будем обозначать побег с листом V и смежной с ним вершиной и через ш. Назовем разрастанием дерева Т дерево Т', полученное присоединением нового побега с(, смежного с вершиной а, где аЬ — побег дерева Т. Дерево, для которого можно построить разрастание (т.е. содержащее хотя бы один побег), будем называть разрастаемым.

Рис. 1.2: Дерево и одно из его разрастаний

Лемма 1.1.3 Для любого разрастания T' дерева Т имеет место неравенство жг(Т^ > жг(Т).

Доказательство. Предположим, что дерево Т/ получается из дерева Т добавлением некоторого побега сё, смежного с вершиной а, где аЬ — побег дерева Т. Ясно, что жг(Т/) = жг+(Т/,с) + жг+(Т/,ё). При этом имеют место равенства

жг+(Т/,ё) = жг(Т), жг+(Т/,с) = жг+(Т,Ь). Поскольку верны соотношения

жг+(Т, а) + жг+(Т, Ь) = жг(Т), жг+(Т, Ь) ^ жг+(Т, а),

то жг+(Т, Ь) ^ 1. Отсюда следует справедливость утверждения данной леммы. ■

Лемма 1.1.4 Каждое (жг, ё, п)-максимальное дерево является разрастае-мым.

Доказательство. Покажем, что если дерево не является разрастаемым, то оно имеет по меньшей мере два набора листьев-дубликатов. Предположим, что (жг, ё, п)-максимальное дерево Т не является разрастаемым и рассмотрим в нем произвольный путь наибольшей длины. Обозначим концы этого пути через щ и и2 (они будут листьями дерева Т), а смежные с ними вершины через V и соответственно. Поскольку дерево Т является (жг, ё, п)-максимальным, то V = -и2. У каждой из вершин г>1,г>2 все соседи, кроме одного, являются листьями. Поскольку дерево Т не является разрастаемым, то ^ 3,ёе^(г»2) ^ 3. Пусть т = ), ёед(г>2)), тогда, удалив по т — 2 листа, смежных с вершинами V и -и2, мы получим разраста-емое дерево Т/, причем жг(Т/) ^ жг(Т) по лемме 1.1.2. Применив последова-

тельно т — 2 раз операцию разрастания к дереву Т', мы получим дерево Т'', причем IV(Т'')| = IV(Т)| и хг(Т'') > хг(Т') ^ хг(Т) (по лемме 1.1.3), что противоречит (хЛ, й, п)-максимальности дерева Т. ■

Лемма 1.1.5 Для любого ( ^ 3 последовательности х%а(2к) и хг^[(2к + 1) строго монотонно возрастают.

Доказательство. Пусть имеется (хЛ, (, п)-максимальное дерево Т, которое по предыдущей лемме является разрастаемым. Через Т' обозначим произвольное разрастание дерева Т. Тогда по лемме 1.1.3 имеет место двойное неравенство

хЛл(и + 2) ^ хг(Т') > хЛ(Т) = хЛл(и).

■

Следствие 1.1.1 В любом (хг,(,п)-максимальном дереве имеется не более одного набора листьев-дубликатов, причем этот набор содержит ровно два элемента.

1.2 Свойства (хг, й, п)-максимальных деревьев

1.2.1 Отсутствие неподвижных вершин

Вершину V дерева Т назовем хл+-неподвижной, если она входит в каждое его н.н.м., то есть, если выполняется равенство хА+(Т^) = хг(Т). Вершину и дерева Т назовем хл—-неподвижной, если она не входит ни в какое его н.н.м., то есть, если выполняется равенство хг—(Т,и) = хг(Т). Очевидно, что все соседи хг+-неподвижной вершины являются хг—-неподвижными. Путь с 2т + 1 вершинами (т ^ 1) в некотором дереве назовем хг-чередующейся цепью, если он начинается и заканчивается в хЛ+-неподвижном листе, причем хг+-неподвижные вершины чередуются в нем с хг—-неподвижными вершинами.

Нетрудно видеть, что в любом дереве листья-дубликаты всегда являются хЛ+-неподвижными вершинами. Если каждая вершина дерева является

либо жг+-неподвижной, либо жг—-неподвижной, то оно содержит единственное н.н.м. Интуитивно ясно, что деревья с максимальным количеством н.н.м. должны содержать как можно меньше таких вершин. А именно, верны следующие утверждения: каждое (жг,ё, 2к)-максимальное дерево не содержит жг+-неподвижных вершин и каждое (жг,ё, 2к + 1)-максимальное дерево содержит ровно две жг+-неподвижные вершины — пару листьев-дубликатов. Доказательство данных предложений будет представлено далее.

Лемма 1.2.1 Всякое нечетное дерево содержит жг+-неподвижный лист.

Доказательство. Индукция по размеру дерева п = 2к + 1. База индукции к = 0 очевидна. Предположим, что утверждение выполняется для любого дерева размера 2к + 1. Рассмотрим произвольное дерево Т размера 2к + 3. Если оно содержит листья-дубликаты, то доказывать нечего. В противном случае в нем существует побег ии, причем вершина и смежна с некоторым поддеревом Т/ размера 2к + 1, которое по предположению индукции содержит жг+-неподвижный лист г. В дереве Т вершина г либо является листом, либо смежна с побегом ии. В обоих случаях эта вершина жг+-неподвижна, так как всякое н.м. дерева Т, не содержащее г, содержит менее а(Т) = а(Т/) + 1 вершин и не является наибольшим. Если г является листом дерева Т, то в нем есть жг+-неподвижный лист. Если же г смежна с и, то вершина V будет жг+-неподвижным листом. ■

Лемма 1.2.2 В любом дереве с жг+-неподвижной вершиной существует жг-чередующаяся цепь, содержащая эту вершину.

Доказательство. Предположим, что в некотором дереве Т существует жг+-неподвижная вершина V. Рассмотрим множество ее соседей {и1, и2,..., ик}, которые, очевидно, являются жг—-неподвижными вершинами и покажем, что каждая из них смежна еще хотя бы с одной жг+-неподвижной вершиной. Предположим, что все соседи вершины и1, кроме V, не являются жг+-неподвижными. Поскольку Т является деревом,

то существует I £ XI(Т), содержащее ровно одного соседа вершины и1 — вершину V. Рассмотрим множество (I \ {V}) и {и1} и снова получим н.н.м. дерева Т. Значит, существует жг+-неподвижная вершина V!, отличная от V и смежная с и1.

Если вершина v1 не является листом, то рассмотрим ее соседа v/, отличного от и1 и, рассуждая аналогично, покажем, что эта вершина смежна с жг+-неподвижной вершиной v2, отличной от v1. Продолжая эти рассуждения, мы рано или поздно покажем существование жг+-неподвижного листа. Если исходная вершина V также является листом, то утверждение леммы доказано. Если же нет, то рассмотрев еще одного ее соседа и2 и проведя аналогичные

рассуждения, мы покажем существование второго жг+-неподвижного листа. ■

Лемма 1.2.3 Если в некотором (жг, ё, п)-максимальном дереве Т существует жг-чередующаяся цепь длины два, то в нем не существует жг+-неподвижных вершин за пределами этой цепи.

Доказательство. Предположим, что имеется жг-чередующаяся цепь Р = (г1, г2, г3) и что существует жг+-неподвижная вершина и за пределами этой цепи. Тогда по предыдущей лемме существует жг-чередующаяся цепь, проходящая через вершину и, а значит, существует жг+-неподвижный лист и за пределами цепи Р. Удалим из дерева Т лист и и обозначим полученное дерево через Т1. Покажем, что имеет место равенство а(Т1) = а(Т) — 1. Очевидно, что имеет место неравенство а(Т[) ^ а(Т) — 1. С другой стороны, равенство а(Т[) = а(Т) невозможно, поскольку в этом случае любое н.н.м. дерева Т1 являлось бы н.н.м. дерева Т, что противоречит жг+—неподвижности листа и дерева Т.

Из равенства а(Т1) = а(Т) — 1 и жг+—неподвижности листа и дерева Т следует, что каждое н.н.м. J дерева Т можно представить в виде объединения ^ и {и}, где н.м. ^ содержит а(Т) — 1 вершин и является наибольшим для дерева Т1. Пусть отображение ^ : XI(Т) —> XI(Т1) переводит каждое н.н.м.

31 и {и} в н.н.м. 3\. Очевидно, что Г инъективно, а значит, хг(Т1) ^ хг(Т).

В дереве Т1 существует набор из листьев-дубликатов г1 и г3. Удалим лист из дерева Т1 и обозначим получившееся дерево через Т2. По лемме 1.1.2 имеет место неравенство хг(Т2) ^ хг(Т1), следовательно, имеет место неравенство хг(Т2) ^ хг(Т). Поскольку дерево Т2 содержит на 2 вершины меньше, чем дерево Т, то по лемме 1.1.5 дерево Т не может быть (хЛ, й, п)-максимальным. Получаем противоречие с предположением. ■

Лемма 1.2.4 Каждое (хг,(,п)-максимальное дерево не содержит хг-чередующихся цепей длины четыре и более.

Доказательство. Пусть Т0 — (хЛ, (, п)-максимальное дерево, в котором имеется хг-чередующаяся цепь Р, которая имеет максимальную длину среди длин всех хг-чередующихся цепей (хг, (, п)-максимальных деревьев. Предположим, что длина Р не менее чем четыре. Покажем, что существует п-вершинное дерево Т такое, что хг(То) = хг(Т), в котором есть хг-чередующаяся цепь (г\, г2,..., г2к+\) длины такой же, что и длина Р, причем (ед(х3) = 2 и (ед(х5) ^ 2. Обозначим Р через ... ^2з+1), где 2в + 1 ^ 5.

Случай (ед^ 3. Рассмотрим некоторую вершину и, смежную с v3 и не принадлежащую Р. Эта вершина является хг—-неподвижной, поэтому она не может быть листом. Из рассуждений леммы 1.2.2 следует, что вершина и смежна по крайней мере с одной хг+-неподвижной вершиной и, отличной от v3. Если вершина и не является листом, то она по лемме 1.2.2 лежит на хг-чередующейся цепи, собственным фрагментом которой является подцепь (и,и^3,... ^2к+\), что невозможно, так как цепь Р имеет наибольшую длину в дереве Т0. Значит, вершина и является листом. Добавим в дерево Т0 ребро VlU и удалим ребро v3u, обозначим полученное дерево через Т1. Нетрудно видеть, что а(Т1) = а(Т0). В Т0 имеется цепь Р' = ... ^2к+1), причем (ед^1) = 2. Поскольку Р яв-

ляется хг-чередующейся, то Р' тоже является хг-чередующейся.

Если в Т1 имеем ёед^3) = 2, то доказывать нечего. Если же ёе^^з) ^ 3, то рассмотрим еще одну жг—-неподвижную вершину и/, смежную с v3 и не лежащую на Р/, которая смежна с некоторым жг+-неподвижным листом и/, отличным от v3. Удалим из дерева Т1 ребро u/v3 и добавим ребро и/и. В полученном дереве Т имеется жг-чередующаяся цепь Р// = (и/, и/, и, и, v1, v2, v3,..., v2k+1), где ёед(и) = ёед^) = 2, при этом жг(Т) = жг(Т0).

Случай = 2. Считаем, что ёед(v5) ^ 3, иначе доказывать нече-

го. В этом случае рассмотрим некоторую вершину и/, смежную с v5 и не принадлежащую Р. Из рассуждений выше следует, что вершина и/ лежит на некоторой жг-чередующейся цепи, при этом эта цепь содержит либо две, либо четыре вершины, не лежащие на цепи Р. В первом варианте обозначим жг+-неподвижный лист, смежный с вершиной и/, через и/, после чего удалим ребро Щу5 и добавим ребро u/v1. В полученном дереве Т положим = и/, г2 = и/, гк = при 3 ^ к ^ 2й + 1, тогда ёед(г3) = ёед(г5) = 2, что и требовалось доказать. Осталось рассмотреть вариант, когда в дереве Т0 существует некоторая жг-чередующаяся цепь , v3, V4, v5, а, Ь, с, ё), где вершина а не принадлежит Р и вершина ё является жг+-неподвижным листом. По предыдущей лемме вершина ё не имеет дубликата в Т0. Удалим ребро Ьс и добавим ребро с^, в полученном дереве Т положим = ё, г2 = с, = Vk_2 при 3 ^ к ^ 2й + 1, тогда ёед(г3) = ёед(г5) = 2. Нетрудно видеть, что жг(Т) = жг(Т0).

Таким образом, мы получили (жг, ё, п)-максимальное дерево Т, в котором существует жг-чередующаяся цепь (г1,г2,... ,г2к+1) длины не менее чем четыре, причем ёед(г3) = 2 и ёед(г5) ^ 2. Обозначим через С смежное с г5 максимальное по включению поддерево дерева Т, не содержащее вершины г4 (в случае 2к + 1 = 5 это дерево является пустым). Вершины г2 и г4 смежны не более чем с ё — 2 максимальными по включению поддеревьями, не содержащими вершин каждое, которые мы будем обозначать через А и Bj соответственно (см. рисунок 1.3). Напомним, что г2 является жг—-неподвижной, а г3 является жг+-неподвижной. Поэтому по лемме 1.2.3 вершина г2 не имеет

хг+-неподвижного листового соседа, отличного от z1. Отсюда и ввиду максимальности цепи Р по длине следует, что каждый из соседей вершины z2, кроме г1 и z3, не является хг+-неподвижной вершиной.

Отсоединим все деревья А от г2 и все деревья Б^ от г4, соединим ребрами корни всех деревьев А с и корни всех деревьев Бj с z2. Мы получим некоторое дерево Т* со степенями всех вершин не более чем (. Очевидно, что а(Т*) = а(Т), это следует из того факта, что любой лист любого дерева входит в некоторое его н.н.м. Понятно, что каждое н.н.м. дерева Т будет и н.н.м. дерева Т*. Поэтому и Т* является (хг, (, п)-максимальным, причем и в Т* цепь (г1, г2,..., z2k+1) является хг-чередующейся. По аналогии с рассуждениями предыдущего абзаца можно показать, что в дереве Т* корни всех деревьев Бj не будут являться хг+-неподвижными. Это так, очевидно, и для дерева Т.

Удалим из Т ребро z4z5 и добавим ребро ZзZ5. Присоединим все поддеревья А{ к вершине z1. Присоединим все поддеревья Бj к вершине z3. Если при этом степень z3 превысит (, то присоединим одно из поддеревьев к вершине z1.

Рис. 1.3: Пример преобразования в случае d =5

Нетрудно видеть, что в полученном дереве Т' степени всех вершин не превосходят (. Напомним, что вершины z1,z3,z5 в дереве Т являются хг+-неподвижными. Поэтому любое его н.н.м. I можно представить в виде I = ^1, Zз, Z5} и 1а и 1в и 1с, где

1с ± I П (V(С) \ Ы),1а = I П У V(Аг),1в ± I П У V(Бj).

Через T" обозначим поддерево дерева T', порожденное вершинами Ясно, что а(Т") = 3 и что каждое его н.н.м. содержит вершину z5. Ясно, что

|{Z2,Z4,Z5}| + IIa| + IIB| + |1c| ^ a(T') ^ a(T") + |1A| + |IB| + |IC|.

Поэтому a(T/) = a(T). Пусть отображение F : XI(T) —у XI(T/) переводит н.н.м. {z1, z3, z5} U IA U Ib U Ic дерева T в н.н.м. {z2, z4, z5} U IA U IB U IC дерева T/. При этом существует хотя бы одно н.н.м. дерева T/, содержащее вершины z1, z4, z5, поскольку корни всех поддеревьев A и Bj дерева T не являются жг+-неподвижными. Поэтому xi(T/) > xi(T). Получаем противоречие с предположением. ■

Из лемм 1.2.2 и 1.2.4 следует, что произвольный жг+-неподвижный лист любого (xi, d, п)-максимального дерева принадлежит xi-чередующейся цепи длины два. Значит, другой конец цепи и будет дубликатом этого листа.

Следствие 1.2.1 Каждый тл+-неподвижный лист любого (xi,d, n)-максимального дерева имеет лист-дубликат.

Список литературы диссертационного исследования кандидат наук Талецкий Дмитрий Сергеевич, 2019 год

Литература

[1] Воронин В. П., Демакова Е. В. О числе независимых множеств для некоторых семейств графов // Труды IV Международной конференции «Дискретные модели в теории управляющих систем», Красновидово, Московская область, 19-25 июня 2000. — С. 145-149.

[2] Дайняк А. Б. О числе независимых множеств в полных д-арных деревьях // Учёные записки Казанского государственного университета. Серия «физико-математические науки», Изд-во Казанского ун-та, Казань. — 2009. — Т. 151. — С. 59-64.

[3] Дайняк А. Б. О числе независимых множеств в деревьях фиксированного диаметра // Дискретный анализ и исследование операций. — 2009. — Т. 16, N0 2. — С. 61-73.

[4] Дайняк А. Б., Сапоженко А. А. Независимые множества в графах // Дискретная математика. — 2016. — Т. 28, N0. 1. — С. 44-77.

[5] Коршунов А. Д., Сапоженко А. А. О числе двоичных кодов с расстоянием 2 // Проблемы кибернетики. — 1983. — Т. 40. — С. 111-130.

[6] Талецкий Д. С. О производящих функциях и предельных теоремах, связанных с максимальными независимыми множествами в графах-решетках // Журнал Средневолжского математического общества. — 2017. — Т. 19, N0. 2. — С. 105-116.

[7] Талецкий Д. С. О свойствах решения рекуррентного уравнения, перечисляющего максимальные независимые множества в полных деревьях //

Журнал Средневолжского математического общества. — 2018. — T. 20, No. 1. — С. 46-54.

[8] Талецкий Д. С., Малышев Д. С. О количестве максимальных независимых множеств в полных q-арных деревьях // Дискретная математика. — 2016. — Т. 28, No 4. — С. 139-149.

[9] Талецкий Д. С., Малышев Д. С. О деревьях ограниченной степени с максимальным количеством наибольших независимых множеств // Дискретный анализ и исследование операций. — 2018. — Т. 25, No 2.

— С. 101-123.

[10] Талецкий Д. С., Малышев Д. С. Деревья без листьев-дубликатов с наименьшим количеством максимальных независимых множеств // Дискретная математика. — 2018. — Т. 30, No 4. — С. 115-133.

[11] Adriantiana E., Wagner S. On the number of independent subsets in trees with restricted degrees // Mathematical and Computer Modelling. — 2009.

— Vol. 51. — P. 678-683.

[12] Andriantiana E. Energy, Hosoya index and Merrifield-Simmons index of trees with prescribed degree sequence // Discrete Applied Mathematics. — 2013.

— Vol. 161, No. 6. — P. 724-741.

[13] Baxter R. J., Enting I. G., Tsang S. K. Hard-Square Lattice Gas // Journal of Statistical Physics. — 1980. — Vol. 22. — P. 465-489.

[14] Calkin N. J., Wilf H. S. The number of independent sets in a grid graph // SIAM Journal of Discrete Mathematics. — 1998. — Vol. 11, No. 1. — P. 54-60.

[15] Cohen D. Counting stable sets in trees // Seminaire Lotharingien de Combinatoire, 10eme session, R. Konig, ed., Institute de Recherche Mathematique Avancee Pub., Strasbourg, France. — 1984. — P. 48-52.

[16] Dainiak A. B. Sharp bounds for the number of maximal independent sets in trees of fixed diameter // arXiv:0812.4948v1. — 2008.

[17] Derikvand T., Oboudi M. R. On the number of maximum independent sets of graphs // Transactions on Combinatorics. — 2014. — Vol. 3, No. 1. — P. 29-36.

[18] Engel K. On the Fibonacci number of an m x n lattice // Fibonacci Quarterly

— 1990. — Vol. 28. — P. 72-78.

[19] Euler R. The Fibonacci number of a grid graph and a new class of integer sequences // Journal of Integer Sequences. — 2005. — 8:07.2.6. — P. 1-12.

[20] Frendrup A., Pedersen A., Sapozhenko A., Vestergaard P. Merrifield-Simmons index and minimum number of independent sets in short trees // Ars Combinatoria. — 2013. — V. 111. — P. 85-95.

[21] Furedi Z. The number of maximal independent sets in connected graphs // Journal of Graph Theory. — 1987. — Vol. 11. — P. 463-470.

[22] Griggs J., Grinstead C., Guichard D. The number of maximal independent sets in a connected graph // Discrete Mathematics. — 1988. — Vol. 68, No 2-3. — P. 211-220.

[23] Heuberger C., Wagner S. Maximizing the number of independent subsets over trees with bounded degree // Journal of Graph Theory. — 2008. — Vol. 58, No 1. — P. 49-68.

[24] Hosoya H., Topological index. A newly proposed quantity characterizing the topological nature of structural isomers of saturated hydrocarbons // Bulletin of the Chemical Society of Japan. — 1971. — Vol. 44, No. 9. — P. 2332-2339.

[25] Hopkins G., Staton W. Graphs with unique maximum independent sets // Discrete Mathematics. 1985. — Vol. 57. — P. 245 - 251.

[26] Hujter M., Tuza Z. The number of maximal independent sets in triangle-free graphs // SIAM Journal of Discrete Mathematics. — 1993. — Vol. 6, No 2.

— P. 284-288.

[27] Jin Z., Li X. Graphs with the second largest number of maximal independent sets // Discrete Mathematics - 2008. - Vol. 308. - P. 5864-5870.

[28] Jin Z., Yan, H. F. Trees with the second and third largest number of maximal independent sets // Ars Combinatoria. — 2009. — Vol. 93. — P. 341-351.

[29] Jou M. J. The second largest number of maximal independent sets in connected graphs with at most one cycle // Journal of Combinatorial Optimization. — 2012. — Vol. 24, No. 3. — P. 192-201.

[30] Jou M. J., Chang G. Maximal independent sets in graphs with at most one cycle // Discrete Applied Mathematics. — 1997. — Vol. 79, No 1-3. — P. 67-73.

[31] Jou M. J., Chang G. The number of maximum independent sets in graphs // Journal of Graph Theory. — 2000. — Vol. 4, No 4. — P. 685-695.

[32] Jou M. J., Chang G. J., Lin Chiang C., Ma T.-H. A finiteness theorem for maximal independent sets // Journal Graphs and Combinatorics. — 1996.

[33] Jou M. J., Lin J. J. Trees with the second largest number of maximal independent sets // Discrete Mathematics. — 2009 — Vol. 309 — P. 4469-4474.

[34] Kalkin N. J. The number of independent sets in a grid graph // SIAM Journal of Discrete Mathematics. — 1997. — Vol. 11, No 1. — P. 54-60.

[35] Kirschenhofer P. Fibonacci numbers of graphs: II // The Fibonacci Quarterly. — 1983. — Vol. 21, No 3. — P. 219-229.

[36] Kirschenhofer P., Prodinger H., Tichy R. F. Fibonacci numbers of graphs III // Proceedings of the First International Conference on Fibonacci Numbers and Applications. — 1986. — P. 105-120.

[37] Li S., Zhang H. Zhang, X. Maximal independent sets in bipartite graphs with at least one cycle // Discrete Mathematics and Theoretical Computer Science. — 2013. — Vol. 15, No. 2. — P. 243-258.

[38] Liu J. Maximal independent sets in bipartite graphs // Journal of Graph Theory. - 1993. - Vol. 17, No 1. - P. 495-507.

[39] Merrifield R. E., Simmons H. E. Topological methods in chemistry, Wiley, New York. - 1989.

[40] Miller R. E., Muller D. E. The problem of maximum consistent subsets // IBM Research Report RC-240. J. T. Watson Research Center, Yorktown Heights, N.Y. - 1960.

[41] Moon J., Moser L. On cliques in graphs // Israel Journal of Mathematics.

- 1965. - Vol. 3, No 1. - P. 23-28.

[42] Oh S., Lee S. Enumerating independent vertex sets in grid graphs // Linear Algebra and its Applications. - 2016. - Vol. 510. - P. 192-204.

[43] Pedersen A. S., Vestergaard P. D. An upper bound on the number of independent sets in a tree // Ars Combinatoria. - 2007. - Vol. 84. - P. 85-96.

[44] Prodinger H., Tichy R. F. Fibonacci numbers of graphs // Fibonacci Quarterly. - 1982. - Vol. 19. - P. 16-21.

[45] Sagan B. E. A note on independent sets in trees // SIAM Journal of Discrete Mathematics. - 1988. - Vol. 1. - P. 105-108.

[46] Wagner S., Wang H., Yu G. Molecular graphs and the inverse Wiener index problem // Discrete Applied Mathematics. - 2009. - Vol. 157. - P. 15441554.

[47] Weber K. On the number of stable sets in an m x n lattice // Rostocker Mathematisches Kolloquium. - 1988. - Vol. 34. - P. 28-36.

[48] Weigt M., Hartmann A. K. Glassy behavior induced by geometrical frustration in a hard-core lattice gas model // Europhysics Letters. - 2003.

- Vol. 62. - P. 533.

[49] Wiener H. Structural determination of paraffin boiling points // Journal of the American Chemical Society. — 1947. — Vol. 1, No. 69, P. 17-20.

[50] Wilf H. The number of maximal independent sets in a tree // SIAM Journal of Algebraic Discrete Methods. — 1986. — Vol. 7, No 1. — P. 125-130.

[51] Wloch I. Trees with extremal numbers of maximal independent sets including the set of leaves // Discrete Mathematics. — 2008. — Vol. 309, No. 20. — P. 4768-4772.

[52] Wood D. On the number of maximal independent sets in a graph // Discrete Mathematics and Theoretical Computer Science. — 2011. — Vol. 13, No. 3. — P. 17-19.

[53] Ying G. C., Meng K. K., Sagan B. E., Vatter V. E. Maximal independent sets in graphs with at most r cycles // Journal of Graph Theory. — 2006. — Vol. 53, No. 4. — P. 270-282.

[54] Zhao Y. The number of independent sets in a regular graph // Combinatorics, Probability and Computing. — 2009. — Vol. 19. — P. 315-320.

[55] Zito J. The structure and maximum number of maximum independent sets in trees // Journal of Graph Theory. — 1991. — Vol. 15, No 2. — P. 207-221.