Сильно регулярные графы с собственным значением 3, их расширения и автоморфизмы тема автореферата и диссертации по математике, 01.01.06 ВАК РФ

Кагазежева Алена Мухамедовна

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

01.01.06 — математическая логика, алгебра и теория чисел

АВТОРЕФЕРАТ

диссертации на соискание ученой степени кандидата физико-математических наук

-7 0КТ 2015

Екатеринбург - 2015

005563035

Работа выполнена в отделе алгебры и топологии ИММ УрО РАН

Научные руководители: Журтов Арчил Хазешович,

доктор физико-математических наук, Кабардино-Балкарский госуниверситет, зав. кафедрой

Махнев Александр Алексеевич, доктор физ.-мат. наук, член-корр. РАН Институт математики и механики УрО РАН,

зав. отделом

Официальные оппоненты: Алеев Рифхат Жалялович,

доктор физ.-мат. наук, доцент Южно-Уральский госуниверситет, профессор

Чуксина Наталья Владимировна, кандидат физико математических наук, Уральский федеральный университет, доцент

Ведущая организация: Институт математики им. С.Л. Соболева СО РАН

Защита состоится ¿Ц- октября 2015 г. в 14 ч. 00 м. на заседании диссертационного совета Д 004.006.03 по защите диссертаций на соискание ученой степени доктора наук при ИММ УрО РАН по адресу: 620990, Екатеринбург, ул. Софьи Ковалевской, д. 16.

С диссертацией можно ознакомиться в научной библиотеке и на сайте ИММ УрО РАН http://www.imm.uran.ru/

Автореферат разослан сентября 2015 :

Ученый секретарь диссертационного совета кандидат физ.-мат. наук Белоусов И.Н.

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность темы. В связи с завершением классификации конечных простых групп возникла задача единого представления конечных простых групп автоморфизмами конечных геометрий. Позднее в этом направлении возникли задачи, не связанные с групповым действием, в частности, такой является задача исследования дистанционно регулярных графов [1].

Система инцидентности, состоящая из точек и прямых, называется а-частичной геометрией порядка (s,i), если каждая прямая содержит ровно s + 1 точку, каждая точка лежит ровно на t + 1 прямой (прямые пересекаются не более, чем по одной точке) и для любой точки а, не лежащей на прямой L, найдется точно а прямых, проходящих через а и пересекающих L (обозначение pGa(s, t)). Если а = 1, то геометрия называется обобщенным четырехугольником и обозначается GQ(s, t). Точечным графом частичной геометрии называется граф, вершинами которого являются точки геометрии, и две различные вершины смежны, если они лежат на общей прямой (коллинеарны). Легко понять, что точечный граф частичной геометрии pGa{s,t) сильно регулярен с параметрами: v = (s + l)(l + st/a), к - s(i + l), Л = (s-l) + (a-l)t, ¡i = a(i+l). Сильно регулярный граф с такими параметрами для некоторых натуральных чисел а, s, t называется псевдогеометрическим графом для pGa(s, t).

Дж. Кулен предложил задачу изучения дистанционно регулярных графов, в которых окрестности вершин - сильно регулярные графы со вторым собственным значением, не большим t для данного натурального числа t. Заметим, что сильно регулярный граф с нецелым собственным значением является графом в половинном случае, а вполне регулярный граф, в котором окрестности вершин — сильно ре1улярные графы в половинном случае, либо имеет диаметр 2, либо являеься графом Тэйлора. Таким образом, задача Кулена может быть решена пошагово для 4 = 1,2,....

Задача Кулена решена для t = 1 Кардановой М.Л. и Махневым A.A. в [2] и независимо Куленом. Случай t = 2 изучался более 10 лет и завершен в статье И.Н. Белоусова, A.A. Махнева и М.С. Нировой [3]. Рассмотрение случая t = 3 начато в статье A.A. Махнева [4] (теорема редукции) и A.A. Махнева и Д.В. Падучих [5] (список параметров исключительных графов).

В данной работе рассмотрены некоторые сильно ре1улярные графы со вторым собственным значением 3 и найдены их автоморфизмы. Кроме того, найдены массивы пересечений дистанционно регулярных графов, в которых окрестности вершин — подходящие сильно регулярные графы со вторым собственным значением 3. Определены возможные порядки и подграфы неподвижных точек автоморфизмов полученных дистанционно регулярных графов.

Граф Г диаметра d называется дистанционно транзитивным, если для любого » е {0—и для любых вершин u,w,x,y, таких что d(u,w) = d(x,y) = t, существует автоморфизм g графа Г такой, что (u, w)> = (х,у). Дистанционно транзитивные графы диаметра 2 (графы ранга 3) сыграли важную роль в классификации конечных простых групп. Более половины спорадических групп могут быть представлены как группы автоморфизмов графов ранга 3 [б].

Если вершины u,w находятся на расстоянии i в Г, то через b,(u,w) (через сДи.ш)) обозначим число вершин в пересечении Гi+I(u) (в пересечении Г^и)) с И. Дистанционно регулярным графом с массивом пересечений {fo, Ьи ...,6j_i;ci,..., cd} называется графдиаметра d, в котором параметры 6S = b,(u,w) и а = c,(u,w) не зависят от вершин и, w, а зависят только от расстояния, на котором эти вершины находятся в графе Г для г € {0,1 ,...,d}.

Цель работы. Изучить локально GQ{4,11)-графы, найти автоморфизмы сильно регулярных графов с параметрами (96,45,24,18) и (320,99,18,36), перечислить массивы пересечений дистанционно регулярных графов, в которых окрестности вершин - сильно регулярные графы со вторым собственным значением 3 и параметрами (t/, И, 5, /л.') и найти автоморфизмы возникших графов.

Методы исследований. Основными методами исследования являются теоретико-графовые методы и методы теории конечных групп, в частности, метод Г. Хигмена (см. [7]) приложения теории характеров к выяснению порядков автоморфизмов дистанционно регулярных графов.

Научная новизна. Все основные результаты диссертации являются новыми:

- доказано, что сильно регулярный граф с параметрами (96,45,24,18) не является ре-берно симметричным,

- найдены автоморфизмы сильно регулярного графа с параметрами (320,99,18,36),

- получено описание вполне регулярных локально GQ(4,11 )-графов,

- перечислены массивы пересечений дистанционно регулярных графов, в которых окрестности вершин сильно регулярные графы со вторым собственным значением 3 и параметрами (и', к', 5, /х'),

- найдены автоморфизмы дистанционно регулярного графа с массивом пересечений {169,126,1; 1,42,169}.

Теоретическая и практическая ценность. Работа носит теоретический характер. Ее результаты могут быть использованы в геометрии и теории графов.

Апробация работы. Основные результаты диссертации неоднократно докладывались и обсуждались на алгебраическом семинаре отдела алгебры и топологии ИММ УрО РАН, а также были представлены на следующих конференциях: Теория групп и ее приложения, IX Международная школа-конференция по теории групп, Владикавказ 2012 г., Международная конференция по теории групп, посвященная 70-летию В.Д. Мазурова, Новосибирск 2013 г., Международная конференция "Группы и графы, алгоритмы и автоматы" , посвященная 80-летию В.А. Белоногова и 70-летию В.А. Баранского, Екатеинбург 2015 г.

Публикации. По теме диссертации имеется 8 публикаций |18-25] (четыре статьи опубликованы в журналах из списка ВАК). Из пяти статей две написаны без соавторов одна - тремя авторами (Кагазежева A.M., Журтов А.Х., Махнев A.A.), две в соавторстве с Махневыи A.A. В работе трех авторов Журтов А.Х. и Махнев A.A. улучшали некоторые моменты доказательства, предложенного Кагазежевой A.M. В статьях Кагазежевой A.M. и Махнева A.A. второму автору принадлежат постановки задач и идеи доказательств,

сами доказательства принадлежат Кагазежевой A.M.

Структура и объем работы. Диссертация состоит из введения, 4 глав и списка литературы, содержащего 37 наименований. Общий объем диссертации составляет 87 страниц.

КРАТКОЕ СОДЕРЖАНИЕ РАБОТЫ

Во введении даны основные определения и обозначения, используемые в диссертации, обсуждается общая мотивировка решаемых задач, сформулированы основные результаты. В главе 1 получено описание вполне регулярных локально £7(3(4,11)-графов. В главе 2 найдены автоморфизмы сильно регулярного графов с параметрами (96,45,24,18) и (320,99,18,36). В главе 3 перечислены массивы пересечений дистанционно регулярных графов, , в которых окрестности вершин сильно регулярные графы со вторым собственным значением 3 и параметрами (и', И, 5, ц'). В главе 4 найдены автоморфизмы дистанционно регулярного графа с массивом пересечений {169,126,1; 1,42,169}.

Мы рассматриваем неориентированные графы без петель и кратных ребер. Если а, Ь — вершины графа Г, то через ¿(а, Ь) обозначается расстояние между а и Ь, а через 1\(а) — подграф графа Г, индуцированный множеством вершин, которые находятся в Г на расстоянии г от вершины а. Подграф Г! (а) называется окрестностью вершины а и обозначается через [о]. Через а1 обозначается подграф, являющийся шаром радиуса 1 с центром о.

Регулярным графом степени к называется граф Г, такой что для любой вершины и 6 Г выполняется равенство |Г(и)| = к. Реберно регулярным графом с параметрами (и, к. А) называется регулярный граф степени к на V вершинах, любое ребро которого лежит точно в А треугольниках. Вполне регулярным графом, с параметрами (г, к, А, р.) называется реберно регулярный граф с параметрами (и, к. А), в котором любые две вершины и, и> е Г на расстоянии 2 имеют ровно ц общих соседей. Сильно регулярным графом с параметрами («, к, А, ц) называется вполне регулярный граф диаметра 2.

Заметим, что сильно ре1улярный граф с д > 0 является дистанционно регулярным графом диаметра 2, а дистанционно регулярный граф с с* > 2 — вполне регулярным графом ск = Ьо, А = А:-Ь1-1и/* = с2.

Пусть задан класс графов Т. Мы скажем, что граф Г является локально Р-графом, если для любой вершины а € Г имеем Г(а) € -Г. Можно поставить задачу описания локально ^-графов. Если граф Г вершинно симметричен, то окрестности всех его вершин изоморфны, и граф Г является локально ^-графом, где Т состоит из графов, изоморфных некоторому графу Д. В этом случае назовем Г локально А-графом. В более общем случае Р может быть классом графов, удовлетворяющих некоторым условиям. Например, класс связных, реберно регулярных графов — это в точности класс связных, локально регулярных графов.

Определим несколько сильно регулярных графов, которые будут фигурировать в диссертации, а также являются примерами локально Д-графов.

Через Кт1<ъ % Шп обозначим полный п-<Эолъный граф, с долями порядков т,1,.... тп„. Если тп! = ... = т„ = т, то соответствующий граф обозначается через Кпхт (и является

локально Л"(п-1) xm-графом). Граф К1т называется т-лапой. Графом Тэйлора называется дистанционно регулярный граф с массивом пересечений {fc, ц, 1;1,ц, к}.

Пусть М и N—конечные множества порядков тип, соответственно. Два элемента из М х N будем считать смежными, если они различаются точно в одной координате. Полученный граф называется т х п-решеткой, при т = п он сильно регулярен с параметрами (n , 2(п — 1), п — 2,2).

Треугольным графом Т{п) называется граф 2-подмножеств множества порядка п, в котором две вершины смежны тогда и только тогда, когда они пересекаются в точности по одной точке. Граф Т{п) сильно регулярен и имеет параметры (п(п- 1)/2,2(п-2), п-2 4) Окрестность каждой вершины в Т{п) изоморфна 2 х {п-2)-решетке, т.е. Т(п) - локально 2 х (п- 2)-решетка. Верно и обратное: связный локально 2х(п-2)-граф изоморфен Т(тг).

Изучение автоморфизмов дистанционно регулярных графов опирается на метод Хиг-мена приложения теории характеров конечных групп, представленный в третьей главе монографии Камерона [7]. При этом граф Г рассматривается как симметричная схема отношений (Х,К) с d классами, где X - множество вершин графа, До - отношение равенства на Л' и для г > 1 класс Я, состоит из пар (u, w) таких, что d(u, w) = i. Для и в Г положим ki = |Г((и)|, v = |Г|. Классу R, отвечает граф Г, на множестве вершин X в котором вершины u,w смежны, если (u,w) 6 Я,. Пусть Л - матрица смежности графа Г; для г > 0 и А0 = / - единичная матрица. Тогда A(Aj = £р{ Л, для подходящих неотрицательных целых plip называемых числами пересечений графа Г.

Пусть Р, - матрица, в которой на месте (j, I) стоит р[}. Тогда собственные значения i>i(0), :.,Pi(d) матрицы Р, являются собственными значениями графа Г кратностей тп0 = l,...,md. Матрицы Р и Q, у которых на месте (i,j) стоят стоят p,(i) и 9i(i) = соответственно, называются первой и второй матрицей собственных значений схемы и связаны равенством PQ = QP = ]Х\1.

Пусть щ и Wj - левый и правый собственные векторы матрицы Ри отвечающие собственному значению Pl{j) и имеющие первую координату 1. Тогда кратность mj собственного значения Pl(j) равна v/{uj,Wj) ((-,-) - скалярное произведение в евклидовом пространстве С ). Фактически, wj являются столбцами матрицы Р и т,и3 являются строками матрицы Q.

Подстановочное представление группы G = Aut(r) на вершинах графа Г обычным образом дает матричное представление ф группы G в GL{n, С). Пространство С» является ортогональной прямой суммой собственных С-инвариантных подпространств W0 Wd матрицы смежности А = Ai графа Г. Для любого д е G матрица ф(д) перестановочна с А, поэтому подпространство Wt является ^(С)-инвариантным. Пусть Xi - характер представления 4>Wx. Тогда для д е G получим

d

XiW^v-^QijaM,

j=o

где aj(g) - число точек х из X таких, что (х,х') 6 R3. Заметим, что значения характеров являются целыми алгебраическими числами, и если правая часть выражения для yАд) -число рациональное, то Xi(g) — Целое число.

Обобщенные четырехугольники GQ{4, t) имеют допустимые параметры при t 6 {1,2,4, 6,8,11,12,16}. Существование GQ(4, t) известно при t 6 {1, 2,4,6,8,16}. Единственность

GQ{ 4,16) доказана в [8]. При te {11.12} неизвестно существование даже псевдогеометрических графов для GQ(4, í). Хорошо известно следующее предположение

Гипотеза. Если GQ{s,t) существуют, то число s + t четно.

В случае GQ{3, t) единственное допустимое четное значение (равно 6. Однако GQ{3,6) (и даже псевдогеометрический граф для GQ(3,6)) не существует [9] (см. (10]). Таким образом, GQ(4,11) — наименьший обобщенный четырехугольник, который может стать контрпримером к этой гипотезе.

Подмножество Л обобщенного четырехугольника называется гиперовалом, если любая прямая пересекает Л по 0 или 2 точкам. То есть, гиперовал в GQ(s, f) — это регулярный подграф без треугольников степени t + 1, имеющий четное число вершин. Известно (см. [11]), что /i-подграфы в локально GQ(s, ¿)-графах являются гиперовалами. Для гиперовала Д обобщенного четырехугольника прямую L назовем секущей, касательной и внешней прямей, если L ПД содержит две, одну и ноль вершин соответственно; точку, смежную с ребром Д, назовем реберной.

Теорема 1 [18]. Пусть Г является связным вполне регулярным локально GQ(4,11)-графом с параметрами (v, к, Х,ц). Тогда диаметр Г равен 3 и /i 6 {48,50,60,66,72}, причем в случае fi = 72 для любой вершины и подграф Г3(и) является кокликой, содержащей не более 20 вершин.

Ключевую роль в доказательстве теоремы 1 имеет следующий результат, полученный с помощью компьютерных вычислений.

Предложение 1 [18]. Пусть Д является гиперовалом в GQ(4,11) на ц вершинах, Xi — множество вершин вне Д, смежных точно с i вершинами из A, x¡ - Тогда выполняются следующие утверждения:

(1) если ц > 66, то Х0 является кокликой;

(2) если r = fi — 66, z € ХГ и L — прямая, проходящая через z, то Х0 С [z] и либо (i) L является секущей для Л и содержит две точки из X2i, либо

(") ^ — внешняя прямая для А, и если L пересекает Ха, то L содержит 3 точки из Х72.

Следствие 1 [18]. Локально GQ(4,11 )-граф не является дистанционно регулярным.

В главе 2 изучены автоморфизмы сильно регулярных графов с параметрами (96,45,24,18) и (320,99,18,36) (имеющих второе собственное значение 3).

Бехбахани и Лам [11] нашли параметры неизвестных сильно регулярных графов с числом вершин, не большим 100.

Предложение 2. Пусть Г — неизвестный сильно регулярный граф с числом вершин, не большим 100, имеющий неединичный автоморфизм, uG = Aut(r). Тогда выполняется одно из следующих утверждений:

(1) Г имеет параметры (85,30,11,10) ц тг(G) = {2,3,5,17};

(2) Г имеет параметры (85,54,33,36) и {3,5,17} С n(G) С {2,3,5,17};

(3) Г имеет параметры (88,27,6,9) и {2,3,11} С tt(G) С {2,3,5,11};

(4) Г имеет параметры (88,60,41,40) и 7r(G) = {2,3,5,11};

(5) Г имеет параметры (96,45,24,18) и 7r(G) = {2,3,5};

(6) Г имеет параметры (96,50,22,30) и 7r(G) = {2,3,5};

(7) Г имеет параметры (96,60,38.36) и n(G) = {2,3,5};

(8) Г имеет параметры (99,42,21,15) и {2,3,7,11} С ж(G) С {2,3,5,7,11};

(9) Г имеет параметры (99,56,28,36) и {2,3,7,11} С тг(С) С {2,'з| 5,'7,' 11};

(10) Г имеет параметры (100,33,8,12) и ?r(G) = {2,3,5,11};

(11) Г имеет параметры (100,66,44,42) и ir(G) = {2,3,5,11}.

A.A. Махнев и М.С. Нирова предложили программу изучения реберно симметричных графов с параметрами из заключения предложения 2. Следующий результат является вкладом в эту программу

Теорема 2 ([19]). Пусть Г - сильно регулярный граф с параметрами (96,45,24 18) д - элемент простого порядка р из АиЦГ) и А = Fix(5). Тогда выполняется одно ш следующих утверждений:

(1) Д - пустой граф, либор = 3 и оц(д) е {0,36,72}, либор = 2 иа^д) 6 {0,24,48,72,

9

(2) Д является ß-кликой, либо

W Р = 2>0 четно, 4 < 0 < 16 и Zß + а1(д) делится на 24, либо («) р = 5, ß = 1 и оц(д) = 45 или ß = 6 и на Г - Д имеем восемънадцать кликовых {д}-орбит, или /3 = 11 « ка Г - Д ижеел4 тринадцать кликовых и четыре пятиугольных (д)-орбит, или ß = 16 и на Г - Д имеам по восемь кликовых и пятиугольных {д}-орбит-Пя ыап\вМетСЯ 1'к0клик0й- Р = 3 и либо 7 = 3, a,(ff) е {27,63}, либо у = 6, a,(g) е

(4) р = 3, лий, |Д| 6 {6,9,12} и 3|A| + Ö1(S) делится на 36, либо |Д| = 24 и а^д) = 72-

(5) р = 2, либо 4 < |Д| < 40 и 3|Д| + а1(5) делится на 24, либо |Д] = 48, любая вершина из Д смежна с вершиной из Т — Д и ах{д) = 48.

Следствие 2. Сильно регулярные графы с параметрами (96,45,24,18) и (96,50,22,30) не являются реберно симметричными. '

Несуществование псевдогеометрического графа для pG2(5,32) доказано в [12] Псевдогеометрический граф для pG2(5,32) имеет сильно регулярные подграфы - окрестность вершины (псевдогеометрический граф для GQ(4,8)) и вторую окрестность вершины (граф с параметрами (320,99,18,36)). В следующей теореме найдены возможные порядки и неподвижных точек автоморфизмов сильно регулярного графа с параметрами (320,99,18,36). Этот результат завершает описание автоморфизмов локальных подграфов в изорегулярном графе Izo{3) (псевдогеометрическом графе для рС3(6,80)), см. [13].

i,(20l); П,У°тЬ Г явллется сильн° регулярным графом с параметрами v^u,yy, l8,d6J, G = Aut(G), д - элемент простого порядка р из G, П = Fix(g). Тогда С {2,3,5,7,11} и выполняется одно из следующих утверждений:

„j1' П ~ пустой гР°Ф, Р = 5 « a,(i) 6 {0,120} илир = 2 uai(g) 6 {0,48,96,144,192,240 288}; '

(2)0

является одновершинным графомг р = 11 и 01(5) = 66/

(3) П является т-кокликой, р = 3, т = 3« + 2, 3 < t < 14 и ax{g) - 9т - 6 делится на

(¿1

(4) П - объединение I изолированных ребер, 2<1<29р = 2и Ql(g) - 61 делится на

(5) р = 11 и либо

(¿) |П| = 67 и а1(д) = 33, либо (и) |П| = 78 и = 66, либо (ш) |П| = 89 и а(д) = 99;

(6) р = 7 и либо

(г) П = #3*4 « 01(5) € {84,252}, либо

(И) |П| = 7я + 5, 2 < я < 10, а1(з) = 21г и а - г + 3 делится на 8, либо (ш) |П| = 96 ц а1(д) = 0/

(7) р = 5 и либо

(») |П| = 90, 01(5) = 90, ш Г - П имеются 36 пятиугольных (д)-орбит и 10 кокли-ковых;

(и) |Г2| = 85, аг(д) = 15, на Г - П имеются 6 пятиугольных (д)-орбит и 41 кокли-ковая;

(т) |П| = 80, 01(3) 6 {0,120}, на Г - О имеются 48 пятиугольных (д)-орбит или 48 кокликовых;

(¿V) |П| = 5з, 3 < 5 < 15, а^д) = 120г + 15я, г 6 {-2, -1.0,1,2};

(8) р = 3, |П| = Ы + 2, П не содержит вершин степени |П| —2 и либо

является объединением двух изолированных вершин и ¿-подграфа, (д) делится на 72, либо

(И) |П| = 80 или |П| = 140 и а1(д) = 0, либо

(Ш) |П| = Зt + 2, 3 < г < 25, оч(д) = 72э + 9« + 54 и а 6 {-3, -2.....4};

(9) р = 2 и либо (¿) П — куб

и а\{д)/24 — нечетное натуральное число, либо (и) ац(д) = О, |П| = Ш, л 6 {1,2,..., 9}, либо (т) а1(д) ф О, |П| = 5 < Ь < 70 и аг(,д) = 48г + 6«.

В [5] найдены параметры исключительных сильно регулярных графов с неглавным собственным значением 3.

Предложение 3. Пусть Г — исключительный сильно регулярный граф с неглавным собственным значением 3. Если А = 5, то Г имеет параметры (21,10,5,4), (111,30, 5,9) или (169,42,5,12).

В третьей главе диссертации изучены вполне регулярные графы, в которых окрестности вершин сильно регулярны с параметрами (111,30,5,9) или (169,42,5,12). Существование графов с параметрами (111,30,5,9) и (169,42,5,12) неизвестно.

Теорема 4 [21]. Пусть Г — вполне регулярный граф, в котором окрестности вершин

- сильно регулярные графы с параметрами (111,30,5,9), и — вершина графа Г и к{ -|Г,(и)|. Тогда ¿(Г) = 3, к3 четно и выполняется одно из утверждений:

(1) ¡1 = 30, 2 < к3 < 18;

(2) ц = 40, 2 < кз < 6 и Г3 является объединением изолированных вершин и ребер.

Теорема 5 [21]. Пусть Г — вполне регулярный граф, в котором окрестности вершин

— сильно регулярные графы с параметрами (169,42,5,12), и — вершина графа Г и = |1\(и)|. Тогда Й(Г) = 3 и выполняется одно из утверждений:

(1) ц = 39, к3 четно, 2 < к3 < 42; (1) ц = 42, кз нечетно, 3 < к3 < 33

(3) ц - 63, к3 четно, 2 < к3 < 12 м Г3 является объединением изолированных вершин и ребер.

Следствие 3. Пусть Г - дистанционно регулярны,1 граф, в которой окрестности вершин - сильно регулярные графы с собственным значением 3 и параметрами (г/, к', 5, и!) 1огда окрестности вершин либо изоморфны треугольному графу Т(7) и Г - половинный граф 7-куба либо сильно регулярны с параметрами (169,42,5,12) и Г имеет массив пересечений {169,126,1; 1,42,169}.

В главе 4 изучаются автоморфизмы дистанционно регулярного графа с массивом переселений {169,126,1; 1,42,169}. В этой главе существенно используются результаты из

Теорема 6 [22]. Пусть Г - дистанционно регулярный граф, имеющий массив пересечений {169,126,1; 1,42,169}, С = Аи1(Г), д - элемент из О простого порядка р и П = * 1Х(5) содержит по з вершин в t антиподальных классах. Тогда тг(в) С {2,3,5,7,11,13,17. 19} и выполняется одно из следующих утверждений: (1) П — пустой граф и либо (») р = 17, а1(д) = 16 • 17, о2(5) = 24 ■ 17, либо (и) р = 5, а1(д) = 5(26771 + 8) и а2{д) = 5(128 - 26т), либо М р = 2, а3(д) = 41, а,(5) = 170 + 26т + 12/ и а2(д) = 510 - 26т - 161;

, ,~ 19, либ° П ~ дистанционно регулярный граф с массивом пересечений {17 12 11,4,17}, либо { = 37/ 1>..

(3) р = 13, либо П - антиподальный класс, либо П - дистанционно регулярный граф с массивом пересечений {13,9,1; 1,3,13}, либо « = 27,40;

(4) р = 11 и П - дистанционно регулярный граф с массивом пересечений {37.27,1; 1 9 37}; 1..1

(5)р = 7 иг = 2,9,16,23,30,37;

(6) р = 5, либо П - дистанционно регулярный граф с массивом пересечений 19 6 112 9}, либо £ = 15,20,25,30,35,40; .... .

9 Л\Р1 Г, 3' ЛЧб° 8 = 4"' = 2.5, 8,..., 41, либо з = 1, П является (-кликой и t = о, о, 11,14;

(8) р = 2, г четно и либо в = 4, г < 42, либо з = 2 и г < 86.

Л 1 л'Л «т " Г " дистань-ионно регулярный граф, имеющий массив пересечений

п т 1о ц , А Ч в™™1>ом окрестности вершин сильно регулярны с параметрами с, - АиЦГ), д - элемент из С простого порядка р > 2 и П = РЬсЫ ~ содержа^ий ™ ^ вершин в I антиподальных классах. Тогда п(С) С

I 'д> 13.1'} « выполняется одно из следующих утверждений:

(1) некоторая {д)-орбита на Г-П содержит геодезический 2-путь, либор = 7 и { = 2 либор - 5 и П - дистанционно регулярный граф с массивом пересечений {9 6 1-1 2 9}'

(2) некоторая (д)-орбита на Г - П является кликой, р = 3 и либо 5 = 4 \ = 25

и П лвляетсл объединением четырех изолированных (-клик, либо в = 1 и П являете -¿-кликом;

(3) »юеАи {д)-орбита на Г-П является кокликой и либо р = 13, П - антиподальный класс, либо р = 5 и( = 40, либо р = 3, в = 4 и « = 14.

Следствие 4. Пусть Г - дистанционно регулярный граф с массивом пересечений {169,126,1:1,42,169}, в котором окрестности вершин сильно регулярны с параметрами (169,42,5,12). Если С = Ац^Г) - неразрешимая группа, действующая транзитивно на множестве вершин графа Г, то 5 = 5(С) является элементарной абелевой 2-группой, факторгруппа в = С/5 изоморфна 5р4(4), для вершины а 6 Г имеем Са = 2е: (£3 х Л5), 5 содержит нормальную в в подгруппу К порядка 4, регулярную на каждом антиподмь-ном классе, : = 2 для антиподального класса Р, Б/К является неприводимым РгБр^-модулем порядка 28,21в или 232 и С5(/) = К для элемента / порядка 17 из С.

ЛИТЕРАТУРА

1. Brouwer А.Е., Cohen A.M., Neumaier A. Distance-regular graphs // Berlin etc: SpringerVerlag - 1989.

2. Карданова М.Л., Махнев A.A. О графах, в которых окрестности вершин являются графами, дополнительными к графу Зейделя // Доклады академии наук 2010. Т 434 N 4. С. 447-449.

3. Белоусов И.Н., Махнев A.A., Нирова М.С. Дистанционно регулярные графы, в которых окрестности вершин сильно регулярны с собственным значением 2 // Доклады академии наук 2012. Т. 447, N 5. С. 475-478.

4. Махнев A.A. О сильно регулярных графах с собственным значением 3 и их расширениях // Доклады академии наук 2013. Т. 451, N 5. С. 475-478.

5. Махнев A.A., Падучих Д.В. Исключительные сильно регулярные графы с собственным значением 3 // Труды Института математики и механики 2013. Т. 19, N 4. С. 167-174.

6. Prager С.Е., Soicher L.H. Low rank representations and graphs for sporadic groups. Lecture series 8. Cambridge, University press, 1997.

7. Cameron P.J. Permutation Groups. London Math. Soc. Student Texts №45. Cambridge: Cambridge Univ. Press. 1999.

8. Махнев A.A. Обобщенный четырехугольник GQ(4,16) и его расширения, Доклады академии наук 2013, т. 451, N 4, 378-380.

9. гагаКагазежева A.M. О локально СС2(4,11)-графах // Математический форум (Итоги науки. Юг России), т. 6. Группы и графы, Владикавказ 2012, 28-39.

10. Махнев A.A. О псевдогеометрических графах некоторых частичных геометрий, Вопросы алгебры, Гомель: Изд-во Гомельского ун-та, 1997, т.11, 8 стр.

11. Cameron P., Hughes D. R., Pasini A. Extended generalized quadrangles // Geom. Dedic 1990, v. 35. 193-228.

12. Махнев A.A. О несуществовании сильно регулярных графов с параметрами (486,165, 36,66), Украинский матем. журнал. 2002. Том. 54, N 7, 941-949.

13. Махнев A.A., Нирова М.С. Об автоморфизмах сильно регулярного графа с параметрами (640,243,66,108), Доклады академии наук 2011, т. 440, № 6, 743-746.

14. Godsil C.D., Henzel A.D. Distance-regular covers of the complete graphs, J. Comb Theory, ser. В 1992. V. 56. P. 205-238.

15. Кондратьев A.C. Граф Грюнберга-Кегеля конечной группы и его приложения // Алгебра и линейная оптимизация. Труды межд. семинара. Екатеринбург 2002, 141-158.

16. Zavarnitsine A.V. Finite simple groups with narrow prime spectrum, Sibirean electr. Math. Reports 2009. V. 6. P. 1-12.

17. Brouwer A.E., Haemers W.H. Spectra of graphs (course notes), http://www. win.tue.nl/ aeb/

Работы автора по теме диссертации

18. Журтов А.Х., Кагазежева A.M., Махнев А.А. Об автоморфизмах сильно регулярного графа с параметрами (96,45,24,18) // Доклады академии наук 2012, т. 446, № 1, 10-14.

19. Кагазежева A.M. О локально СС2(4,11)-графах // Математический форум (Итоги науки. Юг России), т. 6. Группы и графы. Владикавказ 2012, 28-39.

20. Кагазежева A.M., Махнев А.А. Об автоморфизмах сильно регулярного графа с параметрами (320,99,18,36) // Владикавказский математический журнал 2013, т. 15, N 2, 61-71.

21. Кагазежева A.M., Махнев А.А. О графах, в которых окрестности вершин сильно регулярны с параметрами (111,30,5,9) или (169,42,5,12) // Доклады академии наук 2014, т. 456, № 2, 135-139.

22. Кагазежева A.M. Автоморфизмы дистанционно регулярного графа с массивом пересечений {169,126,1; 1,42,169} // Сибир. электрон, матем. известия 2015, т. 12, 318-327.

23. Журтов А.Х., Кагазежева A.M., Махнев А.А. Об автоморфизмах сильно регулярного графа с параметрами (96,45,24,18) //' Теория групп и ее приложения. Тез.докл. Межд. школы-конф. Владикавказ 2012, 58-59.

24. Kagazezheva A.M., Makhnev А.А. On graphs whose vertex neighborhoods are strongly regular with parameters (111,30,5,9) or (169,42,5,12) // The International Conference on Group Theory in Honor of the 70th Birthday of Professor Victor D. Mazurov. Abstracts, Novosibirsk 2013, 81.

25. Kagazezheva A.M. Automorphisms of graph with intersection array {169,126,1; 1,42,169} // "Groups and Graphs, Algorithms and Automata". Abstracts, Ekaterinburg 2015, 54.