Максимально негамильтоновые графы

• Автор: Ролдугин, Павел Владимирович
• Шифр специальности: 01.01.09
• Научная степень: Кандидатская
• Год защиты: 2003
• Место защиты: Москва
• Количество страниц: 133 с. : ил.

ОГЛАВЛЕНИЕ
ОГЛАВЛЕНИЕ

ОСНОВНЫЕ ОБОЗНАЧЕНИЯ И СОКРАЩЕНИЯ

ВВЕДЕНИЕ И ОБЗОР ЛИТЕРАТУРЫ

Глава I. СВОЙСТВА СТРУКТУРЫ МАКСИМАЛЬНЫХ КЛИК

МАКСИМАЛЬНО НЕГАМИЛЬТОНОВЫХ ГРАФОВ

§ 1. Собственные вершины максимальных клик и сведение к упрощенным

МНГ графам

§2. Построение МНГ-системы

§3. Оценка порядков и числа упрощенных МНГ графов

Выводы
Глава И. ПРАВИЛА ВЫВОДА МАКСИМАЛЬНО НЕГАМИЛЬТОНОВЫХ
ГРАФОВ
§ 1. Свойства некоторых элементов МНГ графов
§2. Правила вывода, использующие основание графа
§3. Правила вывода, использующие промежуточные клики
§4. Правила вывода, использующие опорные и соединительные клики
§5. Цепочки правил вывода
Выводы
ЗАКЛЮЧЕНИЕ
Приложение 1. КАТАЛОГ ВСЕХ МАКСИМАЛЬНО НЕГАМИЛЬТОНОВЫХ
ГРАФОВ ПОРЯДКОВ ОТ 3 ДО
Приложение 2. ТРУДОЕМКОСТЬ ПРОВЕРКИ НЕГАМИЛЬТОНОВОСТИ
МНГ ГРАФОВ ПО СРАВНЕНИЮ С ДРУГИМИ ГРАФАМИ
ЛИТЕРАТУРА ;

ОСНОВНЫЕ ОБОЗНАЧЕНИЯ И СОКРАЩЕНИЯ
При изложении результатов работы удобно придерживаться следующих обозначений.
Символы, обозначающие переменные, вершины, графы и тому подобное будем выделять курсивом.
N - множество натуральных чисел.
Z - множество целых чисел.
- соответственно операции целочисленного сложения, вычитания и умножения.
1 ,г - множество натуральных чисел от 1 до г включительно.
С = (У,Е), Г = п, | Е = т: граф порядка п с множеством вершин V и множеством ребер Е.
V(С) - множество вершин графа (7.
Е(р) - множество ребер графа <7.
К1п - полный (то есть содержащий все возможные ребра) граф порядка

Етп - пустой (то есть не содержащий ребер) граф порядка п.
Цепь в графе будем записывать как последовательность вершин а =а1 а2... аг, предполагая, что любые две вершины а,- ам, і = 1,г-1 смежны. При этом запись 6, Ь2 а Ь3 означает цепь Ь, Ь2 а, а2... аг Ь2 и запись а-1 означает цепь аг аг_{... о,. Выражение «цикл аха2...аг» подразумевает, что вершины а, и аг смежны. Будем говорить, что цепь I содержит отрезок 7, если ? - подцепь цепи 1 . Напомним, что простой цепью называется цепь, в которой различны все вершины, кроме, возможно, крайних.

Любую клику (полный подграф) в графе будем отождествлять с ее множеством вершин, то есть выражение «в графе Я существует клика {<з,,...,аг}» означает, что любые две несовпадающие вершины из {а{,...,аг} смежны. Под максимальной кликой графа Я понимается полный подграф в Я, не принадлежащий целиком никакому другому полному подграфу графа Я. Поскольку в данной работе используются только максимальные клики графа, то слово «максимальная» иногда будем опускать.
Та - множество всех вершин графа Я, лежащих в пересечении всех максимальных клик графа (7.
Пусть Я - какой-то подграф в V((7). Выражение С Я обозначает граф, полученный из Я удалением вершин Г(Я) и всех инцидентных им ребер.
Пусть а - вершина графа Я. Через {а} будем обозначать как одноэлементное множество (состоящее из элемента а), так и подграф порядка 1 (состоящий из одной вершины а).
Я, и Я2 - объединение графов Я, и Я2 с непересекающимися множествами вершин; обозначает граф с множеством вершин Р = Г(Я,) и Н(Я2) и множеством ребер Е = Е(Я,)иЕ(р2).
+ С2 - соединение графов (7, и <72 с непересекающимися множествами вершин; обозначает граф, множеством вершин которого является V = Г(С,)иК((?2) и множество ребер есть Е = Е(Ох) и Е(С2) и {(V,, у2): у, є V(<3,), у2 є V(С2)}.
Добавлением собственной вершины а в клику К графа Я назовем следующую операцию: в граф Я добавляется новая вершина а, которая затем соединяется ребрами со всеми вершинами клики К и только с ними.
Предметом изучения данной работы являются максимально негамильтоновые графы. Напомним, что гамильтоновым графом называется

натуральном значении г > 1 верно неравенство Р(г) < С(г). Далее вычислим точное значение величины С(г).
Утверждение 4. Для любого натурального г > 1 верно равенство
С(г) = 2Г~1 +

V _2_ /

Доказательство. При фиксированном г множество неизвестных МНГ-системы - это множество {х,: /ей, 0}. Количество неизвестных равно
2Г -1. Для краткости обозначений неравенства (4) перечислим в другом порядке. Обозначим для к е 2, г через Ок множество упорядоченных наборов из к попарно различных чисел /„ /2,4, принадлежащих множеству /?, таких, что /, < /2. Между множеством всех различных цепочек множеств

= / + 1, 1 = 1,/, 1
соответствие, задаваемое следующим образом: цепочке /, С... /,
соответствует набор 4,...,г,+1 из £>,+|, {г„/2} = /,, /, у =3,/ + 1. Легко убедиться, что такое соответствие взаимно однозначно: для набора /,,..., 4 , удовлетворяющего указанным условиям, положим /, = {/,, /2}, /2 =4 и {/3}, 1}-12 и {/4}, ..., = 1к_2 и {4} ■ Теперь неравенства (4) можно
записать в таком виде:
Г*-1
|5Х.-4м> ^^-Ц4-.4)еАДб2,г, (5)
Отметим, что. неизвестные, участвующие в неравенствах (5), и