Почти хорошие тройки вершин в графах и автоморфизмы графов

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

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

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

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

1.2 Хорошие пары вершин в графах с к = 3?ц —

1.3 Оценка для числа вершин в графах с к — З&і

2 Автоморфизмы графов с параметрами (76, 35.18,14)

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

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

3 Автоморфизмы графа с параметрами (243,66,9,21)

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

3.2 Автоморфизмы графа с параметрами (243,66,9,21)
3.3 Автоморфизмы малых порядков
3.4 Реберно симметричный случай

Введение
Для единого представления конечных простых групп перспективным направлением является поиск такого класса конечных геометрий, что каждая конечная простая группа действует флаг-транзитивно на некоторой геометрии и все геометрии этого класса допускают классификацию ([23], [24], [36], [21]). Например, класс билдингов Титса характеризует группы лиева типа [40]. Позднее в этом направлении возникли задачи, не связанные с групповым действием. В частности, такой является задача классификации дистанционно регулярных графов [20].
Первые результаты о комбинаторно симметричных графах были получены в пятидесятых годах XX века. Пусть Ь{Кп) — реберный граф полного графа Кп на п вершинах или в других обозначениях треугольный граф Т(п). Этот граф является сильно регулярным графом с параметрами (п(п — 1)/2, 2(п —
2),п — 2,4). В работах 1959-60 годов Л. Чанг [28] и А. Хоффман ([33], [34]) независимо показали, что треугольный граф Т(п) определяется однозначно своими параметрами для всех п, за исключением п = 8. Для случая п = 8 было показано, что кроме треугольного графа Т(8), такие же параметры имеют только три графа, которые были найдены Л. Чангом в 1949 году [27].
Реберный граф Ь(Кт)П) полного многодолыюго графа Кт<п является ко-реберно регулярным графом с параметрами (тп, т + п — 2,2). Граф Ь(Кт<п) называют т х п-решеткой. При т = п решетчатый граф является сильно регулярным графом с параметрами (п2,2п — 2, п — 2, 2). С. Шрикханде в [38] показал, что граф, имеющий параметры п х п решетки является либо решеткой, либо графом Шрикханде (н = 4).

Результаты Л. Чанга, С. Шрикханде и А. Хоффмана [35] были объединены Дж. Зейделем [37], который определил все сильно регулярные графы с наименьшим собственным значением —2. Дж. Зейдель показал, что кроме треугольных графов Т(п) и решетчатых п х п-графов, сильно регулярными графами, которые имеют наименьшее собственное значение —2, являются только графы КпХ2, графы Петерсена, Шрикханде, Клебша, Шлефли и три графа Чанга.
В работе рассматриваются неориентированные графы без петель и кратных ребер. Если а,Ь - вершины графа Г, то через б(а, Ъ) обозначается расстояние между а и Ь, а через ГДа) - подграф графа Г, индуцированный множеством вершин, которые находятся на расстоянии г в Г от вершины а.
Подграф Г і (а) называется окрестностью вершины а и обозначается через [о]. Через а1 обозначается подграф, являющийся шаром радиуса 1 с центром а.
Граф Г называется регулярным графом степени к, если [а] содержит точно к вершин для любой вершины а из Г.
Граф Г называется реберно регулярным графом с параметрами (и,к,Х), если Г содержит и вершин, является регулярным степени к, и каждое ребро из Г лежит в А треугольниках.
Граф Г называется вполне регулярным графом с параметрами (?;, к, А, р), если Г реберно регулярен с соответствующими параметрами и подграф [а] П [6] содержит р вершин в случае с1(а. Ь) = 2. Вполне регулярный граф диаметра 2 называется сильно регулярным графом.
Число вершин в [а] П [6] обозначим через А(а,Ь), если фа, 6) — 1, а соответствующий подграф назовем А -подграфом.
Если Да, 6) = 2, то число вершин в [а] П [Ь] обозначим через р(а,Ь), а

Лемма 2.1.2 параметры (v, к, А, у). Тогда либо к = 2/л, Л = у — 1 (так называемый половинный случай), либо неглавные собственные значения гагат, —т графа Г — целые числа, где га2 = (А — у)2 + 4(к — у), п — А + у = 2т
к(т — 1)(А; + т)
и кратность п — т равна-----------------------. Далее, если т — целое число,

большее 1, то т — 1 делитi к — А — 1 и
Доказательство. Это лемма 3.1 из [13].
Доказательство теоремы опирается на метод Хигмена работы с автоморфизмами сильно регулярного графа, представленный в третьей главе монографии Камерона [25]. При этом графу Г отвечает симметричная схема отношений (X, {і?0, /Ї2}), гДе X ~ множество вершин графа, /?о — отношение
равенства на X, Ні — отношение смежности в Г, і?2 — отношение смежности в дополнительном графе Г. Если Р и $ — первая и вторая матрицы собственных значений схемы, то
р<2 = £)Р = и1. Здесь V — число вершин, к, г, в — собственные значения графа Г кратностей 1, /, у—/—1 соответственно (указанные кратности образуют первый столбец матрицы ()).
Подстановочное представление группы С = Аи1,(Г) на вершинах графа Г обычным образом дает матричное представление гр группы С в СЬ(и, С). Пространство С" является ортогональной прямой суммой собственных 'ф(С)-инвариантных подпространств Но, ¥, \^2 матрицы смежности графа Г. Пусть
к-Л- 1 т — 1.
( 1 1 1

у И — /с — 1 —г — 1 — S — 1 !