Содержание
Введение 3
1 Реберно регулярные графы с к = 36] — 2 14
1.1 Предварительные результаты....................................14
1.2 Хорошие пары вершин в графах с к = 3&і — 2....................19
1.3 Оценка для числа вершин в графах с к = 3Ь[ — 2 24
2 Автоморфизмы графов с параметрами (76,35. 18,14) 33
2.1 Предварительные результаты....................................34
2.2 Автоморфизмы графа с параметрами (76,35,18,14)............... 38
3 Автоморфизмы графа с параметрами (243,60,9,21) 51
3.1 Предварительные результаты....................................53
3.2 Автоморфизмы графа с параметрами (243,66,9,21)............... 56
3.3 Автоморфизмы малых порядков...................................65
3.4 Реберно симметричный случай...................................80
2
Введение
Для единого представления конечных простых групп перспективным направлением является поиск такого класса конечных геометрий, что каждая конечная простая группа действует флаг-транзитивно на некоторой геометрии и вес геометрии этого класса допускают классификацию (|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). Граф Ь{К1ПуП) называют т х гс-решеткой. При т — п решетчатый граф является сильно регулярным графом с параметрами (п2}2п — 2,п — 2,2). С. Шрикхамде в [38) показал, что граф, имеющий параметры п х п решетки является либо решеткой, либо графом Шрикханде (п = 4).
3
Результаты Л. Чанга, С. Шрикханде и А. Хоффмана (35] были объединены Дж. Зейделем (37|, который определил псе сильно регулярные графы с наименьшим собственным значением —2. Дж. Зейдель показал, что кроме треугольных графов Т(п) и решетчатых и х гі-графов, сильно регулярными графами, которые имеют наименьшее собственное значение -2, являются только графы Кпх2, графы Петерсена, Шрикханде, Клебша, Шлсфли и три графа Чанга.
В работе рассматриваются неориентированные графы без петель и кратных ребер. Если а, Ь - вершины графа Г, то через с1{а,Ь) обозначается расстояние между а и 6, а через ГДа) - подграф графа Г, индуцированный множеством вершин, которые находятся на расстоянии г в Г от вершины а.
Подграф Г] (а) называется окрестностью вершины а и обозначается через [а]. Через а1 обозначается подграф, являющийся шаром радиуса 1 с центром а.
Граф Г называется регулярным графом степени к, если [а] содержит точно к вершин для любой вершины о, из Г.
Граф Г называется реберно регулярным графом с параметрами (г»,/с, Л), если Г содержит и вершин, является регулярным степени к, и каждое ребро из Г лежит в Л треугольниках.
Граф Г называется вполне регулярным графом с параметрами (?;, к, Л,//), если Г реберно регулярен с соответствующими параметрами и подграф [а]П[/>] содержит /і вершин в случае сі(а. Ь) — 2. Вполне регулярный граф диаметра 2 называется сильно регулярным графом.
Число вершин в [а] П [6] обозначим через Л(а,6), если гі(а, Ь) = 1, а соответствующий подграф назовем Х-подграфюм.
Если <Да, 6) = 2, то число вершин в [а] П [6] обозначим через /Да, 6), а
4
соответствующий подграф назовем р-подграфом.
Если вершины иуш находятся на расстоянии і в Г, то через Ьфи./ш) (через с\(и, ги)) обозначим число вершин в пересечении Г,+і(и)
(Гг_і(?і)) с Г(ги). Заметим, что в реберно регулярном графе число 6](г/.,ги) не зависит от выбора смежных вершин и,ги и равно 1ц = к — X — І.Граф Г диаметра (I называется дистанционно регулярным с массивом пересечений {6(), 61}..., Сі,, сн}, если значения 6Дгх, ги) и а(и, ги) не зависят от выбора вершин и, ю на расстоянии г в Г для любого г = 0, ....(1.
Пусть Т — некоторый класс графов. Граф Г назовем локально Т графом, если [а] лежит в Т для любой вершины а графа Г. Если при этом класс Т состоит из графов, изоморфных некоторому графу Д, то граф Г назовем локально А-графом.
Пусть Г — реберно регулярный граф с параметрами (у. к. Л) и 61 = А:—Л — 1. Пара вершин и, и называется (почти) хорошей, если д{и, ш) = 2 и р(и, ги) равно к — 2Ь\ 4- 1 (равно к — 2Ь\ 4- 2). Тройка вершин (и,ги,г) называется (почти) хорошей, если ги, г Є Г2(?і) и //(гг, ги) -1- //(г/, г) не больше 2к — 4Ь\ 4- 3 (равно 2к - 46] 4- 4).
Основанием для развития метода хороших нар стало следующее наблюдение. Пусть Г — реберно регулярный граф с параметрами (и, к, Л) и &і = к — X— 1. Если вершины иуш находятся на расстоянии 2 в Г, то выполняются следующие утверждения:
(1) степень любой вершиш,і в //-подграфе из Г не меньше к — 2/д;
(2) вершина (I имеет степень а в графе [г/] П [ги], тогда и только тогда, когда [й] содержит точно ос — (к — 2Ь\) вершин вне и '- и ги1;
(3) если р(и,ги) = к — 2Ь\ 4- 1, то подграф (?/] П [ги] является кликой и [Ф\ С и1- иги-1 для любой вершины (І Є [а] П [ги];
(4) если Г — (uL U ад *•) содержит единственную вершину ТО n('U,z) = n(w,z).
A.A. Махнев [1| получил следующее свойство хороших троек:
Пусть Г — реберно регулярный граф, содержащий хорошую тройку (и, w, z) и S == |[?i] П [w] П[г]\. Тогда выполняются следующие утверждения:
(1) если fi(utw) = ß(Uj z) = к — 2Ь\ + 1, то 6 = 0 в случае, когда вершины w, z не смежны и ö < 1 в случае, когда вершины w, z смежны;
(2) если p(u,w) + n{u,w) = 2к - Ab\ -f 3, то ö < 1.
С помощью этих результатов получается новое доказательство классификации графов Тервиллигера без 3-лап. Получение аналогичных оценок для почти хороших троек потребовало значительных усилий (см. [2] - [5]). В |6|) была доказана
Теорема А. Пусть Г — связный реберно регулярный граф с параметрами (v,k, Л), к = 36] +7 и 7 > —2. Если (u.wfz) — почти хорошая тройка и Д = [гл] П [tc] П [z\ — непустой граф), то вершины w, z смежны и выполняется одно из следующих утверждений:
(1) |Д| < 2 < -1;
(2) подграф А является 3-кликой, Ь\ =6.к = 16 и v — 31;
(3) подграф А является 3-кликой, bу = 3 и Г — граф Клебша;
(4) подграф А является 4-кликой, bi = 5 и Г — граф Шлефли.
С помощью теоремы А были найдены новые верхние границы для числа вершин реберно регулярных графов (в случае к > ЗЬ\ Исаковой М.М., в случае к — 3b\ - 1 Чуксиной Н.В. и в случае к = 36] — 2 Токбаевой A.A.).
Цель диссертации. Целью данной работы является решение следующих задач:
1. Найти новіле верхние границы для числа вершин реберно регулярных графов с к = Збі — 2.
2. Найти возможные порядки и подграфы неподвижных точек сильно регулярного графа с параметрами (76,35,18,14).
3. Найти возможные автоморфизмы сильно регулярного графа с параметрами (243,66,9,21).
Методы исследования. Основными методами исследования являются методы теории конечных групп, теории характеров, теоретико-графовые методы и методы локального анализа комбинаторно симметричных графов.
Научная новизна. Основные результаты, полученные в работе, являются новыми. Выделим из них следущие.
1. Найдены новые верхние оценки для числа вершин реберно регулярных графов с к = З&і — 2.
2. Определены возможные порядки элементов группы С автоморфизмов сильно регулярного графа с параметрами (76,35,18,14), в частности, установлено, что тг(С) С {2,3,5, 7,19}.
3. Найдены возможные порядки и подграфы неподвижных точек автоморфизмов сильно регулярного графа Г с параметрами (243,66,9,21). Доказано, что граф Г не является реберно симметричным.
Теоретическая и практическая ценность. Работа носит теоретический характер. Результаты продолжют изучение реберно регулярных графов и их автоморфизмов. Результаты и методы диссертации могут быть использованы для изучения графов и конечных геометрий подобного тина.
Апробация работы. Основные результаты работы докладывались на:
Международной алгебраической конференции, посвященной 80-летию со
7
- Київ+380960830922