Сильно регулярные графы с собственным значением 3, их расширения и автоморфизмы

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

ОГЛАВЛЕНИЕ
Введение
Глава 1. Локально ОС}(4,11)-графы § 1.1. Вспомогательные результаты § 1.2. Большие гиперовалы в 0(^(4,11)
§ 1.3. Локально 0(^(4,11)-графы
Глава 2. Автоморфизмы сильно регулярных графов с параметрами (96,45, 24,18) и (320,99,18,36)
§ 2.1. Сильно регулярный граф с параметрами (96,45,24,18)
§ 2.2. Графы с параметрами (96,45,24,18) и (96,50,22,30) не являются реберно симметричными
§ 2.3. Сильно регулярный граф с параметрами (320,99,18,36)
Глава 3. Дистанционно регулярные графы, в которых окрестности вершин сильно регулярны со вторым собственным значением
§ 3.1. Графы, в которых окрестности вершин сильно регулярны с параметрами (111, 30, 5, 9)
§ 3.2. Графы, в которых окрестности вершин сильно регулярны с параметрами (169,42,5,12)
Глава 4. Автоморфизмы дистанционно регулярного графа с массивом пересечений {169,126,1;1,42,169}
§ 4.1. Автоморфизмы графа с параметрами (169,42, 5,12)
§ 4.2. Автоморфизмы дистанционно регулярнго графа с массивом пересечений
§ 4.3. Дистанционно регулярный граф с массивом пересечений {169,126,1; 1,42,169}, вершинно симметричный случай Литература
Введение
Для единого представления конечных простых групп перспективным направлением является поиск такого класса конечных геометрий, что каждая конечная простая группа действует флаг-транзитивно на некоторой геометрии и все геометрии этого класса допускают классификацию. Например, класс билдингов Титса характеризует группы лиева типа [1]. Позднее в этом направлении возникли задачи, не связанные с групповым действием. В частности, такой является задача исследования дистанционно регулярных графов [2].
Дж. Зейдель [3] классифицировал все сильно регулярные графы с наименьшим собственным значением —2. Зейдель показал, что кроме треугольных графов Т(п) и решетчатых п х n-графов, сильно регулярными графами, которые имеют наименьшее собственное значение равно —2, являются только полные многодольные графы Кпх2, графы Петерсена, Шрикхандс, Клебша, Шлефли и три графа Чанга.
Дж. Кулеп предложил задачу изучения дистанционно регулярных графов, в которых окрестности вершин — сильно регулярные графы со вторым собственным значением, не большим t для данного натурального числа I. Заметим, что сильно регулярный граф с нецелым собственным значением является графом в половинном случае, а вполне регулярный граф, в котором окрестности вершин — сильно регулярные графы с к — 2/х, либо имеет диаметр 2, либо являеься графом Тэйлора. Таким образом, задача Кулона может быть решена пошагово для /. = 1,2,
Задача Кулена решена для t = 1 (окрестности вершин — графы, дополнительные кзейделевым) Кардановой M.JI. и Махневым A.A. в [4] и независимо Куленом. Случай t — 2 изучался более 10 лет и завершен в статье И.Н. Бело-

усова, A.A. Махнева и М.С. Нировой [5]. Рассмотрение случая t = 3 начато в статье A.A. Махнева [6] (теорема редукции) и A.A. Махнева и Д.В. Падучих [7] (список параметров исключительных графов).
Диссертация вносит существенный вклад в решение задачи Кулена для t — 3. Ее цель — изучить локально GQ(4,11)-графы, найти автоморфизмы сильно регулярных графов с параметрами (96,45,24,18) и (320,99,18,36), перечислить массивы пересечений дистанционно регулярных графов, в которых окрестности вершин сильно регулярные графы со вторым собственным значением 3 и параметрами (г/, к', 5, /Г) и найти автоморфизмы возникших графов.
Основными методами исследования являются теоретико-графовые методы и методы теории конечных групп, в частности метод Хигмсна приложения теории характеров к выяснению порядков автоморфизмов дистанционно регулярных графов.
В работе рассматриваются неориентированные графы без петель и кратных ребер. Если а,Ь ~ вершины графа Г, то через d(a, Ъ) обозначается расстояние между а и Ъ, а через ГДа) - подграф графа Г, индуцированный множеством вершин, которые находятся па расстоянии г в Г от вершины а.
Подграф Г] (а) называется окрестностью вершины а и обозначается через [а]. Через ах обозначается подграф, являющийся шаром радиуса 1 с центром а.
Граф Г называется регулярным графом степени к, если [а] содержит точно к вершин для любой вершины а из Г.
Граф Г называется реберио регулярным графом с параметрами (v,k,), если Г содержит v вершин, является регулярным степени к, и каждое ребро из Г лежит в Л треугольниках.

не менее чем с 5 вершинами, противоречие с леммой 2.1. Теперь либо х$ = О, XI = З—Х4, Х2 = 42+Зхд и хз = 46 —Зх4, либо Х5 = 1, Х4 = О, XI — О, Х2 — 50 и Х3 = 40. Таким образом, /3 = 1. Напомним, что Х{э) = {3>о:о(д)+а{д))/12—4, поэтому 3 + а (д) делится на 12 и а(д) — 45.
Лемма 2.6. Выполняются следующие утверждения:
(1) если А пустой граф, то либо р = 3 и а(д) Е {0, 36, 72}, либо р = 2 и а1(д) € {0,24,48,72,96};
(2) если А является (3-кликой, то либо
(г) р = 2, (3 четно, 4 < /3 < 16 и 3/3 + а^(д) делится на 24, либо (гг) р = 5, /3 = 1 и сДд) = 45 или /3 ш 6 и па Г — Д имеем восемь-надцатъ кликовых (д)-орбит, или Р — 11 гг на Г — Д имеем 13 кликовых и 4 пятиугольных (д)-орбит, или /3 = 16 и на Г — Д имеем по 8 кликовых и пятиугольных (д) -орбит;
(3) если Д является 'у-кокликой, то р = 3 и либо 7 = 3, «1(5) £ {27, 63}, либо 7 = 6, «1(9) €1 {18, 54,90};
(4) если А является объединением п > 2 изолированных клик порядков т > ... > 77гп и т >2, то р = 2 и числа тг четны.
Доказательство. Напомним, что *1(0) = (За0(д) + оДд))/12 - 4. Если Д — пустой граф, то р делит 96, поэтому р = 2 или 3. В случае р = 3 число оДйО делится на 36 и 01(5) € {0,36,72}. В случае р = 2 имеем а(д) 6 {0,24,48,72,96}. Утверждение (1) доказано.
Пусть Д является /3-кликой. Если /3 = 1, то р = 5 и сДд) = 45. Если же Р > 2, то р делит 24 — (Р — 2) и 20, поэтому либо /3 четно и р = 2, либо /3 сравнимо с 1 по модулю 5 и р = 5. Но в случае р = 2 каждая вершина из Г — Д смежна с четным числом вершин из Д, поэтому /3 > 2 и 3/3 + ад (д) делится на 24.