Некоторые алгебраические аспекты теории конечных графов

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

Оглавление
Введение
0.1 История вопроса и основные результаты
0.1.1 Графы с наименьшим собственным значением
0.1.2 Графы без 3-лап
0.1.3 Графы и транзитивные группы подстановок
0.1.4 Графы без 3-лап и теория доминирования
1 Характеризация треугольных и решетчатых графов
1.1 Графы без 3-лап с р -подграфами большого радиуса
1.2 Кореберно-регулярные графы без 3-лап
2 Графы без 3-лап с равномощными р-подграфами
2.1 р-регулярные графы без 3-лап
2.1.1 Редукция р-регулярных графов без 3-лап
2.1.2 Вполне регулярные графы Тервиллигера без 3-лап
2.1.3 Редукция регулярных графов Тервиллигера без 3-лап

2.2 Нерегулярные графы без 3-лап с равномощными
ц -подграфами
2.2.1 Некоторые общие свойства графов без 3-лап
2.2.2 Сильные пары в графах без 3-лап
2.2.3 Свойства графов без 3-лап с равномощными
р -подграфами
2.2.4 Исключительные тройки в графах без 3-лап
с равномощными р-подграфами
2.2.5 Особые тройки в графах без 3-лап с равномощными р -подграфами
3 Характеризация некоторых дистанционно-регулярных графов
3.1 Характеризация графов Хэмминга
3.1.1 О регулярных отделимых графах
3.1.2 Отделимые реберно-регулярные графы, содержащие 3-лапы
3.2 Графы без корон с регулярными р-подграфами
3.2.1 Условие редуцированности в графах без 3-
лап с регулярными р-подграфами
3.2.2 Локальная теорема
3.2.3 Характеризация графов Грассмана и Джонсона
3.3 Сильно регулярные графы с расщепляемыми окрестностями вершин
4 Теория доминирования и неприводимости

4.1 Доминирование и неприводимость в графах с блоками без 3-лап
4.1.1 Предварительные леммы
4.1.2 Доказательство теоремы
5 Основные определения и обозначения
5.1 Граф и его подграфы
5.2 Регулярные графы
5.3 Расширения графов
5.4 Реберные графы
5.5 Граф Шлефли
5.6 Граф системы корней
5.7 Обобщенно регулярные графы
5.8 Некоторые примеры дистанционно-регулярных графов
5.9 Редукция графа
5.10 Доминирование и неприводимость
5.11 Блоки и блок-графы

фами Т(п), при п > 6, то по теореме Холла-Шульта [23] граф Г является треугольным графом Т(п + 2), при п > 6, либо п — 6 и Г является графом Конвея-Смита на 63 вершинах или графом Доро на 65 вершинах. Первые графы противоречат выбору Г. Если Г является графом Конвея-Смита или графом Доро, то Г не удовлетворяет условию теоремы.
Пусть все антиокрестности в графе Г будут графами Шле-фли. Так как граф Шлефли является дополнительным к точечному графу обобщенного четырехугольника С<3(2,4), то дополнительный к Г граф будет локально С(3(2,4) -графом. По теореме Бьюкенхаута-Хубаута [9] (см. также [11]) граф Г является дистанционно-регулярным графом Госсета £У(1) на 56 вершинах с массивом пересечений {27,10,1; 1,10,27} или сильно регулярным графом с параметрами (64,27,10,12). Но тогда Г не удовлетворяют условию теоремы. Лемма доказана.
Лемма 1.1.10 Если а,Ъ,с — 3-коклика из графа Г, а й,е — несмежные вершины из [а] П [Ь], то в Г нет вершин смежных с вершинами а, <7 и е и не смежных с вершиной Ь.
Доказательство. Пусть х — вершина из Г, смежная с вершинами а,фе и не смежная с вершиной Ь, где вершины а, 6, с, Де выбраны как указано в условии леммы. По лемме 1.1.5 [х] С сД и ех , а о1 и Ъх = и ех. Отсюда [х] П [Ъ]' С [а] П [Ь]г и по лемме 1.1.7, примененной к р -замкнутому подграфу [5]' [х]П[Ъ}' = [а]П[Ь]'.