МАТЕМАТИКА
54
АВТОМОРФИЗМЫ СИЛЬНО РЕГУЛЯРНОГО ГРАФА С ПАРАМЕТРАМИ (392, 115, 18, 40)
© 2015 г. Член-корреспондент РАН А. А. Махнев, Д. Н. Пономарев
Поступило 09.01.2014 г.
ДОКЛАДЫ АКАДЕМИИ НАУК, 2015, том 460, № 1, с. 18-21
УДК 519.17+512.
Б01: 10.7868/80869565214310053
Мы рассматриваем неориентированные графы без петель и кратных ребер. Для вершины а графа Г через Гг(а) обозначим г -окрестность вершины а, т.е. подграф, индуцированный Г на множестве всех вершин, находящихся на расстоянии г от а. Подграф Г(а) = Г1(а) называется окрестностью вершины а и обозначается [а], если граф Г фиксирован. Положим а1 = {а} и [а].
Степенью вершины называется число вершин в ее окрестности. Граф Г называется регулярным степени к, если степень любой вершины а из Г равна к. Граф Г назовем реберно-регулярным с параметрами (V, к,Х), если он содержит V вершин, регулярен степени к и каждое его ребро лежит в А треугольниках. Граф Г — вполне регулярный граф с параметрами (V, к, X, ц), если он реберно-регуля-рен с соответствующими параметрами и [а] п [Ь] содержит точно ц вершин для любых двух вершин а, Ь, находящихся на расстоянии 2 в Г. Вполне регулярный граф называется сильно регулярным графом, если он имеет диаметр 2.
Кликовым а -расширением графа Г называется граф Г', полученный заменой каждой вершины и на а -клику Ки, причем вершина из Ки смежна с вершиной из К„ тогда и только тогда, когда и, w смежны в Г.
В [1] начато решение задачи изучения дистанционно-регулярных графов, в которых окрестности вершин — сильно регулярные графы с неглавным собственным значением 3. А именно, получена редукция задачи к изучению дистанционно-регулярных графов, в которых окрестности вершин являются исключительными сильно регу-
Институт математики и механики им. Н.Н. Красовского
Уральского отделения Российской Академии наук, Екатеринбург
Уральский федеральный университет им. Б.Н. Ельцина, Екатеринбург
лярными графами с неглавным собственным значением 3.
В списке дистанционно-регулярных графов, в которых окрестности вершин сильно регулярны с параметрами (115, 18, 1, 3), имеется граф с массивом пересечений {115, 96, 30, 1; 1, 10, 96, 115}.
Если Г — дистанционно-регулярный граф с массивом пересечений {115, 96, 30, 1; 1, 10, 96, 115}, то для любой вершины u е Г подграф Г(и) является сильно регулярным с параметрами (115, 18, 1, 3), подграф Г2(и) является дистанционно-регулярным с массивом пересечений {75, 64, 18, 1; 1, 6, 64, 75}. Антиподальные частные графов Г и Г2(и) сильно регулярны с параметрами (392, 115, 18, 40) и (276, 75, 10, 24) соответственно.
Если Г — сильно регулярный граф с параметрами (392, 115, 18, 40), то для любой вершины u е Г подграфы [u] и Г2(и) сильно регулярны с параметрами (115, 18, 1, 3) и (276, 75, 10, 24). Более того, графы с такими параметрами имеют неглавное собственное значение 3. В [2] найдены возможные автоморфизмы сильно регулярных графов с параметрами (115, 18, 1, 3) и (276, 75, 10, 24).
Предложение 1. Пусть Г — сильно регулярный граф с параметрами (115, 18, 1, 3), G = Aut(r), g — элемент простого порядка p из G, Q = Fix(g). Тогда n(G) с {2,3,5,23} и выполняется одно из утверждений:
1) Q — пустой граф, либо p = 5 и a^g) = 15, 55, либо p = 23 и a1(g) = 23;
2) Q является l-кокликой, 1 < l < 13, p = 3, l сравнимо с 1 по модулю 3 и a1(g) = 24s + 23 - 5l;
3) Q = a1 для некоторой вершины a ей и p = 2.
Предложение 2. Пусть Г — сильно регулярный граф с параметрами (276, 75, 10, 24), G = = Aut(r), g — элемент простого порядка p из G, Q = Fix(g). Тогда n(G) £ {2,3,5,7,23} и выполняется одно из утверждений:
1) D. — пустой граф, либо p = 2 и a1(g) = 40s + 12, либо p = 3 и a1(g) = 60t + 12, либо p = 23 и a1(g) = 92;
2) О является п -кликой, либо р = 5, п = 1 и а^) = 75,175, либо р = 2, п = 4 и а1(?) = 40/ + 24;
3) О является / -кокликой, р = 3, 3 < / < 48;
4) О является объединением т (т > 2) изолированных клик, либо р = 3 и О — коклика, либо р = 2 и порядки изолированных клик в О равны 2 или 4;
5) О содержит геодезический 2-путь и либо
(1) р = 7 и |П|е {38,45,52,59}, либо
(И) р = 5,|П|= 5г +1,4 < г < 17, либо
(ш) р = 3, | а |= 3^, 3 < 5 < 27, либо
(IV) р = 2, | О |= 2t, 4 < г < 46.
С помощью предложений 1 и 2 найдены автоморфизмы сильно регулярного графа с параметрами (392, 115, 18, 40).
Теорем а. Пусть Г — сильно регулярный граф с параметрами (392, 115, 18, 40), О = Ат(Г), g — элемент из О простого порядка р и О = Р1х^). Тогда |О| делит 8 • 7 • 23 и выполняется одно из следующих утверждений:
1) О — пустой граф, либо р = 2 и а^) = 56г, либо р = 7 иа^) = 140;
2) |П| = 1, р = 23 и а^) = 115.
Этот результат является ключевым для описания автоморфизмов дистанционно-регулярного графа с массивом пересечений {115, 96, 30, 1; 1, 10, 96, 115}.
Приведем некоторые вспомогательные результаты.
Лемма 1. Пусть Г является сильно регулярным графом с параметрами (V, к, X, ц) и неглавными собственными значениями г, 5, 5 < 0. Если А — индуцированный регулярный подграф из Г степени й на w вершинах, то
. , w(k - й) ,
5 < й--1-- < Г,
V - w
причем одно из равенств достигается тогда и только тогда, когда каждая вершина из Г - А
w(k - й) л
смежна точно с —-- вершинами из А.
V - ^
Доказательство. Это утверждение хорошо известно (см., например, § 2 из [3]).
Пусть Г является сильно регулярным графом с параметрами (392, 115, 18, 40) и неглавными собственными значениями 3 и —25. Если А — индуцированный регулярный подграф из Г степени й на w вершинах, то
й - 3 < ^И5-^ < й + 25.
392 - w
Поэтому число вершин в коклике (клике) не больше 70 (не больше 5). Если С является 70-ко-кликой из Г, то любая вершина из Г - С смежна точно с 25 вершинами из С.
Доказательство теорем опирается на метод Хигмена работы с автоморфизмами сильно регулярного графа, представленный в третьей главе монографии Камерона [4]. При этом графу Г отвечает симметричная схема отношений (X, {Я0, Я1, ^2}), где X — множество вершин графа, Я0 — отношение равенства на X, Я1 — отношение смежности в Г, Я2 — отношение смежности в дополнительном графе Г. Если Р и Q — первая и вторая матрицы собственных значений схемы, то
( 1 1 1 ^
Р =
1
к
1
^у - к -1 -г -1 -5 - 1у
PQ = QP = VI. Здесь V — число вершин, к, г, 5 — собственные значения графа Г кратностей 1, /, V — / — 1 соответственно (указанные кратности образуют первый столбец матрицы Q).
Подстановочное представление группы О = = Аи(Г) на вершинах графа Г обычным образом дает мономиальное матричное представление у группы О в ОЬ^, С). Пространство С^ является ортогональной прямой суммой собственных у(О)-инвариантных подпространств W0,W1,W2 матрицы смежности графа Г. Пусть х, — характер представления yW¡. Тогда для любого g е О получим равенство
Ъ (¿) = VQij а ]
1=0
где а у (¿) — число точек х из X таких, что (х, ^) 6 Яу.
Лемма 2. Пусть Г — сильно регулярный граф с параметрами (392, 115, 18, 40), О = Ат(Г), g — элемент простого порядка р из О и х2 — характер, полученный при проектировании у (О) на подпространство
размерности 46, тогда х2(?) =
3а0^) - а^) 28
+16,
а, (¿) = а^ ) для любого I, не кратного р, и 46 - х^) делится на р.
Доказательство. Рассмотрим сильно регулярный граф Г с параметрами (392, 115, 18, 40). Тогда
Q =
Г 1 1 14
345 9 -5 46 -10 4
и значение характера, полученного при проектировании на подпространство размерности 46, равно
46^) - 10а^) + 4а2(я)
%2(Я) ='
. Подставляя в эту
20
МАХНЕВ, ПОНОМАРЕВ
формулу значение a2(g) = v - а0(g) - a1(g), полу, ч 3а0(g) - a1(g) л, чим х 2(g) = 0 ' 1 +16.
28
Два последних утверждения леммы следуют из леммы 2 [5].
Лемма 3 [1, лемма 4]. Пусть Г является сильно регулярным графом с параметрами (v, кД, ц) и собственными значениями к, r,-m. Если g — автоморфизм Г и D. = Fix(g), то |Q| < v • max{^'^}.
к - r
В случае сильно регулярного графа с параметрами (392, 115, 18, 40) получим |Q| < 140.
Лемма 4. Пусть А является 4-кликой сильно регулярного графа Г с параметрами (392, 115, 18, 40), X — множество вершин из Г - А, смежных точно с i вершинами из А, xt = |Xi|.
Тогда выполняются следующие утверждения:
1) x0 = 36, x1 = 256, x2 = 96;
2) X0 — регулярный граф степени 3.
Доказательство. Заметим, что xt = 0 для i > 3. Поэтому x2 = 6 • 16 = 96, x1 = 4 • 64 = 256 и x0 = 36.
Пусть a е X0, y = |Xt пГ2(а)|. Тогда y2 = 6 • 8 = = 48, y1 = 4 • 48 = 192 и y0 = 32. Отсюда X0 - регулярный граф степени 3. Лемма доказана.
Для a ей пусть Q' = Q(a), a1(g)' — число вершин u е [a] таких, что u смежна с ug, a1(g)" — число вершин u е Г - a1 таких, что u смежна с ug. Тогда
«1(g)'+ «1(g)" = «1(g).
Лемма 5. Пусть Г — сильно регулярный граф с параметрами (392, 115, 18, 40), g — автоморфизм Г простого порядка p и Q = Fix(g). Тогда выполняются следующие утверждения:
1) если D. — пустой граф, то либо p = 2 и a1(g) = 56r, либо p = 7 и a1(g) = 140;
2) если D. является кликой или кокликой, то |Q| = 1, p = 23 и a1(g) = 115;
3) D. не является объединением m (m > 2) изолированных клик.
Доказательство. Пусть D. — пустой граф. Поскольку 392 = 8 • 49, то p е {2,7}.
Пусть p = 2. По лемме 2 число a1(g) делится на 56.
Пусть p = 7. По лемме 2 число a1(g) - 3 делится на 23, поэтому a1(g) = 196s - 56. Если s > 2, то некоторая (g)-орбита является 7-кликой, противоречие. Утверждение 1) доказано.
Пусть Q является n-кликой. Если n = 1 и Q = {a}, то p делит 115 и 276, поэтому p = 23. Ввиду леммы 2 число a1(g) - 3 делится на 28, поэтому a1(g) = 115.
Пусть n > 2 и a,b ей. Поскольку g действует полурегулярно на [a] - bL, то p делит 96 и p = 2,3. Далее, g действует полурегулярно на [a] n [b] - Q, поэтому 20 - n делится наp. Ввиду предложения 1 имеем p = 3, n = 2 и aj(g) = 24s + 18. Далее, для a ей элемент g действует без неподвижн^тх точек на r2(a) и a"(g) = 60t +12. С другой стороны,
X2(g) = 6—a1(g) + 16, поэтому a1(g) = 84l + 6, про-28
тиворечие с тем, что 4s + 3 + 10t + 2 = 14l.
Пусть D. является l-кокликой, l > 2. Для различных вершин a, b eQ элемент g действует полурегулярно на [a] n [b], [a] - [b] и на r2(a) n r2(b) - Q, поэтому p делит 40, 75 и 202 - l. Отсюда p = 5 и
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.