ДОКЛАДЫ АКАДЕМИИ НАУК, 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 рублей.