Графы Тервиллигера в теории дистанционно регулярных графов

• Автор: Гаврилюк, Александр Львович
• Шифр специальности: 01.01.06
• Научная степень: Докторская
• Год защиты: 2012
• Место защиты: Екатеринбург
• Количество страниц: 177 с. : ил.

Оглавление
Введение

Определения и основные обозначения

Обозначения

Определения свойств регулярности графов

Определения семейств графов

Мотивация работы

Общая характеристика работы

1 Характеризации графов Тервиллигера

1.1 Вспомогательные результаты

1.2 Проблема регулярности в регулярных графах Тервиллигера

1.3 Графы Тервиллигера с д ^
1.3.1 Графы Тервиллигера с д =
1.3.2 Сильно регулярные графы Тервиллигера с д =
1.3.3 Графы Тервиллигера с д =
1.4 Графы Тервиллигера, в которых окрестность некоторой вершины изоморфна графу Петерсена
1.5 Графы Тервиллигера с д =
1.6 Неравенство Кулена - Пака и графы Тервиллигера
1.7 Граница для коклик в д-подграфах
2 Локальные характеризации некоторых графов
2.1 Вспомогательные результаты
2.2 Дистанционно регулярные локально 5 графы
2.3 Локально НоБг графы
2.3.1 Предварительное обсуждение
2.3.2 Графы диаметра не больше
2.3.3 Ограничение диаметра
2.4 Возможные автоморфизмы дистанционно регулярных локально Новг графов

2.4.1 Предварительное обсуждение
2.4.2 Массив пересечений {50,42,1,1, 2,50}
2.4.3 Массив пересечений {50,42, 9,1, 2,42}
2.4.4 Замечание о рациональных характерах в методе Хигмена
2.5 Графы, в которых окрестность каждой вершины изоморфна
графу Гевиртца
2.5.1 Предварительное обсуждение
2.5.2 Редукция к графам диаметра, большего
2.5.3 Графы большого диаметра
3 Нереализуемость некоторых массивов пересечений
3.1 Вспомогательные результаты
3.2 Массивы пересечений {55,36,11; 1,4,45} и
{56,36,9; 1,3, 48}
3.3 Массив пересечений {45, 30,7; 1,2,27}
3.3.1 Предварительное обсуждение
3.3.2 Верно неравенство |Lo| <
3.3.3 Верно неравенство jLo| <
3.3.4 Верно неравенство |Lo| Ф
3.4 Массивы пересечений {52,35,16; 1,4, 28} и
{69,48, 24; 1,4, 46}
4 Графы Райзера и геодезические графы диаметра 2
4.1 Графы Райзера
4.2 Бирегулярные геодезические графы диаметра
4.2.1 Вспомогательные результаты
4.2.2 Случай нерегулярного графа В
4.2.3 Случай регулярного графа В
4.2.4 Некоторые результаты о несуществовании графов

Введение
В диссертации проводится систематическое изучение класса графов Тервил-лигера и связанных с ним вопросов в теории дистанционно регулярных графов. Разработаны методы изучения локального строения графов Тервилли-гера, дистанционно регулярных графов с заданными окрестностями вершин, предложены доказательства несуществования дистанционно регулярных графов с некоторыми допустимыми массивами пересечений.
В этой главе приведены основные определения и обозначения, объясняется мотивация работы.
Определения и основные обозначения
В этом разделе собраны общие для всех глав обозначения и определения графов и их свойств. Наша терминология и обозначения в основном стандартны, см. монографию [1].
Обозначения
В работе рассматриваются только неориентированные графы без петель и кратных ребер. Пусть Г является таким графом. Для подмножества X вершин графа Г мы будем также через X обозначать подграф, индуцированный в Г множеством X. Соответственно число вершин в графе X обозначается через Х. Далее термин подграф всегда будет означать подграф, индуцированный множеством вершин.
Для пары вершин л, у £ Г таких, что в Г существует путь, соединяющий х и у, через ё(х, у) обозначается расстояние между х и у, т.е. длина кратчайшего пути между этими вершинами. Диаметром б(Г) графа Г называется максимальное встречающееся расстояние между его вершинами. Вершины х,у с д(х,у) = 1, т.е. соединенные ребром, называются смежным,и; смежность вершин также обозначается через х ~ у.

1.2 Проблема регулярности в регулярных графах Тер-виллигера
Напомним, что для вершин х,у графа Г с сІ(х,г/) = 2 через Ь2{х,у) обозначается число |[г/]ПГ3(ж)|, а для вершины х графа Тервиллигера Г через Ьх мы обозначаем порядок ядра вершины х, т.е. Ьх = |[ж]х|.
В [1, Предложение 1.16.1] доказана следующая исправленная версия утверждения Тервиллигера из работы [7].
Предложение 1.1 Пусть Г — связный регулярный граф Тервиллигера, и предположим, что Ь2(х,у) = Ь2(у,х) для всякой пары вершин х,у, находящихся на расстоянии 2 в Г. Тогда для любой вершины г £ Г подграф является регулярным графом Тервиллигера с параметром д(Д2) = м(Г) ~
1ВДХ|.
В статье [7] Тервиллигер не предполагал условия 62 (ж, у) = 62(2/1 х)> 110 без этого предположения его доказательство было некорректным. В теореме 1.1, доказываемой в этом разделе, это ограничение снято.
Лемма 1.2.1 Пусть Г — граф Тервиллигера с пустым графом Г1. Тогда для любых вершин и, га графа Г с с1(гг, ад) = 2 и степенями ки и кт> соответственно, получим
ки-Ъ2(у),и) - |([гг] П [го] и {и})11 = ки1 - Ъ2(и,ш) - |([гг] П [го] и {го})х|, (1.1)
и следующие утверждения равносильны:
(1) ки - 62(го, и) = ки,- Ъ2{и, го);
(2) для произвольного непустого подмножества X из [гг] П [го] степени вершин и, и: в графе X Xі равны;
(3) |(М П [го] и {гг})х| = |(М П [го] и {го})х|.
Доказательство. Для произвольного подмножества Е С [гг] П [го] определим подграфы
Еи = {х £ [гг] [го] | {гг, го, х}х = Е},
Ет = {і£ [го] [гг] | {гг,го,х}х = Е}.
Тогда для у Є {гг, го} получим ку — /г + |Еу.
Пусть 0 ф Е С [гг] П [го]. Если х Є Еи, то [ж] П [го] содержит Е и у — |і?|
вершин из [го] [гг], попадающих в В самом деле, для у Є [ж] П [го] [гг]
имеем Е С [г/], далее, [гг] П [у является кликой, поэтому [гг] П [го] П [у] С Е и