Исследование количеств паросочетаний в некоторых классах графов тема диссертации и автореферата по ВАК РФ 00.00.00, кандидат наук Кузьмин Никита Александрович

• Кузьмин Никита Александрович
• кандидат наук
• 2025

Оглавление диссертации кандидат наук Кузьмин Никита Александрович

3.4 Преобразование висячих циклов

3.5 Некоторые дополнительные преобразования циклов

3.6 Основной результат этой главы

4 Перечисление паросочетаний в полных д-арных деревьях

4.1 Рекуррентные соотношения для количеств паросочетаний и порожденных паросочетаний в {Тд,^}

4.2 Некоторые вспомогательные результаты из математического анализа

4.3 Асимптотика количества паросочетаний в деревьях {Тч^}

4.4 Асимптотика количества порожденных паросочетаний в деревьях {Тя,4

4.4.1 Случай 1 < д <

4.4.2 Случай больших д - разрешимость одной системы нели-

нейных уравнений

4.4.3 Случай больших д - предельные равенства

4.4.4 Основной результат этого раздела

Заключение

Литература

Введение

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

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

В данной диссертационной работе (если явным образом не оговаривается иное) рассматриваются только обыкновенные графы, т.е. конечные неориентированные графы без петель и кратных ребер. Паросочетанием графа называется произвольное множество попарно несмежных его ребер. Индекс Хосойи (называемый еще г-индексом), предложенный в работе [21] японским химиком Харуо Хосойя, определяется как количество его паросочетаний, включая и пустое. Значения индекса Хосойи определяют некоторые физико-химические свойства соответствующих химических соединений, в частности, точки кипения алканов, энергию сопряженных п-электронных систем, см., например, обзоры [22, 23, 24, 25]. С индексом Хосойи через понятие реберного графа (т.е. графа смежности ребер) непосредственно связан индекс Меррифилда-Симмонса [31], определяемый как количество подмножеств попарно несмежных вершин графа (независимых множеств), также влияющий на некоторые свойства углеводородов. Отметим высокоцитируемые работы [15, 16, 28, 40], посвященные некоторым вопросам теории индексов Винера и Меррифилда-Симмонса.

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

По всей видимости, исторически первый результат о максимизации индекса Хосойи в классах графов был получен И. Гутманом в работе [17]. Именно, там было показано, что среди ациклических полиэнов максимальное значение значение ¿-индекса имеет линейный изомер. В графовых терминах это можно переформулировать (и несколько обобщить) так: для любого п в классе п-вершинных деревьев единственным максимальным графом является п-путь. Структура оптимального дерева мотивировала исследователей варьировать ассоциированные с ним ограниченные параметры (количество листьев, максимальную степень, наличие совершенного паросочетания и т.д.), выявлять соответствующие максимальные деревья и находить значение индекса Хосойи на них. Значительный интерес также вызывают аналогичные постановки задач для недревесных случаев.

В той же работе [17] было доказано, что для любого п > 6 в классе п-вершинных деревьев предмаксимальный граф единственен и получается соединением ребрами висячей вершины (п — 4)-пути с двумя 2-путями. Данный граф имеет 3 листа и поэтому является максимальным элементом класса п-вершинных деревьев с 3 листьями. Случай п-вершинных деревьев с 4 листьями рассматривался в работе [40]. Оказалось, что для любого п > 9 максимальное дерево получается соединением ребрами каждой висячей вершины (п — 8)-пути с двумя 2-путями. В других работах рассматривался случай деревьев с большим количеством листьев. Например, в работе [47] установлено, что для любого п = 2к + г, где к > 2 и г € {0,1}, в классе п-вершинных деревьев с к + 1 висячей вершиной максимальный граф единственен. Если г = 0,

то соответствующий граф получается соединением ребрами к — 1 изолированной вершины со всеми нелистовыми вершинами (к + 1)-пути. Если г = 1, то соответствующий граф получается соединением ребрами к — 1 изолированной вершины со всеми, кроме одной предлистовой, нелистовыми вершинами (к + 2)-пути.

В работе [40] показано, что для любого п > 4 и любого допустимого ^ в классе п-вершинных деревьев с максимальной степенью вершины ^ максимальный граф единственен. Если d > п——1, то соответствующий граф получается соединением ребрами центральной вершины звезды порядка 2d — п + 1 с п — 1 — d копиями 2-пути. Если d < -, то соответствующий граф получается соединением ребрами висячей вершины (2d — п + 1)-пути с d — 1 копией 2-пути.

В работе [32] рассматривался класс п-вершинных деревьев диаметра 5, содержащих совершенное паросочетание, т.е. паросочетание, которое покрывает все вершины. Оказалось, что для любого п = 4р + г, где р > 2 и г € {0, 2}, максимальный граф единственен. Если г = 0, то соответствующий максимальный граф получается присоединением ребрами р копий 2-пути к одной вершине 2-пути и р — 1 копии 2-пути к другой. Если г = 2, то соответствующий максимальный граф получается присоединением ребрами р копий 2-пути к каждой вершине 2-пути.

В работе [33] рассматривался класс п-вершинных графов, не содержащих совершенного паросочетания. В ней было доказано, что для любого п = 4р+г, где г € {0,2}, максимальный граф единственен. Если г = 0, то соответствующий граф получается соединением ребром изолированной вершины с центральной вершиной (п — 1)-пути. Если г = 2, то соответствующий граф получается соединением ребром изолированной вершины с вершиной (п — 1)-пути, смежной с его центральной вершиной.

В работе [37] для некоторых п и 7 были описаны максимальные п-вершинные деревья с числом доминирования 7, причем такое дерево в каждом случае оказалось единственным.

Квази-деревом называется граф, получаемый соединением ребрами некоторых вершин дерева с изолированной вершиной. Такие графы рассматривались в работе [29]. В ней было доказано, что для любого п > 2 в классе п-вершинных квази-деревьев максимальный граф единственен и получается соединением ребрами изолированной вершины со всеми вершинами (п — 1)-пути.

Заметное количество работ посвящено максимизации ¿-индекса для классов (п,п + к)-графов, т.е. связных графов с п вершинами и п + к ребрами. В работе [18] (с исправлением в [19]) было установлено, что для любого п > 3 в классе (п, п)-графов единственным максимальным элементом является п-цикл. В работах [42] для любого п > 5 были описаны все предмаксималь-ные (п,п)-графы, таких графов получилось 2 (кроме случая п = 6). Первый получается соединением ребром (п — 2)-цикла с листовой вершиной 2-пути, второй граф получается соединением ребром 4-цикла с листовой вершиной (п — 4)-пути. В классе (п,п + 1)-графов единственный максимальный граф получается соединением ребром 4-цикла и (п — 4)-цикла. Это было доказано в работах [12, 30], работа [12] содержала ошибку, приводящую к неправильному ответу и исправленную в [30]. Заметим, что аналогичная задача для (п, п + 1)-графов но без висячих вершин была уже решена в [18, 19]. В работе [30] установлено, что для любого п > 15 в классе (п,п + 2)-графов максимальный граф единственен и получается соединением ребрами двух 4-циклов с последовательными вершинами (п — 8)-цикла.

Для любых п > 3 и д > 3 в классе (п,п)-графов с заданным обхватом д, т.е. длиной кратчайшего цикла, максимальный граф является единственным [13]. Оказалось, что такой граф получается соединением ребром д-цикла с висячей вершиной (п — д)-пути. В работах [45, 46] для любых п > 6 и ё, > 3 в классах (п, п)-графов и (п, п+1)-графов с максимальной степенью вершины ё, были найдены все экстремальные графы. Отметим, что в некоторых случаях таких графов было несколько.

Шестиугольные цепи играют важную роль в математической химии как

природные представления бензоидных углеводородов. Так в работах [10, 20, 35, 36, 38, 48] рассматривались различные типы шестиугольных цепей и были описаны соответствующие максимальные графы. Аналогичные результаты для одного из классов многоугольных цепей были получены в работе [39].

В работах [43, 44] рассматривалась и решалась задача максимизации ¿-индекса для п-вершинных графов с заданным кликовым числом и связностью. Оказалось, что в обоих случаях оптимальные графы единственны для всех значений параметров. Отметим некоторые недавние результаты [11, 34] о максимизации ¿-индекса в некоторых классах графов.

При поиске графов с экстремальным значением индекса Хосойи обычно используется ряд стандартных приемов. Среди этих приемов отметим доказательство отсутствия висячих вершин стандартными преобразованиями графов, установление формы возникающих графов, их параметризация и настройка параметров с использованием стандартных расщеплений циклов и прокаток циклов вдоль пути или цикла с использованием свойств чисел Фибоначчи.

В данной диссертационной работе предлагается новый метод поиска графов из заданных классов, имеющих максимальное значение ¿-индекса, основанный на специальных локальных преобразованиях. Данный метод описывается в первой главе, где также приводятся некоторые используемые в работе определения и обозначения теории графов. Во второй главе диссертации рассматривается задача максимизации ¿-индекса в классе п-вершинных деревьев диаметра не более чем 5, которая там полностью решается с помощью упомянутого метода. Данные результаты опубликованы в [2, 5] и обобщают результат из [32]. Во второй главе работы также рассматривается и полностью решается методом локальных преобразований графов задача максимизации ¿-индекса в классе деревьев с п вершинами и 5 или 6 листьями при всех достаточно больших п, продолжая результаты работ [17] и [40]. Этот результат опубликован в [6]. В третьей главе приводится новое, более короткое и комбинаторное, доказательство известного результата (см. работу [30]) о структуре

максимальных (п,п + 2)-графов при п > 17. Оно было получено независимо от содержания работы [30] и использует несколько новых локальных преобразований графов, увеличивающих г-индекс и не представленных в работе [30]. Соответствующий результат опубликован в работе [3].

В работе [27] была найдена асимптотика количества всех независимых множеств в полных д-арных деревьях при стремлении высоты дерева к бесконечности. Выяснилось, что вид асимптотики при 1 < д < 4 отличается от вида асимптотики при д > 5, в этом случае он зависит от четности высоты дерева. В работе [7] рассматривалась аналогичная задача для максимальных независимых множеств. Там было показано, что при д = 2 вид асимптотики такой же, как и в случае всех независимых множеств при 1 < д < 4, а при всех достаточно больших д вид асимптотики зависит от остатка при делении на 3 высоты дерева.

В четвертой главе диссертации исследуются асимптотики количеств па-росочетаний и порожденных паросочетаний (т.е. паросочетаний, в которых никакие два ребра одновременно несмежны ни с каким другим) в полных д-арных деревьях при стремлении их высоты к бесконечности. В ней показывается, что для просто паросочетаний вид асимптотики не зависит от д и что для порожденных паросочетаний имеется одна картина при 1 < д < 3, а при всех достаточно больших д ее вид зависит от остатка при делении на 3 высоты дерева. Там же проводятся вычислительные эксперименты по выяснению области справедливости последнего утверждения в терминах д. Эти результаты опубликованы в работе [4].

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

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

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

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

2. Выявить все графы, имеющие максимальный индекс Хосойи среди п-вершинных деревьев диаметра не более чем 5, деревьев с 5 или с 6 листьями, а также связных п-вершинных графов с п + 2 ребрами.

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

Введение диссертации (часть автореферата) на тему «Исследование количеств паросочетаний в некоторых классах графов»

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

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

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

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

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

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

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

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

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

2. Для любых п и 4 < d < 5 найдены все п-вершинные деревья диаметра d, имеющие максимальный индекс Хосойи среди всех таких деревьев.

3. Найдены все п-вершинные деревья с 5 листьями (при п ^ 20) или с 6 листьями (при п ^ 26), имеющие максимальный индекс Хосойи среди всех таких деревьев.

4. Предложено новое, более короткое и менее техническое, доказательство

известного результата о структуре связных графов с п ^ 17 вершинами и п+2 ребрами, имеющих максимальный индекс Хосойи среди всех таких графов.

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

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

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

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

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

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

Во второй главе диссертации для любых п и 1 < ё, < 5 полностью описываются п-вершинные деревья диаметра имеющие максимальный ¿-индекс

среди всех таких деревьев. Там же для полностью описываются все п-вершинные деревья с 5 листьями (при п ^ 20) или с 6 листьями (при п ^ 26), имеющие максимальный ¿-индекс среди всех таких деревьев.

В третьей главе диссертации излагается новое доказательство известного результата о структуре связных графов с п ^ 17 вершинами и п + 2 ребрами, имеющих максимальный ¿-индекс среди всех таких графов.

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

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

8. Степень достоверности и апробации результатов работы, публикации автора по теме диссертации

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

1. Международная конференция студентов, аспирантов и молодых ученых «Ломоносов» (Москва, 2021).

2. Заочный семинар XIX международной конференции «Проблемы теоретической кибернетики» (Москва, 2021).

3. Международная конференция «Актуальные тренды 2022 года в комби-

наторике и геометрии: исследование и преподавание» (Сочи, 2021).

4. XIV международный научный семинар «Дискретная математика и ее приложения» (Москва, 2022).

5. Международная научная конференция «Графы, игры и модели» (Майкоп, 2022).

6. Международная научная конференция «Анализ данных, сети и аппроксимации» (Сочи, 2023).

7. Третья конференция математических центров России (Майкоп, 2023).

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

9. Семинар лаборатории комбинаторных и геометрических структур МФТИ.

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

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

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

1. Кузьмин Н.А. О деревьях радиуса 2 с максимальным количеством па-росочетаний // Журнал Средневолжского математического общества. — 2020. — Т. 22, № 2. — С. 177-187.

2. Кузьмин Н.А., Малышев Д.С. Новое доказательство результата о полном описании (п,п + 2)-графов с максимальным значением индекса Хосойи // Математические заметки. — 2022. — Т. 111, № 2. — С. 258-276.

3. Кузьмин Н.А., Малышев Д.С. Перечисление паросочетаний в полных д-арных деревьев // Математические заметки. — 2022. — Т. 111, № 3. — С. 393-402.

4. Кузьмин Н.А., Малышев Д.С. О деревьях диаметра 5 с максимальным

количеством паросочетаний // Математический сборник. — 2023. — Т. 214, № 2. — С. 143-154.

5. Кузьмин Н.А., Малышев Д.С. О 5- и 6-листных деревьях, имеющих наибольшее количество паросочетаний // Математические заметки. — 2024. — Т. 115, № 3. — C. 372-385.

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

Глава 1

Терминология, обозначения и некоторый класс преобразований графов

В первой главе определяются некоторые понятия и обозначения теории графов, которые будут использоваться на протяжении всей данной диссертации. Все основные понятия и факты, которые в этой и следующих главах не приводятся, можно найти, например, в учебниках [1, 8, 9, 14]. В первой главе диссертации также излагается метод для построения локальных преобразований графов, увеличивающих индекс Хосойи. Этот метод был предложен в работе [3].

1.1 Некоторые понятия и обозначения теории графов 1.1.1 Множества, графы и их подграфы

Через N обозначается множество натуральных чисел. Для множеств А и В через А и В, А П В, А \ В обозначены объединение, пересечение и разность множеств А и В.

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

Мультиграфом называется неориентированный граф, в котором допускаются кратные ребра. Псевдографом называется неориентированный граф, в котором допускаются петли и кратные ребра.

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

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

• через Сп обозначается п-цикл, т.е. простой цикл, содержащий п вершин,

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

Граф Кр,1 иногда называется р-звездой. Вилкой называется результат подразбиения произвольного ребра 3-звезды. Связный граф с п вершинами и т ребрами называется (п, т)-графом.

Деревом называется связный граф без циклов. Полным д-арным деревом высоты Н называется корневое дерево, все листья которого находятся на расстоянии Н от корня, степень корня равна д, а степень всех остальных вершин, кроме вершин степени 1, равна д + 1. Такое дерево будет обозначаться через

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

Изоморфизм графов С1 и С2 обозначается через С1 = С2. Пусть С — граф, V Е V(С),У' С V(С),Е' С Е(С). Степень вершины V обозначается через а ее окрестность через ). Графы С \ V' и С \ Е' получаются из С удалением всех вершин из V' и всех ребер из Е', соответственно, имея в виду, что удаление вершины подразумевает удаление всех инцидентных ей ребер. Подграф графа С, порожденный подмножеством V', обозначается через С^'].

1.1.2 Метрические характеристики, специальные вершины и ребра

Эксцентриситетом вершины графа называется максимальное из расстояний между ней и остальными вершинами. Диаметр графа — максимальный из эксцентриситетов его вершин. Центральная вершина графа — вершина с минимальным эксцентриситетом. Центр графа — множество его центральных вершин. По теореме Жордана [26] центр любого дерева состоит либо из одной вершины, либо из двух смежных вершин. Вершина степени один графа называется листом (или висячей вершиной). Мостом графа называется ребро, удаление которого увеличивает количество его компонент связности.

1.1.3 Паросочетания, индекс Хосойи и его разложение по ребру

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

г(О).

Для любых графов О1 и О2 с непересекающимися множествами вершин выполнено г(О1+О2) = г(О1)^г(О2), где О1+О2 — дизъюнктное объединение О1 и О2.

Пусть О — граф, е Е Е (О). Равенство г (О) = г+(О,е) + г_(О,е), где г+(О,е) и г_(О,е) — количества паросочетаний О, содержащих и не содержащих е, соответственно, будем называть разложением г (О) по ребру е. Например, воспользовавшись этим разложением, нетрудно установить, что при любом г индекс Хосойи пути на г вершинах равен где

^о = 0, = = 1, ^ = + ^_2, г > 3 — числа Фибоначчи.

Важным свойством чисел Фибоначчи, которое мы будем использовать в данной работе, является следующее тождество:

^и+ш ^и+1 • + Р'и • ^ш—Ъ п > ° ^^ > 1.

Оно может быть доказано разложением г-индекса (п + т — 1)-пути по п-ому его ребру.

Граф С из заданного класса графов X будем называть максимальным, если он имеет наибольший индекс Хосойи среди всех IV(С)|-вершинных графов из X.

1.2 Лемма о разложении г-индекса и следствия из нее

Пусть С — некоторый граф, а Н — его подграф. Любое подмножество Б С V(Н) такое, что никакая вершина из V(С) \ V(Н) несмежна ни с какой вершиной из V(Н) \ Б, назовем Н-отделяющим. Пусть Б — некоторое Н-отделяющее множество. Через Сs обозначим граф

((V(С) \ V(Н)) и Б,Е(С) \ Е(Н)).

Пусть А, В С V (С) и А П В = 0. Через г (С, А, В) обозначается количество паросочетаний графа С, покрывающих все вершины из А и не покрывающих ни одной вершины из В.

Лемма 1.2.1. Справедливо равенство

г (С) = ^ г (Сs, Б', Б \ Б') • г (Н \ Б').

s'cs

Доказательство. Каждое паросочетание графа С может быть разбито на две части — паросочетание графа и паросочетание графа Н. В графе Сs оно покрывает некоторое подмножество Б' С Б и не покрывает подмножество Б \ Б'. Для любого Б' С Б количество таких паросочетаний графа С равно г(С,5<, Б', Б \ Б') • г(Н \ Б'). Суммируя по всем подмножествам множества Б, мы получаем количество всех паросочетаний графа С. □

Предположим, что Gs состоит из двух компонент связности СS и СS. Положим = V^) П Б, Б2 = V ^) П Б. Тогда для любого Б' С Б по лемме 1.2.1 справедливо

г(Сs, Б', Б \ Б') = г^, 51 П Б', 51 \ Б') • г^, 52 П Б', 52 \ Б').

19

Откуда получаем

г (О) = ^ = г (ОБ, 51 П 5", 51 \ 5") • г (О|, 52 П 5", 52 \ 5") • г(Н \ 5").

5 'СБ

Предположим, что некоторые графы О1 и О2 содержат подграфы Н1 и Н2, соответственно, причем одновременно выполнены следующие два условия:

1. некоторое подмножество 5 С V(О1) П V(О2) одновременно является и ^-отделяющим и Н2-отделяющим,

2. подграфы ОБ и О| изоморфны. По лемме 1.2.1 выполнено

г (О2) _ г (О1) = ^ г(ОБ, 5', 5 \ 5") • Л(5"),

ч2\ „ГГ11) =

Б 'СБ

где Л(5") = г(Н2 \ 5") _ г(Н1 \ 5"). Из нее же прямо следует справедливость следующего утверждения:

Следствие 1.2.1. Если для любого подмножества 5" С 5 справедливо Л(5') > 0, причем для некоторого б7 С 5 выполнено

Л(5') > 0,г(ОБ,5,5 \ 5') = 0,

то г (О2) > г (О1).

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

Предположим, что в некотором графе О выделены вершины и и и>, не обязательно различные. Для к ^ 1 через обозначим граф, получаемый добавлением к О простого пути ,..., vk) и ребер г^и, w (см. рисунок 1.1).

Рис. 1.1: Граф

Уточним, что в случае и = ад, к = 1 граф С(1) будет мультиграфом с ребром кратности 2.

Переобозначим С через С(0). Справедливо следующее утверждение:

Следствие 1.2.2. Для любого к ^ 2 верно г(С(к)) = г(С(к—1)) + г(С(к—2)).

Доказательство. Предположим, что и = ад. По лемме 1.2.1 для Б = {и, ад} и любого р ^ 1 имеем

г(С(р)) = £ г^р), Б', Б \ Б') • .

s 'cs

Очевидно, что графы С|^), СS1), С^ ... изоморфны между собой. Тем самым, для любого Б' С Б имеем

г^0), Б', Б \ Б') = г(cS1), Б', Б \ Б') = г(СS2), Б', Б \ Б') = ...

Для любого г ^ 2 выполнено г(Д) = г1)+г(Р^—2). Значит, утверждение следствия справедливо, когда и = ад.

Если и = ад, то для Б = {и} доказательство проводится по аналогии. Случай к = 2 разбирается отдельно. При к ^ 3 используется равенство г(С^) = г(Сг—1) + г(С^—2), верное при всех г ^ 3. □

Глава 2

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

Во второй главе данной диссертации рассматривается и для любого п полностью решается задача максимизации г-индекса в п-вершинных деревьях диаметра не более чем 5. В ней также рассматривается и для любого достаточно большого п полностью решается задача максимизации г-индекса в п-вершинных деревьях с 5 или с 6 листьями. Эти результаты опубликованы в работах [2, 5, 6].

2.1 О максимальных деревьях диаметра не более чем 3

Задачи максимизации индекса Хосойи в деревьях диаметра 1 и 2 являются тривиальными. Первая из них осмыслена только для п = 2, а для второй единственным допустимым решением является (п _ 1)-звезда, где п > 3. Любое п-вершинное дерево диаметра 3 получается соединением ребром центральных вершин а-звезды и Ь-звезды, где а + Ь = п _ 2,п > 4. Его г-индекс равен

(а + 1) • (Ь + 1) + 1 = (а + 1) • (п _ 1 _ а) + 1.

Нетрудно видеть, что единственным оптимальным параметром будет

п

а = [ 2 1

2.2 О максимальных деревьях диаметра 4

2.2.1 Некоторые преобразования графов, увеличивающие индекс Хосойи

Предположим, что граф С1 состоит из подграфа С^ и связного подграфа С^' и отделенного от них вершинами и й2 порожденного 3-пути (^,й2,й1), а граф С2 состоит из подграфов С^ и С^^ и отделенного от них вершинами и й2 порожденного 3-пути (й2,^,й1) так, как показано на рисунке 2.1.

Лемма 2.2.1. Если V(С£) = {й2}; то г(С2) > г(С1).

Доказательство. Для доказательства этого утверждения воспользуемся следствием 1.2.1 и его обозначениями. Положим

С1 = С1, С2 = С2, Б = Ы, Н1 = Сl[V(С^)и{и, 52}], Н2 = С2[V(С^)и{и, 52}].

Л(0) = 0, Л({52}) = г(Н2\Ы) — г(С^) = г(С^\Ы) > 0, г(С£, {52}, 0) = 0,

Предположим, что граф С1 состоит из подграфа С и отделенной от него вершиной звездой Н1 с д + 1 листьями, см. рисунок 2.2.

В случае четного д граф С2 состоит из подграфа С- и отделенного от него вершиной подграфа Н2 так, как показано на рисунке 2.3.

Лемма 2.2.2. Для каждого четного д > 4 верно, что г(С2) > г(С1).

Доказательство. Для доказательства этого утверждения воспользуемся следствием 1.2.1 и его обозначениями. Положим

Рис. 2.1: Преобразование 2-1

Очевидно, что

т.к. С^ связен и V(С£) = {й2}. Поэтому г(С2) > г(С1).

□

С1 = С1,С2 = С2,Б = {51}.

Рис. 2.2: Граф Сх

Рис. 2.3: Преобразование 2-2

Очевидно, что

Л(0) = 3 • (^ - 1) • 22-2 + 22+1) - (д + 2) > 0, Л({^}) = 3 • 22-1 - (д + 1) > 0, 2

г(ОБ, 0, {51}) > 0.

Поэтому г(О2) > г(О1).

□

В случае нечетного д граф О2 состоит из подграфа ОБ и отделенного от него вершиной подграфа Н2 так, как показано на рисунке 2.4.

Рис. 2.4: Преобразование 2-3

Лемма 2.2.3. Для каждого нечетного д > 3 верно, что г(О2) > г(О1). Доказательство. Для доказательства этого утверждения воспользуемся

следствием 1.2.1 и его обозначениями. Положим

О1 = О1,О2 = О2,^ = {51}.

Очевидно, что

Л(0) = ^ • 2 V +2^ - (д + 2) > 0, Л({^}) = 2^ - (д + 1) > 0, 2

г(О", 0, {51}) > 0.

Поэтому г(О2) > г(О1). □

2.2.2 Центры максимальных деревьев диаметра 4 и смежные с ними поддеревья

Напомним, что по теореме Жордана центр любого дерева состоит либо из одной вершины, либо из двух смежных вершин.

Лемма 2.2.4. Центр каждого максимального дерева диаметра 4 состоит из одной вершины.

Доказательство. Пусть Т — максимальное дерево диаметра 4, имеющее две центральные вершины и й2. Применим к нему преобразование 2-1 и получим дерево Т диаметра 4 с тем же количеством вершин. По лемме 2.2.1 имеем, что г(Т) > г(Т). □

Лемма 2.2.5. В любом максимальном дереве диаметра 4 центральная вершина смежна не более чем с одним листом.

Доказательство. Пусть Т — максимальное дерево диаметра 4, центральная вершина й2 которого смежна с д > 2 листьями. Обозначим через О" подграф Т, порожденный й2 и д-1 листом, смежным с й2, а оставшийся лист обозначим через V. Отсоединим листья, смежные с й2 и принадлежащие О", а затем присоединим их к листу V. Получим дерево Т диаметра 4. Тогда из леммы 2.2.1 следует, что г(Т) > г(Т). □

Из лемм 2.2.1-2.2.5 заключаем, что каждое максимальное дерево Т* имеет один из двух видов из рисунка 2.5. Через а и Ь обозначены количества соответствующих вхождений 2-путей и 3-путей в дерево.

Рис. 2.5: Структура любого максимального дерева диаметра 4

2.2.3 Об отсутствии листа в максимальных деревьях диаметра 4, смежного с центральной вершиной

Предположим, что Т* содержит лист /, см. рисунок 2.5(11).

Случай а = 0

Удалим / и добавим его в качестве листового соседа к вершине степени 2 одного из а путей Р3 в п-вершинном дереве Т*. Полученное дерево обозначим через Т**. Очевидно, что диаметры деревьев Т* и Т** равны 4 и имеют одинаковые количества вершин.

Лемма 2.2.6. Если п > 12, то г(Т**) > г(Т*).

Доказательство. Несложно посчитать, что количество паросочетаний в дереве Т*, не покрывающих вершины с, ровно 2а • 3Ь штук. В случае, когда вершину с покрывает ребро /с, их так же 2а • 3Ь штук. В случае же, когда вершину с покрывают остальные смежные с ней ребра, то количество паро-сочетаний равно а • 2а—1 • 3Ь + Ь • 2а • 3Ь—1. Тем самым, справедливо равенство

г(Т*) = 2а+1 • 3Ь + а • 2а—1 • 3Ь + Ь • 2а • 3Ь—1 = 2а—1 • 3Ь—1 • (12 + 3а + 2Ь).

Аналогичным способом получаются соотношения

г(ТГ) = 2а—1^3ь+1+(а—1)^2а—2^3ь+1+(Ь+1)^2а—1^3Ь = 2а—2^(6+3(а—1)+2(Ь+1)),

г(Т**) — г(Т*) = 2а—2 • 3Ь—1 • (3а + 2Ь — 9).

Очевидно, что 3а + 2Ь = п — 2, поэтому 3а + 2Ь — 9 = п —11. Из чего следует, что г(ТГ) — г(Т*) > 0, при п > 12. □

Случай а = 0

В Т* удалим лист, отличный от 1, и прикрепим его к I в качестве листового соседа. Полученное дерево обозначим через Т2**.

Лемма 2.2.7. Справедливо неравенство г(Т2**) > г(Т*).

Доказательство. Справедливы следующие соотношения:

г(Т*) = 2 • 3Ь + Ь • 36"1, г(Т2**) = 23 • 36"1 + 4 • (Ь - 1) • 36"2.

Очевидно, что г(Т2**) - г(Т*) = (Ь + 2) • 36"2 > 0. Значит, г(Т2**) > г(Т*). □

Из лемм 2.2.6 и 2.2.7 следует, что при п > 12 каждое максимальное дерево диаметра 4 не содержит листа, смежного с центральной вершиной.

2.2.4 Настройка параметров а и Ь в максимальных деревьях диаметра 4

Предположим, что п > 12. Тогда каждое максимальное дерево диаметра 4 имеет вид, представленный на рисунке 2.5(1). Данное п-вершинное дерево будем обозначать через Т*6. Несложно проверить, что верны следующие равенства:

г(Та*,ь) = 2а • 3Ь + а • 2а-1 • 3Ь + Ь • 2а • 36"1 = 2а-1 • 36"1 • (6 + 3а + 2Ь), 2а + 3Ь = п -1.

Пусть /(а, Ь) = г(Т*6). Тогда поиск максимальных деревьев диаметра 4 сводится к нахождению глобального максимума функции / при соответствующих ограничениях. Имеем, что Ь = п-13-2а и подставим это в f (предполагая, что а Е К):

/ (а) = 2а-1 • 3 3 ,

1 п-4-2а ^ 2, . 2п + 5а + 16 5Ч 1а = 2 • 3— • ((1п2 - 2 1п3)--3- +

/ П 3 16 2

;а = 0 ^ а = 21п3 - 31п2 - У - 5п.

Пусть а*(п) = у^т--5п. Функция / возрастает на (-то, а*(п)) и убывает

8

на (а*(п), Нетрудно видеть, что а*(п) < 0 уже при п > 56.

а 1 п—4—2а 2п + 5а + 16

)а— 1 ^-

2.2.5 Полное описание максимальных деревьев диаметра 4

Из рассуждений подраздела 2.2.4 и целочисленности а и Ь следует, что справедлива следующая

Теорема 2.2.1. При любом п > 56, где п = 3к + г и к Е М,г Е {0,1, 2}, максимальное дерево диаметра 4 единственно и имеет вид дерева, представленного на рисунке 2.5(I), где Ь = к + г—13—2а и (г, а) Е {(0,1), (1,0), (2, 2)}.

С целью выявления максимальных деревьев диаметра 4 при 12 < п < 55 был проведен вычислительный эксперимент по поиску оптимальных целочисленных а и Ь, показавший следующие результаты (см. таблицу 2.1):

п а 6 п а 6 п а 6 п а 6

12 4 1 23 11 0 34 9 5 45 4 12

13 6 0 24 10 1 35 8 6 46 3 13

14 5 1 25 12 0 36 7 7 47 2 14

15 7 0 26 11 1 37 6 8 48 4 13

16 6 1 27 10 2 38 8 7 49 3 14

17 8 0 28 12 1 39 7 8 50 2 15

18 7 1 29 11 2 40 6 9 51 1 16

19 9 0 30 10 3 41 5 10 52 0 17

20 8 1 31 9 4 42 4 11 53 2 16

21 10 0 32 8 5 43 6 10 54 1 17

22 9 1 33 10 4 44 5 11 55 0 18

Таблица 2.1: Значения параметров а, 6 и 12 < п < 55, соответствующие максимальным деревьям диаметра 4

Напомним, что в случае п = 5 единственным максимальным деревом диаметра 4 будет п-путь. По леммам 2.2.1-2.2.5 случай 6 < п < 11 отличается от случая п > 12 возможным наличием листа, смежного с центральной вершиной. С целью поиска всех максимальных деревьев диаметра 4 при 6 < п < 11 был проведен вычислительный эксперимент, результат которого представлен в таблице 2.2. Параметр / в таблице отвечает за наличие листа, смежного с центральной вершиной, т.е. если / = 1, то такой лист существует, а если / = 0, то такого листа в дереве нет.

п а Ь 1 п а Ь 1 п а Ь 1

6 2 0 1 8 3 0 1 11 5 0 0

7 3 0 0 9 4 0 0

8 2 1 0 10 3 1 0

Таблица 2.2: Описание оставшихся максимальных деревьев диаметра 4

2.3 О максимальных деревьях диаметра 5

2.3.1 Некоторые новые преобразования графов, увеличивающие г-индекс

Предположим, что граф С состоит из связного подграфа Св и отделенного от него вершинами и й2 порожденного 4-пути Н1 = (и, й^в^-и), а граф С2 состоит из подграфа Св и отделенного от него вершинами и й2 порожденного 4-пути Н2 = (51,й2,^,м) так, как показано на рисунке 2.6.

Рис. 2.6: Преобразование 2-4

Лемма 2.3.1. Если V(Св) = то г(С2) > г(С1).

Доказательство. Для доказательства этого утверждения воспользуемся следствием 1.2.1 и его обозначениями. Положим

С1 = СЬС2 = ^2,5 = {51,52}.

Несложно проверить, что

Л(0) = 5 - 5 = 0, Л({^}) = 3 - 2 = 1,

Л({52}) = 2 - 2 = 0, Л({51, 52}) = 2 - 1 = 1.

Т.к. Св связен и V(Св) = {й1}, то г(Св, {й1}, {й2}) > 0. Поэтому г(С2) > г(С1). □

Предположим, что граф С1 состоит из подграфа Св и отделенной от него вершиной порожденной вилкой Н1 на множестве вершин {V, и, и1, й1}, а

граф С2 состоит из подграфа и отделенного от него вершиной порожденного 5-пути Н2 = (и1,и, в1,у,у1) так, как показано на рисунке 2.7.

Рис. 2.7: Преобразование 2-5

Лемма 2.3.2. Верно, что г(С2) > г(С1).

Доказательство. Для доказательства этого утверждения воспользуемся следствием 1.2.1 и его обозначениями. Положим

С1 = = С2)Б = {51}.

Несложно проверить, что

Л(0) = 8 - 7 = 1, Л{{в1}) = 4 - 3 = 1.

Поэтому г(С2) > г(С1). □

Предположим, что граф С1 состоит из подграфа и отделенного от него вершинами и в2 порожденного подграфа Н1 на множестве вершин {у,и,у1 ,и1,в1,52}, а граф С2 состоит из подграфа и отделенного от него вершинами и в2 порожденного 6-пути Н2 = (и1,и, в1, в2,у,у1) так, как показано на рисунке 2.8.

Рис. 2.8: Преобразование 2-6

Лемма 2.3.3. Верно, что г(С2) > г(С1).

Доказательство. Для доказательства этого утверждения воспользуемся следствием 1.2.1 и его обозначениями. Положим

С1 = С1,С2 = С2,5 = {51,52}.

Несложно проверить, что

Л(0) = 13 - 11 = 2, Л({51}) = 6 - 6 = 0,

Л({52}) = 6 - 4 = 2, Л({51, 52}) = 4 - 3 = 1.

Поэтому г(С2) > г(С1).

□

2.3.2 О свойствах максимальных деревьев диаметра 5

Структура максимальных деревьев диаметра 5 и некоторые ее свойства

Из лемм 2.2.1-2.2.3 следует, что каждое максимальное дерево диаметра 5 имеет вид, представленный на рисунке 2.9. Уточним, что Е {0,1}, где = 1 тогда и только тогда, когда соответствующий лист содержится в дереве. Через а и Ь-1 обозначено количество соответствующих вхождений 2-путей и 3-путей в дерево.

Рис. 2.9: Структура каждого максимального дерева диаметра 5

Индекс Хосойи такого дерева обозначим через /(11, /2, а1, а2, Ь1, Ь2). Очевидно, что если в данном дереве имеется п вершин, то

2а1 + 2а2 + 3Ь1 + 3Ь2 = п - /1 - /2 - 2.

(2.1)

Лемма 2.3.4. В любом максимальном дереве диаметра 5 выполнены следующие свойства:

1. Если дерево содержит центральный лист, то он единственный и &1 = &2 = 0.

2. Если п — четное, то дерево не содержит центральных листьев.

Доказательство. Из леммы 2.3.1 следует, что в любом максимальном дереве диаметра 5 либо /1 = 0, либо /2 = 0. Если в нем есть центральные листья, то можно считать, что /1 = 1. Из лемм 2.3.2 и 2.3.3 следует, что Ь1 = Ь2 = 0. Подставив эти значения в равенство (2.1) получим, что 2а1 + 2а2 = п — 3, что невозможно в случае четного п. □

Список литературы диссертационного исследования кандидат наук Кузьмин Никита Александрович, 2025 год

Литература

[1] Емеличев В.А., Мельников О.И., Сарванов В.И., Тышкевич Р.И. Лекции по теории графов. — М.: Наука, 1990. — 384 С.

[2] Кузьмин Н.А. О деревьях радиуса 2 с максимальным количеством па-росочетаний // Журнал Средневолжского математического общества. — 2020. — Т. 22, № 2. — С. 177-187.

[3] Кузьмин Н.А., Малышев Д.С. Новое доказательство результата о полном описании (n,n + 2)-графов c максимальным значением индекса Хосойи // Математические заметки. — 2022. — Т. 111, № 2. — С. 258-276.

[4] Кузьмин Н.А., Малышев Д.С. Перечисление паросочетаний в полных q-арных деревьев // Математические заметки. — 2022. — Т. 111, № 3. — С. 393-402.

[5] Кузьмин Н.А., Малышев Д.С. О деревьях диаметра 5 с максимальным количеством паросочетаний // Математический сборник. — 2023. — Т. 214, № 2. — С. 143-154.

[6] Кузьмин Н.А., Малышев Д.С. О 5- и 6-листных деревьях, имеющих наибольшее количество паросочетаний // Математические заметки. — 2024.

— Т. 115, № 3. — C. 372-385.

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

— Т. 28, № 4. — С. 139-149.

[8] Харари Ф. Теория графов. — М.: Мир, 1982. — 301 С.

[9] Bondy A., Murty U. Graph theory. — Springer-Verlag: Graduate texts in mathematics, V. 244, 2008. — 655 P.

[10] Chen X., Zhao B., Zhao P. Six-membered ring spiro chains with extremal Merrifield-Simmons index and Hosoya index // MATCH Communications in Mathematical and in Computer Chemistry. — 2009. — Vol. 62. — P. 657-665.

[11] Cruz R., Martin C.A., Rada J. Computing the Hosoya index of catacondensed hexagonal systems // MATCH Communications in Mathematical and in Computer Chemistry. — 2017. — Vol. 77. — P. 749-764.

[12] Deng H. The largest Hosoya index of (n,n + 1)-graphs // Computers and Mathematics with Applications. — 2008. — Vol. 56. — P. 2499-2506.

[13] Deng H., Chen S. The extremal unicyclic graphs with respect to Hosoya index and Merrifield-Simmons index // MATCH Communications in Mathematical and in Computer Chemistry. — 2008. — Vol. 59, № 1. — P. 171-190.

[14] Diestel R. Graph theory. — Springer-Verlag: Graduate texts in mathematics, V. 173, 2016. — 447 P.

[15] Dobrynin A.A., Entringer R., Gutman I. Wiener index for trees: theory and applications // Acta Applicandae Mathematicae. — 2001. — Vol. 66, № 3. — P. 211-249.

[16] Dobrynin A.A., Gutman I., Klavzar S., Zigert P. Wiener index of hexagonal systems // Acta Applicandae Mathematicae. — 2002. — Vol. 72, № 3. — P. 247-294.

[17] Gutman I. Acyclic systems with extremal Hiickel n-electron energy // Theoretical Chemistry Accounts. — 1977. — Vol. 45. — P. 79-87.

[18] Gutman I. Graphs with greatest number of matchings Hosoya index // Publications de l'Institut Mathematique. — 1980. — Vol. 27. — P. 67-76.

[19] Gutman I. Correction of the paper "Graphs with greatest number of matchings" // Publications de l'Institut Mathematique. — 1982. — Vol. 32.

— P. 61-63.

[20] Gutman I. Extremal hexagonal chains // Journal of Mathematical Chemistry.

— 1993. — Vol. 12. — P. 197-210.

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

[22] Hosoya H. The topological index Z before and after 1971 // Internet Electronic Journal of Molecular Design. — 2002. — Vol. 1. — P. 428-442.

[23] Hosoya H. Important mathematical structures of the topological index Z for tree graphs // Journal of Chemical Information and Modeling. — 2007. — Vol. 47. — P. 744-750.

[24] Hosoya H. Mathematical meaning and importance of the topological index Z // Croatica Chemica Acta. — 2007. — Vol. 80. — P. 239-249.

[25] Hosoya H. The most private features of the topological index // MATI. — 2019. — Vol. 1. — P. 25-33.

[26] Jordan C. Sur les assemblages de lignes // Journal fiir die reine und angewandte Mathematik. — 1869. — Vol. 70. — P. 185-190.

[27] Kirschenhofer P., Tichy R. Fibonacci numbers of graphs: II // The Fibonacci Quarterly. — 1983. — Vol. 21, № 3. — P. 219-229.

[28] Li X., Zhao H., Gutman I. On the Merrifield-Simmons index of trees // MATCH Communications in Mathematical and in Computer Chemistry. — 2005. — Vol. 54. — P. 389-402.

[29] Lia S., Lib X., Jinga W. On the extremal Merrifield-Simmons index and Hosoya index of quasi-tree graphs // Discrete Applied Mathematics. — 2009.

— Vol. 157, № 13. — P. 2877-2885.

[30] Liu Y., Zhuang W., Liang Z. Largest Hosoya index and smallest Merrifeld-Simmons index in tricyclic graphs // MATCH Communications in Mathematical and in Computer Chemistry. — 2015. — Vol. 73. — P. 195-224.

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

[32] Ou J. On acyclic molecular graphs with maximal Hosoya index, energy, and short diameter // Journal of Mathematical Chemistry. — 2008. — Vol. 43, № 1. — P. 221-233.

[33] Ou J. Maximal Hosoya index and extremal acyclic molecular graphs without perfect matching // Applied Mathematics Letters. — 2006. — Vol. 19, № 7.

— P. 391-397.

[34] Oz M.S., Martin C.A., Rada J. Computation method of the Hosoya index of primitive coronoid systems // Mathematical Biosciences and Engineering. — 2017. — Vol. 19, № 10. — P. 9842-9852.

[35] Ren H., Zhang F. Extremal double hexagonal chains with respect to k-matchings and k-independent sets // Discrete Applied Mathematics. — 2007.

— Vol. 115, № 17. — P. 2269-2281.

[36] Ren H., Zhang F. Double hexagonal chains with maximal Hosoya index and minimal Merrifield-Simmons index // Journal of Mathematical Chemistry.

— 2007. — Vol. 42. — P. 679-690.

[37] §ahin B. On Hosoya Index and Merrifield-Simmons Index of trees with given domination number // Numerical Methods for Partial Differential Equations.

— 2020. — Vol. 38, № 4. — P. 904-915.

[38] Shiu W. Extremal Hosoya index and Merrifield-Simmons index of hexagonal spiders // Discrete Applied Mathematics. — 2008. — Vol. 156, № 15. — P. 2978-2985.

[39] Tian W., Tian S., He X., Wang Y. Extremal problem with respect to Merrifield-Simmons index and Hosoya Index of a class of polygonal chains // Wuhan University Journal of Natural Sciences. — 2014. — Vol. 19, № 4. — P. 295-300.

[40] Wagner S. Extremal trees with respect to Hosoya index and Merrifield-Simmons index // MATCH Communications in Mathematical and in Computer Chemistry. — 2006. — Vol. 57. — P. 221-233.

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

[42] Xu L. The second largest Hosoya index of unicyclic graphs // MATCH Communications in Mathematical and in Computer Chemistry. — 2007. — Vol. 62. — P. 621-628.

[43] Xu K. On the Hosoya index and the Merrifield-Simmons index of graphs with a given clique number // Applied Mathematics Letters. — 2010. — Vol. 23, № 4. — P. 395-398.

[44] Xu K. The Hosoya indices and Merrifield-Simmons indices of graphs with connectivity at most k // Applied Mathematics Letters. — 2012. — Vol. 25, № 3. — P. 476-480.

[45] Xu K., Gutman I. The greatest Hosoya index of bicyclic graphs with given maximum degree // MATCH Communications in Mathematical and in Computer Chemistry. — 2011. — Vol. 66. — P. 795-824.

[46] Xu K., Xu B. Some extremal unicyclic graphs with respect to Hosoya index and Merrifield-Simmons index // MATCH Communications in Mathematical and in Computer Chemistry. — 2009. — Vol. 62. — P. 629-648.

[47] Yan W., Ye L. On the maximal energy and the Hosoya index of a type of trees with many pendant vertices // MATCH Communications in Mathematical and in Computer Chemistry. — 2005. — Vol. 53, № 2. — P. 449-459.

[48] Zhang L. The proof of Gutman's conjectures concerning extremal hexagonal chains // Journal of Systems Science and Mathematical Sciences. — 1998. — Vol. 18, № 4. — P. 460-465.