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

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

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

1.1 О реберно регулярных графах с к > 3Ъх

1.2 О хороших парах в графах с к > З&і — 2

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

2.1 Введение

2.2 Об автоморфизмах графа с параметрами (99,14,1,2)

2.3 Об автоморфизмах графа с параметрами (243,22,1,2)

3 Об автоморфизмах графа с параметрами (115,18,1,3)

Литература

Мы рассматриваем неориентированные графы без петель и кратных ребер. Если а, Ь — вершины графа Г, то через (1(а, Ь) обозначим расстояние между а и Ь, а через Г* (а) — подграф, индуцированный Г на множестве всех вершин графа Г, которые находятся на расстоянии і от вершины а. Подграф Г^а) будем называть окрестностью вершины а и обозначать через [а]. Через ах обозначим подграф, индуцированный {а} и [а].
Степенью вершины называется число вершин в ее окрестности. Граф Г называется регулярным степени к, если степень любой вершины а графа Г равна к. Граф Г назовем реберно регулярным с параметрами (и, к, А), если он содержит V вершин, регулярен степени к, и каждое его ребро аЪ лежит в А треугольниках. Граф Г — вполне регулярный граф с параметрами (и, к, А, р), если он реберно регулярен с соответствующими параметрами и [а] П [Ь] содержит р вершин для любых двух вершин а, Ь, находящихся на расстоянии 2 в Г. Вполне регулярный граф называется сильно регулярным графом, если он имеет диаметр 2.
В связи с завершением классификации конечных простых групп возникла задача единого представления конечных простых групп. Перспективным направлением является поиск такого класса конечных геометрий, что каждая конечная простая группа действует флаг-транзитивпо на некоторой геометрии и все геометрии этого класса допускают классификацию [15—18, 20, 30, 31]. Например, класс билдингов Титса характеризует группы Лиевского типа [32]. Позднее в этом направлении возникли задачи, не связанные с групповым действием, в частности, такой является задача классификации дистанционно регулярных графов [14].
Пусть Є — транзитивная группа подстановок на множестве П. Если подгруппа Ср группы С?, состоящая из всех подстановок, фиксирующих точку р Є П, имеет г орбит, то говорят, что Є является группой ранга г. Пусть

г = 3 и соответствующие 3 орбиты — это {р}, Д(р),Г(р). Тогда по группе С? удается построить сильно регулярный граф Г, множество вершин которого — £1 и две вершины р, д смежны в Г, если р Є Д(д) [13].
Д.Хигмэн [21 — 27] развил теорию групп ранга 3. Эти группы являются группами автоморфизмов сильно регулярных графов, причем они действуют транзитивно как иа множестве вершин, так и на множестве ребер. Такие графы являются дистанционно транзитивными графами диаметра 2.
Граф Г диаметра сі называется дистанционно транзитивным, если для любого і Є. {О с?} и для любых вершин и, V, х, р, таких что й(и, и) = <і(х, у) = г, существует автоморфизм д графа Г : (и,х)я — (х,у). Дистанционно транзитивные графы диаметра 2 (графы ранга 3) сыграли важную роль в классификации конечных простых групп. Около половины спорадических групп были построены как группы автоморфизмов графов ранга 3 [28].
Если вершины и, їй находятся на расстоянии г в Г, то через 6г(гл, го) (через сДгдгп)) обозначим число вершин в пересечении Гі+1(п) (Ц-Ди)) с [и>]. Дистанционно регулярным графом называется граф, в котором параметры Ьі(и, и>) и сДи, ш)) не зависят от вершин и, V, а зависят только от расстояния на котором эти вершины находятся в графе Г.
Поскольку каждый дистанционно регулярный граф является вполне ре-] гулярным графом (в частности, реберно регулярным графом), то некоторые* результаты об этих классах графов могут быть использованы в теории ди- 1 станционно регулярных графов.
В первой главе монографии [14] доказано, что если Г — неполный связный реберно регулярный граф с параметрами (у,к,), в котором к > Збь то Г имеет диаметр 2 и у < 2к — 2.
Цель работы. В диссертации исследуются строение реберно регулярных графов с к > ЗЬі — 2 и возможные автоморфизмы сильно регулярных графов с малыми параметрами Аид.

новую вершину р из Д. Назовем эту процедуру выталкиванием неподвижных точек относительно (a, d).
Предположим, что каждая связная компонента Д является треугольником. Пусть {d, е, /} — треугольник из Д. Если в результате выталкивания неподвижных точек относительно (a, d) получим вершину е, то после выталкивания относительно (а, /) получится седьмая вершина из Д. В этом случае заключение леммы выполняется.
Теперь Д содержит изолированную вершину и |Д| < 7. Допустим, что |Д| = 5. Тогда Д содержит треугольник {а,Ь,с} и две изолированные вершины d, е. Без ограничения общности, [d] содержит такое ребро {х, z}, что а Є [ж] П [х(], b Є [г] П [г1]. Для ребра {х, у} из [а] и ребра {z, и} из [6] подграфы [у] П [уь] и [а] П [V] содержат вершину е. Применим лемму 1 к подграфу Л = {а, 6, d, е, х, Xі, у, у1, z, zl, и, и1}. Пусть х* — число вершин из Г — Л, смежных точно с г вершинами из Л. Имеем N = 12, М = 25, d = d2 = 5, Д = 4 для г > 2. Поэтому Ех* = 87, Егх* = 118, Е Q)®» = 27. Противоречие с тем, что хо + Е (г 21)= —4- Лемма и предложение 2.2 доказаны.
Пусть Г — граф Зейделя с параметрами (99,14,1,2) и G — Aut(r). Тогда
(11 1 ) ( 1 1 1
р = 14 -4 3 ,Q = 44 -88/7 11/7
^ 84 3 -4 , V 54 81/7 Г- оо 1“Ч
Поэтому значение характера, полученного при проектировании на подпространство размерности 54 равно
1 81 18
Х2(д) = —(54а0(з) + уоДз) - уЫз) = у(42а0(д) + 9аДд) - 2а2(д).
Подставляя в эту формулу значение аДд) = 99 — а0(д) — аДд), получим
Хг(д) = (4аДд) + атЫ
Пусть t — инволюция из С7, Д = Е1х(д). Если |Д| = 1, а 6 Д, то £ переворачивает все 7 ребер из [а], сД£) = 14 и Хг(^) = (4 + 14 — 18)/7 = 0.