Локальное строение и автоморфизмы реберно регулярных графов

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

1 Хорошие пары в реберно регулярных графах

2 Об автоморфизмах сильно регулярных графов с

А = 0 и д = 2

2.1 Об автоморфизмах графа с параметрами (352,26,0,2)

2.2 Об автоморфизмах графа с параметрами (704,37,0,2)

3 Об автоморфизмах графа с параметрами

(1600,205,0,30)

Литература

Мы рассматриваем неориентированные графы без петель и кратных ребер. Если а,Ъ — вершины графа Г, то через б(а, 6) обозначим расстояние между а и Ь, а через Г;(а) — подграф, индуцированный Г на множестве всех вершин графа Г, которые находятся на расстоянии і от вершины а. Подграф Г і (а) будем называть окрестностью вершины а и обозначать через [о]. Через а1 обозначим подграф, индуцированный {а} и [а].
Степенью вершины называется число вершин в ее окрестности. Граф Г называется регулярным степени к, если степень любой вершины а графа Г равна к. Число вершин в [а] П [Ь] обозначим через А (а, Ь) (р(а,Ь)), если с1(а,Ь) — 1 (с1(а,Ь) = 2), а соответствующий подграф назовем (р-) А-подграфом. Граф Г назовем реберно регулярным с параметрами (и, к, А), если он содержит V вершин, регулярен степени к, и каждое его ребро аЬ лежит в А треугольниках. Граф Г — вполне регулярный граф с параметрами (и, к, А, р), если он реберно регулярен с соответствующими параметрами и [а]П [6] содержит р вершин для любых двух вершин а, Ь, находящихся на расстоянии 2 в Г. Вполне регулярный граф называется сильно регулярным графом, если он имеет диаметр 2.
Через Кть...,т„ обозначим полный п-дольный граф, с долями порядков ті, ..., тп. Если т = ... = тп = т, то соответствующий граф обозначается через Кпхт. Треугольным графом Т(т) называется граф с множеством неупорядоченных пар из Л' в качестве вершин, |Х| = т и пары {а, 6}, {с, (Ї) смежны тогда и только тогда, когда они имеют общий элемент. Граф на множестве вершин X X У называется т X п решеткой, если Х — т, |У| = п и вершины (хі,уі), (х2,У2) смежны тогда и только тогда, когда ад = ад или у ~ а/2• Если вершины и, ги находятся на расстоянии г в Г, то через Ьі(и,и>) (чрез Сі(и,Ш)) обозначим ЧИСЛО вершин В пересечении Гі+і(и) (в пересечении Г*_і(и)) с [го]. Заметим, что в реберно регулярном графе с параметрами
(у, к, Л) значение {ц[и, ю) не зависит от выбора ребра {и, ш} и равно к — Л— 1.
В связи с завершением классификации конечных простых групп возникла задача единого представления конечных простых групп. Перспективным направлением является поиск такого класса конечных геометрий, что каждая конечная простая группа действует флаг-транзитивно на некоторой геометрии и все геометрии этого класса допускают классификацию [15—18, 20, 31, 32]. Например, класс билдингов Титса характеризует группы Лиевского типа [36]. Позднее в этом направлении возникли задачи, не связанные с групповым действием, в частности, такой является задача классификации дистанционно регулярных графов [1,15].
Пусть О — транзитивная группа подстановок на множестве П. Если подгруппа группы С, состоящая из всех подстановок, фиксирующих точку р £ О, имеет г орбит, то говорят, что (3 является группой ранга г. Пусть г — 3 и соответствующие 3 орбиты — это {р}, Д (р), Г(р). Тогда по группе С удается построить сильно регулярный граф Г, множество вершин которого — П и две вершины р, д смежны в Г, если р £ Д(д) [14].
Д.Хигмэн [24 — 30] развил теорию групп ранга 3. Эти группы являются группами автоморфизмов сильно регулярных графов, причем они действуют транзитивно как на множестве вершин и ребер, так и на множестве пар различных несмежных вершин. Такие графы являются дистанционно транзитивными графами диаметра 2.
Граф Г диаметра с1 называется дистанционно транзитивным, если для любого г £ {0 <£} и для любых вершин и, у, х, у, таких что с1(и, у) = й(х, у) = г, существует автоморфизм д графа Г : (и, у)9 = (х,у). Дистанционно транзитивные графы диаметра 2 (графы ранга 3) сыграли важную роль в классификации конечных простых групп. Около половины спорадических групп были построены как группы автоморфизмов графов ранга 3 [31].
Если вершины и, и) находятся на расстоянии г в Г, то через ^(н,гг) (че-

1 1 1 1 1 ( 1 1 1
р = 37 -7 5 ,с? = 296 -56 8/3
^ 666 6 -6 , ^ 407 57 -11/3 )
Поэтому значение характера, полученного при проектировании на подпространство размерности 296 равно
/ % 5ог0 (5) - «1Ы +
XIЫ = ^2 '
Лемма 2.3.1 Пусть X; = Х;(Д), ад = 0 и х$ ф 0. Тогда для любой вершины и £ Хо имеем |[гг] ПХ2| = |Д|.
Доказательство. Число 2-путей с началом и, концом в Д и средней вершиной в Х2 равно 21Д |. Так как вершина из [и] П Х2 лежит в двух таких путях, то |[и] П Х2| = 21Д|/2 = |Д|.
Предложение 2.5. Пусть Г — сильно регулярный граф с параметрами (704,37,0,2), имеющий ипволютивный автоморфизм 2. Тогда для Д = ПхД, |Д| ~ф- 0, выполняется одно из следующих утверждений:
(1) Д является графом степени 1 на 20 вершинах;
(2) Д является графом степени 5 на 32 вершинах;
(3) Д является графом степени 7 на 44 вершинах.
Доказательство. Ввиду леммы 2.1.2 Д является вполне регулярным графом с параметрами (5, /3,0,2), где 6 = |Д|. Так как к = 37, то /3 нечетно. Число ребер между Д и Г — Д равно <5(37 — /3). По лемме 2.1.2, указанное число не больше 2(704 — 5).
Пусть Хг — множество вершин из Г — Д, смежных точно с г вершинами из Д, Хг = |Хф Тогда хо + ад + тд = 704 — <5 и х + 2х2 = <5(37 — /3). По лемме
2.1.1 /3 < 7.
Если /3 = 1, то по лемме 2.1.2 граф Д является объединением 10 изолированных ребер. Тогда XI(^) — (132 — <Т1(£))/12, и аД) кратно 12. В этом