Локальные подграфы и автоморфизмы графов

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

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

1 Вполне регулярные графы с д < А' — 2Ьх +

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

1.2 Доказа гельетво теоремы

1.3 Доказательство предложения

1.4 Доказательство теоремы 2 и следствия

2 Вполне регулярные графы е Ъ

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

2.2 Реберно регулярные графы больших степеней с Ьі

2.3 Графы с Ьх = 6, //-подграфы большие или коклпковые

2.4 Графы с Ьх = 6, д-подграфы малые, но не все кокликовые
2.5 Вполне регулярные графы с к = 10, А
3 Автоморфизмы сильно регулярного графа с параметрами (75,32,10,16)
3.1 Предварительные результаты
3.2 Автоморфизмы графа с параметрами (75,32,10,16)
3.3 Автоморфизмы точечного графа частичной геометрии р(?2(4, 7)
Введение
В связи с завершением классификации конечных простых групп возникла задача, единого представления конечных простых групп. Перспективным направлением является поиск такого класса конечных геометрии, что каждая конечная простая группа действует флаг-транзитиино на, некоторой геометрии и все геометрии этого класса допускают классификацию ([]()]-[ 13|,
[29], [28]). Например, класс билдингов Титса характеризует группы лиева типа (см. [32]). Позднее в этом направлении возникли задачи, не связанные с групповым действием, в частности, такой является задача классификации дистанционно регулярных графов (см. [10]).
Пусть О — транзи тивная группа подстановок на множестве О. Если стабилизатор йр точки р £ П. имеет г орбит на, О, то говорят, что С имеет подстановочный ранг г (является группой подстановок ранга г). Пусть г = 3 и соответствующие три орбиты — это {р}, А(р), Г(р). Тогда по группе О удастся построить сильно регулярный граф Г, множество вершин которого О и две вершины р,д смежны в Г, если д £ П(р) (см. [17]).
Д. Хигман (]17|-[23|) развил теорию групп ранга 3. Эти группы являются группами автоморфизмов сильно регулярных графов, причем они действуют транзитивно как на множествах вершин и ребер, так и на множестве пар различных несмежных вершин. Такие графы являются дистанционно транзитивными графами диаметра 2.
В настоящее время при исследовании графов вовлекаются симметрии все более общего вида. Сначала это были условия дистанционной транзитивности и дистанционной регулярности графов, а затем и более общие условия комбинаторной симметричности. Оказалось, что в некоторых случаях комбинаторная симметричность графа влечет его дистанционную транзитивность.
Первые результаты о комбинаторно симметричных графах были получе-

ны в пятидесятых годах. Пусть L(Kn) — реберный граф полного графа Кп на її вершинах пли в других обозначениях треугольный граф Т(п). Этот граф является сильно регулярным графом с параметрами (№,2(п — 2),п — 2,4).
В работах 1959-60 годов Л. Чанг (|16|) и А. Хоффман ([24], [25|) независимо показали, что треугольный граф Т(п) определяется однозначно своими параметрами для всех п, за исключением п = 8. Для случая п — 8 было показано, что кроме треугольного графа Т(8). такие же параметры имеют только три графа, которые были найдены Л. Чангом в 1949 году (см.[15]).
Реберный граф L(Kinnj полного многодольного графа К,п п является ко-реберно регулярным графом с параметрами (тпп,гп + п — 2,2). Граф КІТІіП называют m х п решеткой. При m = п решетчатый граф является сильно регулярным графом с параметрами (п2, 2п — 2, п — 2,2). С. Шрпкхандс в [311 показал, что граф, имеющий параметры п х п решетки является либо решеткой, либо графом Шрикхапде (п = 4).
Результаты Л. Чанга и С. Шрикханде были объединены Дж. Зейделем ((30]), который определил все сильно регулярные графы с наименьшим собственным значением —2. Дж. Зейдсль показал, что кроме треугольных графов Т(п) и решетчатых п х тг-графов, сильно регулярными графами, которые имеют наименьшее собственное значение —2, являются только графы Кпх%, графы Петерсена, Шрикхапде, Клсбша, Шлефли и три графа Чанга.
Для изучения реберно регулярных графов полезным оказался метод хороших пар и его обобщения.
Рассматриваются неориентированные графы без петель и кратных ребер. Если га, Ъ - вершины графа Г, то через d(a, b) обозначается расстояние между а п Ь, а через ГДа) - подграф графа Г, индуцированный множеством вершин, которые находятся на расстоянии і в Г от вершины а.
Подграф ГДга) называется окрестностью вершины а, и обозначается через [а]. Окрестность вершины называется локальным подграфом. Через оД

Лемма 2.1.6 Пусть Г - связный реберно регулярный граф с 'параметрами (и,к,Х) и Ь = 6. Если к > 25. то либо граф Г сильно регулярен, либо Г принадлежит МР(6).
Доказательство. Пусть Г — неполный связный реберно регулярный граф с параметрами (и.к,Х). не являющийся сильно регулярным. Ввиду теоремы
1.4.3 из [Ю| имеем к <С (6| + 3Ь + 2)/2, и и < 1 + к + кЬ/(к — 2Ьу + 1). В случае 5] = 0 имеем к < 27 п V < 1 + к + 6к/{к — 11).
Если к > 25, го ввиду следствия из |6] либо граф Г принадлежит МР{6). либо для графа А = Г выполняется одно из следующих утверждений:
(г) граф А разбивается дополнительными графами для 4-трапов Мебиуса Фь
и / = 12 или 36,
(и) граф А разбивается 3x3 решетками £2і
Граф А на множестве вершин графа А, в котором вершины ?/,, и; смежны, если они смежны в А и |А(н,)П А(ге)| = 0, — дистанционно регулярный граф диаметра 4 либо имеющий массив пересечений {136,135, 6,1:1, 2,135,136} и являющийся антиподальным 4-накрытием спільно регулярного графа с параметрами (2432,136,0, 8), либо имеющий массив пересечений (я', х— 1,4,1:1,2, .т-1,.х} и являющийся антиподальным 3-накрытием сильно регулярного графа с параметрами ((ж + 2)(ж + 3)/6, ад 0, 6).
Так как и < 38, то граф Г принадлежит МГ{6).
Лемма 2.1.7 Пусть Г — реберно регулярный граф с параметрами {у, к, А). Если к > 36ц. то диаметр Г не больше 2.