научная статья по теме АВТОМОРФИЗМЫ СИЛЬНО РЕГУЛЯРНОГО ГРАФА С ПАРАМЕТРАМИ (276, 75, 10, 24) Математика

Текст научной статьи на тему «АВТОМОРФИЗМЫ СИЛЬНО РЕГУЛЯРНОГО ГРАФА С ПАРАМЕТРАМИ (276, 75, 10, 24)»

ДОКЛАДЫ АКАДЕМИИ НАУК, 2014, том 457, № 5, с. 516-519

МАТЕМАТИКА

УДК 519.17

АВТОМОРФИЗМЫ СИЛЬНО РЕГУЛЯРНОГО ГРАФА С ПАРАМЕТРАМИ (276, 75, 10, 24)

© 2014 г. Член-корреспондент РАН А. А. Махнев, М. С. Самойленко

Поступило 09.12.2013 г.

DOI: 10.7868/S0869565214230078

Мы рассматриваем неориентированные графы без петель и кратных ребер. Для вершины а графа Г через Г((а) обозначим /-окрестность вершины а, т.е. подграф, индуцированный Г на множестве всех вершин, находящихся на расстоянии / от а. Подграф Г(а) = Г^а) называется окрестностью вершины а и обозначается [а], если граф Г фиксирован. Положим а1 = {а} и [а].

В [1] начато решение задачи изучения дистанционно-регулярных графов, в которых окрестности вершин — сильно регулярные графы с неглавным собственным значением 3. А именно, получена редукция задачи к изучению дистанционно-регулярных графов, в которых окрестности вершин являются исключительными сильно регулярными графами с неглавным собственным значением 3. В [2] найдены параметры исключительных сильно регулярных графов с неглавным собственным значением 3. В [3] классифицированы дистанционно-регулярные графы, в которых окрестности вершин сильно регулярны с параметрами (115, 18, 1, 3).

Предложение. Пусть Г — дистанционно-регулярный граф, в котором окрестности вершин сильно регулярны с параметрами (115, 18, 1, 3). Тогда выполняется одно из следующих утверждений:

1) Г — сильно регулярный граф с параметрами (576, 115, 18, 24), (484, 115, 18, 30) или (392, 115, 18, 40);

2) диаметр Г равен 3, Г имеет массив пересечений {115, 96, 84; 1, 8, 92} и спектр 1151, 23217, 3713, -9805;

3) диаметр Г равен 4 и Г имеет массив пересечений {115, 96, 30, 1; 1, 10, 96, 115}.

Если Г имеет массив пересечений {115, 96, 30, 1; 1, 10, 96, 115}, то для любой вершины и е Г под-

Институт математики и механики им. Н.Н. Красовского

Уральского отделения Российской Академии наук, Екатеринбург

Уральский федеральный университет им. Б.Н. Ельцина, Екатеринбург

граф Г(и) является сильно регулярным с параметрами (115, 18, 1, 3), а подграф Г2(и) является дистанционно-регулярным с массивом пересечений {75, 64, 18, 1; 1, 6, 64, 75}. Антиподальные частные Г2(и) и Г сильно регулярны с параметрами (276, 75, 10, 24) и (392, 115, 18, 40). В данной работе изучены автоморфизмы сильно регулярного графа с параметрами (276, 75, 10, 24).

Теорема. Пусть Г — сильно регулярный граф с параметрами (276, 75, 10, 24), О = Аи^Г), g — элемент простого порядка р из О, О = Р1х^). Тогда п(О) с {2, 3, 5, 7, 23} и выполняется одно из утверждений:

1) О — пустой граф, либор = 2 и а^) = 40« +12, либор = 3 и а^) = 60/ + 12, либор = 23 и а^) = 92;

2) О является п-кликой, либо р = 5, п = 1 и а^) = 75, 175, либор = 2, п = 4 и а^) = 40« + 24;

3) О является 31-кокликой, р = 3, 1 < / < 16 и а^) = 20г + 92 - 51/;

4) О является объединением т (т > 2) изолированных клик, либор = 3 и О — коклика, либор = 2 и порядки изолированных клик в О равны 2 или 4;

5) О содержит геодезический 2-путь и либо

(1)р = 7 и |О| е {38, 45, 52, 59}, либо

(И) р = 5, |О| = 5г + 1, 4 < г < 17, либо

(ш)р = 3, |О| = 3/, 3 < /< 27 и а^) = 20г + 92 — 51/, либо

(IV) р = 2, |О| = 2/, 4 < / < 46 и а^) = 40г + 92 — 34/.

Приведем некоторые вспомогательные результаты.

Лемма 1 [4]. Пусть Г является сильно регулярным графом с параметрами (у, к, А, ц) и неглавными собственными значениями г, «, « < 0. Если А — индуцированный регулярный подграф из Г степени й на w вершинах, то

, , ж (к - й) . ^ < а------ < г,

V - ж

АВТОМОРФИЗМЫ СИЛЬНО РЕГУЛЯРНОГО ГРАФА

517

причем одно из равенств достигается тогда и только тогда, когда каждая вершина из Г—А смежна точно

w(к - А с -- вершинами из А.

V - w

Пусть Г является сильно регулярным графом с параметрами (276, 75, 10, 24) и неглавными собственными значениями 3 и —17. Тогда число вершин в коклике (клике) не больше 51 (не больше 5). Если С является 51-кокликой из Г, то любая вершина из Г—С смежна с 17 вершинами из С.

Доказательство теорем опирается на метод Хигмена работы с автоморфизмами сильно регулярного графа, представленный в третьей главе монографии Камерона [5]. При этом графу Г отвечает симметричная схема отношений (Х, [Е0, Я1, Я2}), где X — множество вершин графа, Я — отношение равенства на X, Я1 — отношение смежности в Г, Я2 — отношение смежности в дополнительном графе Г . Если Р и О — первая и вторая матрицы собственных значений схемы, то

(

Р =

1

к

V - к - 1

1

г

-г - 1

л

1

- 1 у

ности 230. Тогда =

11 а о (г) + а 1 (г) - 9 2 20

, =

= а,-^) для любого /, не кратного р, и 230 — делится на р.

Доказательство. Рассмотрим сильно регулярный граф Г с параметрами (276, 75, 10, 24). Тогда

о =

1 1 1

230 46 -23 5 5

45 -51 18

5 5

и значение характера, полученного при проектировании на подпространство размерности 230,

2 а1 (г) а2 (г)

10 ао (г) +

равно Х1(?) =

12

. Подставляя

в эту формулу значение а2(^) = V — а0(^) —а1(^), по-11ао(г) + а1(г) - 92

лучим Х1&) =

20

РО = ОР = V/. Здесь V — число вершин, к, г, s — собственные значения графа Г кратностей 1, /, V — / — 1 соответственно (указанные кратности образуют первый столбец матрицы 0.

Подстановочное представление группы О = = АШ;(Г) на вершинах графа Г обычным образом дает мономиальное матричное представление у группы О в ОЬ(V, С). Пространство С^ является ортогональной прямой суммой собственных у(О)-инва-риантных подпространств Ж0, Ж1, W2 матрицы смежности графа Г. Пусть %,- — характер представления уW. Тогда для любого g е О получим равен-2

ство 1^) = V-1 ^ Оц а^), где ау-^) — число точек х

1 = 0

из Xтаких, что (х, х^ е Яу-.

Лемма 2. Пусть Г — сильно регулярный граф с параметрами (276, 75, 10, 24), О=АШ;(Г), g — элемент простого порядка р из О и х1 — характер, полученный при проектировании у (О) на подпространство размер-

Два последних утверждения леммы следует из леммы 2 [6].

Лемма 3 [7, теорема 3.2]. Пусть Г является сильно регулярным графом с параметрами (V, к, А, ц) и собственными значениями к, г, —т. Если g — автоморфизм Г и О = Б1х^), то |О| < ута Х ' А ' .

к - г

В случае сильно регулярного графа с параметрами (276, 75, 10, 24) получим |О| < 92.

В леммах 4—8 предполагается, что Г — сильно регулярный граф с параметрами (276, 75, 10, 24), g — автоморфизм Г простого порядка р и О = Б1х^).

Лемма 4. Пусть А — трехвершинный подграф из Г, XI — множество вершин из Г — А, смежных точно с I вершинами из А, XI = |Х-|. Тогда выполняются следующие утверждения:

1) х0 + х3равно 81, если А — клика; равно 120, если А — коклика;

2) х0 + х3 равно 95, если А — геодезический 2-путь; равно 104, если А — объединение изолированной вершины и ребра.

Доказательство. Пусть А — клика. Тогда х2 =3(9 — х3), х1 = 3(55 + х3) и х0 = 81 — х3. Аналогично доказываются остальные утверждения.

Лемма 5. Выполняются следующие утверждения:

1) О — пустой граф, либор = 2 и а^) = 40« + 12, либор = 3 и а^) = 60t + 12, либор = 23 и а^) = 92;

2) если О является п-кликой, то либо

(/)р = 5, п = 1 и а^) = 75, либо

(»)р = 2, п = 4 и а^) = 40« + 24;

3) если О является 1-кокликой, тор = 3, I = 31, 1 < / < 16 и а^) = 20г + 92 — 51/;

518

МАХНЕВ, САМОИЛЕНКО

4) если О является объединением т (т > 2) изолированных клик, то либо р = 3 и О — коклика, либо р = 2 и порядки изолированных клик в О равны 2 или 4.

В леммах 6—8 предполагается, что О содержит геодезический путь Ь, а, с.

Лемма 6. Выполняются следующие утверждения:

1) Г не содержит К11,11-подграфов и собственных сильно регулярных подграфов А с Ад = 10 и = 24;

2) если О содержит [а] для некоторой вершины а е О, тор = 2, О = а1 и а^) = 0;

3)р < 13.

Доказательство. Пусть Г содержит регулярный подграф степени 11 на w вершинах. Тогда

11--64и-_ < 3, поэтому w > 92 . Отсюда Г не со-

276 - ж 3

держит К11,11-подграфов

Пусть Г содержит собственный сильно регулярный подграф А с Ад = 10 и = 24. Тогда 49 + + (кд — 24) = «2 и кд = «2 — 25. Отсюда « = 9, А имеет параметры (162, 56, 10, 24) и число ребер между А и Г — О равно 162 • 19, но не больше 114, противоречие.

Еслир > 29, то О — сильно регулярный подграф с Хп = 10 и = 24, противоречие.

Пусть О содержит вершину а степени 75. Тогда каждая вершина и из Г — О смежна с 24 вершинами из О(а). Поэтому для любой вершины Ь е О — а1 имеем [Ь] с О и [и] п О(а) = [и] п О(Ь) = [а] п [Ь], противоречие. Значит, |О| = 76 и а^) = 0. Поскольку вершина из О(а) смежна с 64 вершинами из Г — О, то р = 2.

Пусть р = 23. Тогда число |О| делится на 23, поэтому |О| = 23, 46, 69, 92. Степень вершины в О сравнима с 6 по модулю 23, А0 = 10 и = 1, 24. Отсюда степень вершины в О равна 29 или 52.

Если О — регулярный граф степени 29, то вви-

ду леммы 1 имеем 29 —

461 О|

< 3, поэтому 23|О| >

276 - |О|

> 13(276 — |О|) и |О| > 78. В случае |О| = 92 подграф Г — О имеет восемь ^)-орбит.

Если О содержит вершину а степени 52, то

52 • 18

число ребер между Г — О и О не меньше

24

две вершины из О, смежные с общей парой ^)-ор-бит на Г — О, противоречие.

Случаи р = 17, 19 рассматриваются аналогично. Лемма 7. Выполняется неравенство р < 7 и в случаер = 7 имеем |О| е {38, 45, 52, 59}.

Доказательство. Пусть р = 13. Тогда число |О| сравнимо с 3 по модулю 13, поэтому |О| = 29, 42, 55, 68, 81. В случае |О| = 81 подграф Г — О имеет пятнадцать ^)-орбит. Степень вершины в О сравнима с 10 по модулю 13, А0 = 10 и = 11, 24. Отсюда степень вершины в О равна 23, 36, 49 или 62. Если О содержит вершину а степени 62, то |О2(а)| >

> 6 2,-12 , противоречие. В случае |О| = 29 граф О

регулярен степени 21, противоречие.

В случае |О| = 81 некоторая вершина и из Г — О

81 • 2

смежна по крайней мере с

15

вершинами из О.

Отсюда подграфы и^ и [и] п О являются коклика-ми. Противоречие с леммой 6. Значит, |О| < 68. Если О содержит вершину а степени 49, то 49 • 12

|О2(а)| > ——— , противоречие. В случае |О| = 68

некоторая вершина и из Г — О смежна по крайней 68 • 3

мере с

18

вершинами из О. Отсюда подграфы

Отсюда |О2(а)| = 39 и О(а) состоит из вершин степени 29 в О. Поскольку каждая вершина из О(а) смежна с двумя ^-орбитами на Г — (О и а1) из се

Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.

Показать целиком