О числе минимальных вершинных покрытий

Аннотация
Объектом исследования в данной работе является особый класс графов – Цепочки. Вводятся в рассмотрение 2 новых подкласса Цепочек:
граф Гусеница и Цепочка Петерсена, звеньями которых служат цикл с концами в смежных вершинах и Граф Петерсена с концами в несмежных вершинах соответственно.
Находится число минимальных вершинных покрытий указанных классов графов.

Цель работы – Найти вершинные характеристики Звеньев, основой
которых служат цикл с концами в смежных вершинах и
Граф Петерсена с концами в несмежных вершинах
– Определить число минимальных вершинных
покрытий Графа Гусеницы и Цепочки Петерсена.

Глава 1. Звенья и раскраски

Глава 2. Цепочки.
Основной результат

Глава 3. Граф Гусеница

Глава 4. Цепочки Петерсена

Цепочка Петерсена
Определение 4.1 Пусть G(5,2) – граф Петерсена.
Цепочку Ch(n, G(5,2), A,B), где A,B – несмежные вершины G(5,2),
назовём Цепочкой Петерсена и будем обозначать Ch(n, G(5,2)).

Заключение
В данной работе нами были исследованы два ярких представителя Цепочек: Граф Гусеница и Цепочка Петерсена.
В Главе 1 приведены понятия Звена графа и его вершинных характеристик, а также даны определения хорошей, О-почти хорошей и
АВ-почти хорошей раскрасок графа. Ключевым является утверждение, доказанное в Теореме 1.2: количество хороших раскрасок графа в точности совпадает с числом его минимальных вершинных покрытий.
В Главе 2 содержится основной результат по Цепочкам – формула для нахождения числа минимальных вершинных покрытий Цепочки (Теорема 2.1).
Коэффициенты данной формулы зависят от вершинных характеристик Звеньев. Указанный результат был получен ранее в [2].

Заключение
В Главах 3-4 найдены точные значения вершинных характеристик Звеньев, основой которых выступает цикл с концами в смежных вершинах (Теорема 3.2) и
граф Петерсена с концами в несмежных вершинах (Теорема 4.1).
В Главах 3-4 также установлены рекуррентные формулы для нахождения числа минимальных вершинных покрытий графа Гусеницы (Теорема 3.3) и
Цепочки Петерсена (Теорема 4.2).

Направления исследования
1. Нахождение числа минимальных вершинных покрытий Цепочек второго рода, получаемых путём замыкания Цепочек в цикл;
2. Расширение подклассов Цепочек за счёт изучения новых видов Звеньев.

Источники
1. Задача 13 «Окрестностные множества в графах» // РТЮМ-2018.
2. Листопадов М.В., Пасмурцев Е.С., Калугин П.Д. Вершинные покрытия графов // Доклад на XXV республиканском конкурсе работ исследовательского характера учащихся.
3.https://ru.wikipedia.org/wiki/%D0%93%D1%80%D0%B0%D1%84_%D0%9F%D0%B5%D1%82%D0%B5%D1%80%D1%81%D0%B5%D0%BD%D0%B0

СПАСИБО ЗА ВНИМАНИЕ!!!