Симметричные графы и их автоморфизмы

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

Содержание
Введение
1 О графах, в которых окрестности вершин являются псевдо-геометрическими графами для р£76._ 2(з, !■)

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

1.2 Сильно регулярный случай

1.3 Графы диаметра 3, в которых окрестности вершин изоморфны

1>сх ,2(М)

2 Графы, в которых окрестности вершин — псевдогеометриче-ские графы для 3,3)

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

2.2 Локально псевдо (?<5(3, 3)-графы

3 Графы, в которых окрестности вершин — псевдогеометриче-ские графы для 0(^(3, 5)

3.1 Предварительные результаты
3.2 Локально псевдо 3, 5)-графы
3.3 Случай р =
3.4 Случай р —
4 Автоморфизмы графа с параметрами (245,64,18,16)
4.1 Предварительные результаты
4.2 Автоморфизмы графа с параметрами (245, 64,18,16)
4.3 Автоморфизмы малых порядков

Введение
Для единого представления конечных простых групп перспективным направлением является поиск такого класса конечных геометрий, что каждая конечная простая группа действует флаг-транзитивно на некоторой геометрии и все геометрии этого класса допускают классификацию [1]. Например, класс билдингов Титса характеризует группы лиева типа [15]. Позднее в этом направлении возникли задачи, не связанные с групповым действием. В частности, такой является задача классификации дистанционно регулярных графов [16].
Пусть О — транзитивная группа подстановок на множестве П Если стабилизатор Ор точки р € Г2, имеет г орбит на Я, то говорят, что С имеет подстановочный ранг г. Пусть г = 3 и соответствующие три орбиты — это {р}. А (р). Г (р). Тогда по группе С удается построить сильно регулярный граф Г, множество вершин которого О и две вершины р. д смежны в Г, если Я £ Г (р) [17].
Д. Хигмеп ([17]—[211) развил теорию групп ранга 3. Эти группы являются группами автоморфизмов сильно регулярных графов, причем они действуют трапзитивно как на множествах вершин и ребер, так и на множестве пар различных несмежных вершин. Такие графы являются дистанционно транзитивными графами диаметра 2.
В настоящее время при исследовании графов вовлекаются симметрии все более общего вида.
В работе рассматриваются неориентированные графы без петель и кратных ребер. Если а,Ь - вершины графа Г, то через Да, Ь) обозначается рас-

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

Если 23 = 1, ТО 7з = О И 72 = 12, поэтому Д, содержит 13 вершин степени, не меньшей 12 в г0, противоречие с тем, что степень вершины из Х3 в подграфе [сі] П [с2] больше 4 для подходящих вершин сг, о> из 2?0.
Значит, _г3 = 0, хго = 18, г2 = 30 и = 52. Далее, До — Ю + /?2 и /Д = 30 — 2Д2. Пусть вершина из хГ2 смежна с ф вершинами из 2г. Тогда 52 > 4.
+ 61 + §2 — 38 и <5і + 252 — 34, поэтому 5і — 34 — 252 и й0 = 4 + 62. Значит, число ребер между Х2 и Хо не меньше 240, противоречие с тем, что некоторая вершины из Х0 смежна по крайней мере с 14 вершинами из Х2. Лемма доказана.
До конца работы предполагается, что Г является вполне регулярным графом с параметрами (и,40,12,12), в котором окрестности вершин являются пссвдогеометрическими графами для С(^(3, 3).
Лемма 2.2.8 Выполняются следующие утверждения:
(1) Хо является подграфом из 3-клики;
(2) |Г3(а)| <9 и Г3(а) является кокликой. > . •
Доказательство. Пусть ц = 12. Ввиду леммы 2.2.2 имеем жо+Е (Д^ж* = 76 и хо < 4. Заметим, что число 2-путой в [с] с началом д и концом в [с] П [с?] равно 48.
Допустим, что Хо содержит ребро {сі, е}. Тогда число ребер между [а] П [с] и [с] П Щ — {е} равно 48 и [с] П [сі] — {е) содержит не менее 4 вершин, смежных с 5 вершинами из [а] П [с]. Минимум ж0 + Е (г2 )^і достигается в случае, когда [сі] и [е] содержит 6 вершин из Х5 и 14 вершин из Х4. Но и в этом случае ад + Е Оз1)37? > 36 + 42 + 2, противоречие. Утверждение (1) доказано.
Так как Ф содержит ребро {Ъ, і/}, то [6] и [&'] содержи!' не менее 15 вершин из Ф. поэтому число ребер между Г2(а) и Г3(а) не больше 90-4, но не меньше