Границы для числа вершин в графах и автоморфизмы графов

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

Содержание
Введение

1 Реберно регулярные графы с к > 3?д

1.1 Предварительные результаты

1.2 Графы с хорошими парами

1.3 Графы без хороших пар

2 Автоморфизмы графа с параметрами (64,35,18,20)

2.1 Предварительные результаты

2.2 Автоморфизмы графа с параметрами (64,35,18,20)

3 Автоморфизмы графа с параметрами (396,135,30,54)

3.1 Предварительные результаты

3.2 Автоморфизмы графа с параметрами (396,135,30,54)
3.3 Автоморфизмы малых порядков
3.4 Автоморфизмы частичной геометрии •рСч(5, 26)

Введение
Для единого представления конечных простых групп перспективным направлением является поиск такого класса конечных геометрий, что каждая конечная простая группа действует флаг-транзитивно на некоторой геометрии и все геометрии этого класса допускают классификацию ([20]-[24], [37], [21]). Например, класс билдингов Титса характеризует группы лиева типа [38]. Позднее в этом направлении возникли задачи, не связанные с групповым действием. В частности, такой является задача классификации дистанционно регулярных графов [20].
Пусть С — транзитивная группа подстановок па, множестве П. Если стабилизатор Стр точки р (- Д имеет г орбит на И, то говорят, что С имеет подстановочный ранг г. Пусть г = 3 и соответствующие три орбиты — это {р}, Д(р), Г(р). Тогда по группе в удается построить сильно регулярный граф Г, множество вершин которого О и две вершины р, д смежны в Г, если д е Г» [29].
Д. Хигман ([29]—[35]) развил теорию групп ранга 3. Эти группы являются группами автоморфизмов сильно регулярных графов, причем они действуют транзитивно как на множествах вершин и ребер, так и на множестве пар различных несмежных вершин. Такие графы являются дистанционно транзитивными графами диаметра 2.
В настоящее время при исследовании графов вовлекаются симметрии все более общего вида.
В работе рассматриваются неориентированные графы без петель и кратных ребер. Если а, Ь — вершины графа Г, то через с1(а, Ъ) обозначается рас-

стояние между а и Ъ, а через Гфа) - подграф графа Г, индуцированный множеством вершин, которые находятся на расстоянии г в Г от вершины а.
Подграф Г і (а) называется окрестностью вершины а и обозначается через [а]. Через а1- обозначается подграф, являющийся шаром радиуса ] с центром а.
Граф Г называется регулярным графом степени к, если [а] содержит точно к вершин для любой вершины а из Г.
Граф Г называется реберно регулярным графом, с параметрами (и, к, А), если Г содержит V вершин, является регулярным степени к, и каждое ребро из Г лежит в Л треугольниках.
Граф Г называется вполне регулярным графом с параметрами (и, к. А, //,), если Г реберно регулярен с соответствующими параметрами и подграф [а]П[6] содержит д вершин в случае с1(а, Ъ) — 2. Вполне регулярный граф диаметра 2 называется сильно регулярным графом.
Число вершин в [а] П [Ь] обозначим через А(а, 6), если с1(а,Ь) — 1, а соответствующий подграф назовем А -подграфом.
Если д(а,Ь) = 2, то число вершин в [а] П [Ь] обозначим через д(а, Ь), а соответствующий подграф назовем р-подграфом.
Если вершины и, го находятся на расстоянии г в Г, то через Ьфгц го) (через Сі(и,из)) обозначим число вершин в пересечении Г,+1('«)
(Г;_і(г/,)) с Г('ш). Заметим, что в реберно регулярном графе число Ь(и,ш) не зависит от выбора смежных вершин и, ги и равно Ъ = к — А — І.Граф Г диаметра с? называется дистанционно регулярным, с массивом, пересечений {Ьо, Ьі,..., Ь(і-й сі,..., Сії}, если значения Ь{(и, го) и сг-(н, т) не зависят от выбора вершин и, и) на расстоянии г в Г для любого г = 0,д.
Пусть Т — некоторый класс графов. Г раф Г назовем локально Т графом,

36 • 10, поэтому некоторая вершина и) из Г — 12 смежна по крайней мере с 13 вершинами из 12. Так как /зд = 20, то [го] П12 является кликой. Противоречие с тем, что максимальный порядок клики в Г не больше 8.
Итак. 12 не является сильно регулярным графом с параметрами (?/, к'. 18 — р, 20). Лемма доказана.
Пусть и € Г — 12. Отметим следующее свойство:
(*) если и смежна с и9, то |Г — (гг1 и (нэ)Л"| = 12 и |12| не больше 30; если же V, не смежна с и■9, то [Г — (и-1 и (гг-7)х)| = 12 и |12| не больше 32.
Лемма 2.2.6 Верны неравенства р ф 11 ирф 7.
Доказательство. Пусть р — 11. Тогда любое ребро графа 12 лежит в 7 или в 18 треугольниках из 12, а для несмежных вершин а, Ъ £ 12 подграф 12(а) Г) 12(6) содержит 9 или 20 вершин. Заметим, что вершина из 12 смежна с 11 или 22 вершинами из Г —12 (соответственно с 24 или 13 вершинами из 12). Если степень вершины а в 12 равна 13, то 12(а) — регулярный граф степени 7 на 13 вершинах, противоречие. Поэтому 12 — регулярный граф степени 24, и |Г — 12] = 112, 3 < I по свойству (*). Отсюда |12| = 31, и ввиду свойства (*) имеем а(д) — 0, противоречие с тем, что ввиду целочисленное уДр) число ЗоДэ1) — 93 должно делиться на 8.
Пусть р = 7. Тогда любая (р)-орбита длины 7 является кликой, кокликой, семиугольником или дополнительным графом к семиугольнику, любое ребро графа 12 лежит в 4, 11 или в 18 треугольниках из 12, а для двух несмежных вершин а,Ь £ 12 подграф 12(а) П 12(6) содержит 6, 13 или 20 вершин.
Если |!2| > 16, то по лемме 2.2.6 получим |12| = 16 и аДр) = 0. Поэтому любая орбита длины 7 является кокликой, ГДД П ГгД-7) П ГгД9 ] содержит 4 вершины из , и |12| < 12, противоречие.