Реберно регулярные графы и их автоморфизмы

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

1 Реберно регулярные графы с к > ЗЬі — 3
1.1 Предварительные результаты
1.2 Доказательство теоремы
1.3 Вполне регулярные графы с д = к — 2£ц +
1.4 Редукция к графам диаметра
1.5 Графы диаметра
2 О сильно регулярных графах с д = 1 и их автоморфизмах
2.1 Предварительные результаты
2.2 Автоморфизмы графов с параметрами (v,k,3,l)
2.3 Автоморфизмы графа с параметрами (3905,64,3,1)
2.4 Группа автоморфизмов графа с параметрами (3905,64,3,1)
2.5 Автоморфизмы графа с параметрами (9701,100,3,1)
2.6 Группа автоморфизмов графа с параметрами (9701,100,3,1)
3 Об автоморфизмах дистанционно регулярного графа с массивом пересечений {8, 7,5; 1,1,4}
3.1 Предварительные результаты
3.2 Характеры конечных групп и автоморфизмы дистанционно регулярных графов
3.3 Инволютивные автоморфизмы графа с массивом пересечений {8,7,5;1,1,4}
3.4 Граф с массивом пересечений {8,7,5;1,1,4} не является вершинно транзитивным

В связи с завершением классификации конечных простых групп возникла задача единого представления конечных простых групп. Перспективным направлением является поиск такого класса конечных геометрий, что каждая конечная простая группа действует флаг-трапзитнвно на некоторой геометрии и все геометрии этого класса допускают классификацию ([15]-[19], [37], [36]). Например, класс билдингов Титса характеризует группы лиева тина [40]. Позднее в этом направлении возникли задачи, не связанные с групповым действием, в частности, такой является задача классификации дистанционно регулярных графов [15].
Пусть б — транзитивная группа подстановок на множестве П. Если стабилизатор точки р € П, имеет г орбит па П, то говорят, что (7 имеет подстановочный ранг г (является группой подстановок ранга г). Пусть г — 3 и соответствующие три орбиты — это {р}, Д(р), Г(р). Тогда по группе (7 удается построить сильно регулярный граф Г, множество вершин которого П и две вершины р, д смежны в Г, если q £ Г(р) [26].
Д. Хигман ([26]—[32]) развил теорию групп ранга 3. Эти группы являются группами автоморфизмов сильно регулярных графов, причем они действуют транзитивно как на множествах вершин и ребе]), так и на множестве пар различных несмежных вершин. Такие графы являются дистанционно транзитивными графами диаметра 2.
В настоящее время при исследовании графов вовлекаются симметрии все более общего вида. Сначала это были условия дистанционной транзитивности и дистанционной регулярности графов, а затем и более общие условия комбинаторной симметричности. Оказалось, что в некоторых случаях комбинаторная симметрия графа влечет его дистанционную транзитивность.
Первые результаты о комбинаторно симметричных графах были получо-

ны б пятидесятых годах. Пусть L(Kn) — реберный граф полного графа Кп на га вершинах или в других обозначениях треугольный граф Т(п). Этот граф является сильно регулярным графом с параметрами (Q), 2(га — 2),га — 2,4). В работах 1959-60 годов Л. Чанг [23] и А. Хоффман ([33], [34]) независимо показали, что треугольный граф Т(п) определяется однозначно своими параметрами для всех га, за исключением га = 8. Для случая п — 8 было показано, что кроме треугольного графа Т(8), такие же параметры имеют только три графа, которые были найдены JI. Чангом в 1949 году [22].
Реберный граф L(Km Результаты Л. Чанга, С. Шрикханде и А. Хоффмана [35] были объединены Дж. Зейдслем [38], который определил все сильно регулярные графы с наименьшим собственным значением —2. Дж. Зсйдель показал, что кроме треугольных графов Т(п) и решетчатых га х га-графов, сильно регулярными графами, жоторые имеют наименьшее собственное значение —2, являются только графы КпХ2, графы Петерсена, Шрикханде, Клебша, Шлсфли и три графа Чанга.
В работе рассматриваются неориентированные графы без петель и кратных ребер. Если а, b - вершины графа Г, то через d(a,b) обозначается расстояние между а и 6, а через Г* (а) - подграф графа Г, индуцированный множеством вершин, которые находятся на расстоянии г в Г от вершины а.
Подграф ГДа) называется окрестностью вершины а и обозначается через [а]. Через а1 обозначается подграф, являющийся шаром радиуса 1 с центром а.

содержит единственную вершину д из [и] и каждая вершина из [с£]П[и] смежна с £ или с е.
Пусть [с/] П [у] П [г] содержит отличную от £, е вершину /. Тогда / смежна с 91,02, |М П [/]| = Ъ- 2=1, противоречие.
Таким образом, [с?] П [у] П [г] = {£,е} и £>1 = 4. Допустим, что вершины <71, <72 несмежны. Тогда степень щ в графе [с?] П [у] равна 61 — 3 и [дч] П [<72] содержит вершину г из [с£] П [и]. Без ограничения общности, г смежна с £ и [с?] Г) [г] содержит и, £,<71, <72 и вершину из [и] П [щ], противоречие. Значит, вершины <71, <72 смежны. Если [<71] П [<72] содержит вершину г из [ Пусть {г, й} = [<£] П [«] П [£], /, к — смежные с £ вершины из ([у] П [2]) — [<£], [г] — у1 соответственно. Если г смежна с <71, то [<£] содержит ЛДз-нодграф {е, <72, г; £, <71, г'}. Тогда степень г в графе [£] П [и] равна 2 и [с/] П [г] содержит и, £, я, <71 и вершину г', противоречие. Значит, {г, я} = [ Пусть о, к — смежные с е вершины из ([т/]П[Д) — [(£], [г]-;;/1 соответственно. Как и выше, к смежна сои р(о, и) = 3. Отсюда найдется вор шип ар из [z}-yL, несмежная с вершинами из [у] П [г]. Противоречие с тем, что тогда вершина 2 изолирована в [р] П [у].
Лемма 1.5.9 Пусть вершина д из [«] П ^(р) смс-жпа с двумя вершинами 91,92 из Ы — 2±- Тогда каждая вершина из [