=Paper=
{{Paper
|id=Vol-1662/alg2
|storemode=property
|title=Автоморфизмы дистанционно регулярного графа с массивом пересечений {121, 90, 1; 1, 30, 121}(Automorphisms of distance-regular graph with intersection array {121, 90, 1; 1, 30, 121})
|pdfUrl=https://ceur-ws.org/Vol-1662/alg2.pdf
|volume=Vol-1662
|authors=Konstantin S. Efimov,Alexander A. Makhnev
}}
==Автоморфизмы дистанционно регулярного графа с массивом пересечений {121, 90, 1; 1, 30, 121}(Automorphisms of distance-regular graph with intersection array {121, 90, 1; 1, 30, 121})==
https://ceur-ws.org/Vol-1662/alg2.pdf
Автоморфизмы дистанционно регулярного графа
с массивом пересечений {121, 90, 1; 1, 30, 121}
К.С. Ефимов2 А.А. Махнев1
konstantin.s.efimov@gmail.com makhnev@imm.uran.ru
1 – ИММ УрО РАН (Екатеринбург)
2 – УрФУ (Екатеринбург)
Аннотация
А.А. Махнев и М.С. Самойленко выделили параметры сильно регу-
лярных графов с не более чем 1000 вершинами, которые могут быть
окрестностями вершин в антиподальном дистанционно регулярном
графе диаметра 3 с λ = µ. Ими же предложена программа исследо-
вания вершинно симметричных антиподальных дистанционно регу-
лярных графов диаметра 3 с λ = µ, в которых окрестности вершин
сильно регулярны с вышеуказанными параметрами. В данной ра-
боте рассмотрен граф с массивом пересечений {121, 90, 1; 1, 30, 121}.
Доказано, что вершинно симметричный граф с массивом пересече-
ний {121, 90, 1; 1, 30, 121} является реберно симметричным с цоко-
лем группы автоморфизмов, изоморфным Z2 × L2 (121).
1 Введение
Мы рассматриваем неориентированные графы без петель и кратных ребер. Для вершины a графа Γ
через Γi (a) обозначим i-окрестность вершины a, то есть подграф, индуцированный Γ на множестве всех
вершин, находящихся на расстоянии i от a. Положим [a] = Γ1 (a), a⊥ = {a}∪[a]. Графом Тэйлора называется
дистанционно регулярный граф с массивом пересечений {k, µ, 1; 1, µ, k}.
Допустим, что Γ — антиподальный дистанционно регулярный граф диаметра 3 с λ = µ, в котором
окрестности вершин сильно регулярны. Тогда Γ имеет массив пересечений {k, µ(r − 1), 1; 1, µ, k} и спектр
√ f √ f
k 1 , k , −1k , − k , где f = (k + 1)(r − 1)/2. Далее, (r − 1)k 0 = v 0 − k 0 − 1 и число (v 0 + 1)(r − 1) четно. В
случае r = 2 получим граф Тэйлора, в котором k 0 = 2µ0 . Обратно, для любого сильно регулярного графа
с параметрами (v 0 , 2µ0 , λ0 , µ0 ) найдется граф Тэйлора, в котором окрестности вершин сильно регулярны с
соответствующими параметрами.
В [1] выделены параметры сильно регулярных графов с не более чем 1000 вершинами, которые могут
быть окрестностями вершин в антиподальном дистанционно регулярном графе диаметра 3 с λ = µ.
В рамках проекта РНФ 14-11-00061 продолжается программа исследования вершинно симметричных
антиподальных дистанционно регулярных графов диаметра 3 с λ = µ, в которых окрестности вершин
сильно регулярны с параметрами из заключения предложения [1]. В данной работе рассмотрены параметры
(121, 30, 11, 6).
Copyright c by the paper’s authors. Copying permitted for private and academic purposes.
In: A.A. Makhnev, S.F. Pravdin (eds.): Proceedings of the 47th International Youth School-conference “Modern Problems in
Mathematics and its Applications”, Yekaterinburg, Russia, 02-Feb-2016, published at http://ceur-ws.org
7
Теорема 1. Пусть Γ — сильно регулярный граф с параметрами (121, 30, 11, 6), G = Aut(Γ), g — элемент
простого порядка p из G и Ω = Fix(g). Тогда π(G) ⊆ {2, 3, 5, 7, 11} и выполняется одно из следующих
утверждений:
(1) Ω является пустым графом, p = 11 и α1 (g) = 0, 121;
(2) Ω является n-кликой, либо n = 1, p = 5, α1 (g) = 55l + 30 или p = 3, α1 (g) = 33l − 3, либо n = 3t + 1,
1 6 t 6 3, p = 3 и α1 (g) = 33l − 3 − 9t, либо n = 2t + 1, 1 6 t 6 5, p = 2 и α1 (g) = 22l + 8 − 6t;
(3) Ω является m-кокликой, либо m = 3t + 1, 1 6 t 6 3, p = 3 и α1 (g) = 33l − 9t − 3, либо m = 2t + 1,
1 6 t 6 5, p = 2 и α1 (g) = 22l + 8 − 6t;
(4) Ω содержит ребро и является объединением s изолированных клик и либо p = 3, число вершин в
максимальной клике из Ω сравнимо с 1 по модулю 3 и s сравнимо с 1 по модулю 3, либо p = 2, число
вершин в максимальной клике из Ω нечетно и s нечетно;
(5) если Ω содержит [a] для некоторой вершины a, то p 6 3, в случае |Ω| = 31 имеем p = 3 и
α1 (g) = 33l − 60, 2 6 l 6 4;
(6) Ω содержит геодезический путь, p 6 7 и в случае p = 7 подграф Ω сильно регулярен с параметрами
(16, 9, 4, 6).
Теорема 2. Пусть Γ — дистанционно регулярный граф с массивом пересечений {121, 90, 1; 1, 30, 121},
G = Aut(Γ), g — элемент простого порядка p из G и Ω = Fix(g) содержит по s вершин в t антиподальных
классах. Тогда π(G) ⊆ {2, 3, 5, 7, 11, 13, 23, 61} и выполняются следующие утверждения:
(1) если Ω — пустой граф, то p ∈ {2, 61};
(2) если Ω — антиподальный класс, то p = 11;
(3) если Ω — клика, то p = 3 и t = 2, 5, 8, 11;
(4) если p > 11, то либо p = 23 и Ω — дистанционно регулярный граф с массивом пересече-
ний {29, 21, 1; 1, 7, 29}, либо p = 13 и Ω — дистанционно регулярный граф с массивом пересечений
{17, 12, 1; 1, 4, 17};
(5) если p = 7, то t = 10, 17, 24 и в случае t = 10 подграф Ω является дистанционно регулярным с
массивом пересечений {9, 6, 1; 1, 2, 9};
(6) если p = 5, то t = 2, 7, 12, 17, 22, 27 и в случае t = 7 подграф Ω является объединением четырех
изолированных 7-клик;
(7) если p = 3, s = 4, то t = 3l + 2, l 6 9 и в случае t = 5 подграф Ω является объединением четырех
изолированных 5-клик;
(8) если p = 2, s > 0, то каждая вершина из Γ − Ω смежна с четным числом вершин из Ω и либо s = 2,
t 6 60, либо s = 4, t 6 30.
Следствие. Вершинно симметричный дистанционно регулярный граф с массивом пересечений
{121, 90, 1; 1, 30, 121} является реберно симметричным графом с группой автоморфизмов, имеющей цо-
коль Z2 × L2 (121).
Заметим, что ввиду границы Дельсарта [2, предложение 4.4.6] максимальный порядок клики в дистан-
ционно регулярном графе с массивом пересечений {121, 90, 1; 1, 30, 121} и спектром 1211 , 11305 , −1121 , −11305
не больше 1 − k/θd = 1 + 121/11 = 12. Если C является 12-кликой из Γ, то каждая вершина вне C смежна
с 0 или с b1 /(θd + 1) + 1 − k/θd = −9 + 12 = 3 вершинами из C.
2 Автоморфизмы графа с параметрами (121, 30, 11, 6)
В этом параграфе Γ — сильно регулярный граф с параметрами (121, 30, 11, 6) (псевдогеометрический
граф для сети pG2 (10, 2)) и спектром 301 , 830 , −390 , G = Aut(Γ), g – элемент простого порядка p из G и
Ω = Fix(g).
Ввиду границ Хофмана, порядок коклики в Γ не больше vm/(k + m) = 121 · 3/33 = 11, порядок клики
C в Γ не больше 1 + k/m = 11 и в случае |C| = 11 каждая вершина из Γ − C смежна точно с 2 вершинами
из C.
Лемма 1. Пусть ψ — мономиальное представление группы G в GL(121, C), χ1 — характер проекции
ψ на подпространство собственных векторов размерности 30, отвечающих собственному значению 8.
Тогда χ1 (g) = (3α0 (g) + α1 (g))/11 − 3 и χ1 (g) − 30 делится на p.
8
Доказательство. Имеем
1 1 1
Q = 30 8 −3 .
90 −9 2
Поэтому χ1 (g) = (30α0 (g) + 8α1 (g) − 3α2 (g))/121. Подставляя α2 (g) = 121 − α0 (g) − α1 (g), получим
χ1 (g) = (3α0 (g) + α1 (g))/11 − 3.
Последнее утверждение леммы следует из [3, лемма 1].
Лемма 2. Пусть A — трехвершинный подграф из Γ, yi — число вершин из Γ − A, смежных точно с
i вершинами из A. Если A — коклика, то y0 = 46 − y3 , если A — объединение изолированной вершины и
ребра, то y0 = 53 − y3 , если A — геодезический путь, то y0 = 59 − y3 , а если A — клика, то y0 = 64 − y3 .
Доказательство. Пусть A — коклика. Тогда y1 = 54 + 3y3 , y2 = 18 − 3y3 и y0 = 46 − y3 . Пусть A —
клика. Тогда y1 = 24 + 3y3 , y2 = 30 − 3y3 и y0 = 64 − y3 . Аналогично рассматриваются оставшиеся случаи.
Лемма 3. Выполняются следующие утверждения:
(1) Γ не содержит собственных сильно регулярных подграфов с параметрами (v 0 , k 0 , 11, 6);
(2) если Ω является пустым графом, то p = 11 и α1 (g) = 0, 121;
(3) если Ω является n-кликой, то либо n = 1, p = 5, α1 (g) = 55l + 30 или p = 3, α1 (g) = 33l − 3, либо
n = 3t + 1, 1 6 t 6 3, p = 3 и α1 (g) = 33l − 3 − 9t, либо n = 2t + 1, 1 6 t 6 5, p = 2 и α1 (g) = 22l + 8 − 6t;
(4) если Ω является m-кокликой, либо m = 3t + 1, 1 6 t 6 3, p = 3 и α1 (g) = 33l − 9t − 3, либо m = 2t + 1,
1 6 t 6 5, p = 2 и α1 (g) = 22l + 8 − 6t;
(5) если Ω содержит ребро и является объединением s изолированных клик, то либо p = 3, число
вершин в максимальной клике из Ω сравнимо с 1 по модулю 3 и s сравнимо с 1 по модулю 3, либо p = 2,
число вершин в максимальной клике из Ω нечетно и s нечетно.
Доказательство. Пусть Γ содержит собственный сильно регулярный подграф ∆ с параметрами
(v 0 , k 0 , 11, 6). Тогда n2 = 4(k 0 − 6) + 25, поэтому n = 2u + 1 и k 0 = u2 + u. Далее, ∆ имеет неглавные
собственные значения u + 3, 2 − u и кратность u + 3 равна (u − 1)(u2 + u)(u2 + 2u − 2)/(6(2u + 1)). При
u = 4 получим 3 · 20 · 22/54, а при u = 3 граф ∆ является полным многодольным. В любом случае имеем
противоречие.
Пусть Ω является пустым графом. Тогда p = 11, χ1 (g) = α1 (g))/11 − 3 и χ1 (g) − 30 делится на 11.
Поэтому α1 (g) равно 0 или 121.
Пусть Ω является n-кликой. Если n = 1, то p делит 30 и χ1 (g) = (α1 (g) − 30)/11. В случае p = 5
число χ1 (g) делится на 5, поэтому α1 (g) = 55l + 30. В случае p = 3 число χ1 (g) делится на 3, поэтому
α1 (g) = 33l − 3. В случае p = 2 имеем α1 (g) = 0 и χ1 (g) = −3 и χ1 (g) − 30 не делится на 2, противоречие.
Если n > 1, то p делит 18 и 13−n. В случае p = 3 имеем n = 3t+1, t 6 3, число χ1 (g) = (9t−30+α1 (g))/11
делится на 3 и α1 (g) = 33l − 3 − 9t. В случае p = 2 имеем n = 2t + 1, t 6 5, число χ1 (g) = (6t − 30 + α1 (g))/11
четно и α1 (g) = 22l + 8 − 6t. В случае t = 5 каждая вершина из Γ − Ω смежна с четным числом вершин из
Ω, поэтому α1 (g) = 22(l − 1) = 0.
Пусть Ω является m-кокликой, m > 1. Тогда p делит 6 и 67 − m. В случае p = 3 число χ1 (g) делится на
3, m = 3t + 1, t 6 3, χ1 (g) = (9t + 3 + α1 (g))/11 − 3 и α1 (g) = 33l − 9t − 3. В случае p = 2 число χ1 (g) четно,
m = 2t + 1, t 6 5, χ1 (g) = (6t + 3 + α1 (g))/11 − 3 и α1 (g) = 22l + 8 − 6t.
Пусть Ω содержит ребро и является объединением s изолированных клик. Тогда p делит 6 и 18. В случае
p = 3 число вершин в максимальной клике из Ω сравнимо с 1 по модулю 3 и s сравнимо с 1 по модулю 3.
В случае p = 2 число вершин в максимальной клике из Ω нечетно и s нечетно.
Лемма 4. Пусть Ω содержит геодезический путь b, a, c. Тогда выполняются следующие утверждения:
(1) p 6 11 и если α2 (g) = 0, то либо p = 7, α0 (g) = 44, либо p = 5, α0 (g) = 11, либо p = 3, α0 (g) = 22, 55,
либо p = 2, α0 (g) = 11, 33, 55;
(2) если Ω содержит [a] для некоторой вершины a, то p 6 3, в случае |Ω| = 31 имеем p = 3 и
α1 (g) = 33l − 60, 2 6 l 6 4.
Доказательство. Пусть p > 13. Тогда Ω – сильно регулярный подграф с параметрами (v 0 , k 0 , 11, 6),
противоречие.
Если α2 (g) = 0, то χ1 (g) = 8 + 2α0 (g)/11, причем χ1 (g) − 30 делится на p, поэтому 2α0 (g)/11 − 22 делится
на p. Отсюда α0 (g) = 11w, p делит 2(11 − w) и либо p = 11, α0 (g) = 121, противоречие, либо p = 7,
α0 (g) = 44, либо p = 5, α0 (g) = 11, либо p = 3, α0 (g) = 22, 55, либо p = 2, α0 (g) = 11, 33, 55.
9
Пусть Ω содержит [a] для некоторой вершины a. Тогда [u] ∩ Ω содержит 6 вершин из Ω для любой
вершины u ∈ Γ − Ω. Отсюда любая hgi-орбита длины p не содержит геодезических 2-путей, в частности
она является кликой или кокликой.
Если p > 7, то [u] ∩ Ω является 6-кликой и для двух вершин b, c ∈ [u] ∩ Ω подграф [b] ∩ [c] содержит a, 4
вершины из [u] ∩ Ω и p верщин из hgi-орбиты, содержащей u, противоречие.
В случае p = 5 подграф [u]∩Ω является кликой, иначе для двух несмежных вершин b, c ∈ [u]∩Ω подграф
[b] ∩ [c] содержит a и 5 верщин из hgi-орбиты ∆, содержащей u. В этом случае [u] ∩ Ω является кокликой,
противоречие с тем, что ∪b∈[u]∩Ω ([a] ∩ [b]) содержит не менее 55 вершин. Если ∆ – клика, то ∆ ∪ (Ω ∩ [u])
является 11-кликой, противоречие с тем, что a смежна с 6 вершинами этой клики. Значит, ∆ – коклика,
противоречие с тем, что ∪u∈∆ ([u] − [a]) содержит не менее 120 вершин. Итак, p 6 3.
Если |Ω| = 31, то χ1 (g) = (60 + α1 (g))/11 и χ1 (g) − 30 делится на p. В случае p = 3 имеем α1 (g) = 33l − 60,
2 6 l 6 4. В случае p = 2 имеем α1 (g) = 22l − 60, для вершины u, смежной с ug , подграф [u] содержит
нечетное число вершин из Ω − [a], противоречие.
Лемма 5. Пусть Ω содержит геодезический путь b, a, c. Тогда p 6 7 и в случае p = 7 подграф Ω сильно
регулярен с параметрами (16, 9, 4, 6).
Доказательство. Пусть p = 11. Тогда µΩ = 6 и для смежных вершин a, b ∈ Ω подграф Ω(a) ∩ [b]
содержит 0 или 11 вершин. Далее, |Ω| = 11t, t 6 5, и степень вершины в Ω равна 8, 19.
Если a – вершина степени 8 в Ω, то число ребер между Ω(a) и Ω2 (a) равно 6(11t − 9) = 18e + 7(8 − e),
поэтому 6t = 10 + e и либо t = 2 = e, либо t = 3, e = 8. В любом случае имеем противоречие с тем, что для
двух вершин b, c из Ω(a), смежных с 18 вершинами из Ω2 (a), подграф [b] ∩ [c] содержит не менее 12 вершин
из Ω2 (a). Итак, Ω – регулярный граф степени 19 на 44 вершинах. Теперь число ребер между Ω(a) и Ω2 (a)
равно 6 · 24 = 18e + 7(19 − e), поэтому e = 1. Для вершины b из Ω(a), смежной с 18 вершинами из Ω2 (a),
и вершины c из Ω − (a⊥ ∪ b⊥ ) подграф [c] содержит не более 12 вершин из a⊥ ∪ b⊥ и не более 5 вершин из
Ω − (a⊥ ∪ b⊥ ), противоречие.
Пусть p = 7. Тогда µΩ = 6 и для смежных вершин a, b ∈ Ω подграф Ω(a) ∩ [b] содержит 4 или 11 вершин.
Далее, |Ω| = 7t + 2, t 6 8, и степень вершины в Ω равна 9, 16, 23. В случае |Ω| = 58 ввиду леммы 2 каждая
hgi-орбита длины 7 является кликой, α2 (g) = 0, противоречие с леммой 4. В случае |Ω| = 51 имеем χ1 (g) =
(153 + α1 (g))/11 − 3 и α1 (g) = 56. Далее, ввиду леммы 2 степень вершины в hgi-орбите Σ длины 7 равна
4 или 6. Если степень вершины u в Σ равна 4, то Σ содержит трехвершинный подграф Σ0 , являющийся
объединением изолированной вершины и ребра, причем Σ0 попадает в окрестности двух вершин из Σ.
Таким образом, имеется восемь кликовых hgi-орбит длины 7 и две hgi-орбиты степени 4. Вершина u из
кликовой hgi-орбиты Φ длины 7 смежна не более чем с 5 вершинами из Ω, иначе Φ ∪ (Ω ∩ [u]) является
13-кликой, противоречие. Теперь число ребер между Ω и Γ − Ω, деленное на 7, не больше 5 · 8 + 2 · 3 = 46.
Если a – вершина степени 9 в Ω, то число ребер между Ω(a) и Ω2 (a) равно 6(7t − 8) = 18e + 11m + 4(9 −
m − e), поэтому 6t = 12 + m + 2e, t 6 5. В случае t = 2 имеем m = e = 0 и Ω – сильно регулярный граф
с параметрами (16,9,4,6). В случае t = 3 имеем m = 6, e = 0 и множество Σ вершин из Ω(a), смежных с
11 вершинами из Ω2 (a), индуцирует клику. Противоречие с тем, что для двух вершин b, c ∈ Σ подграф
[b] ∩ [c] содержит 4 вершины из Σ и не менее 9 вершин из Ω2 (a). В случае t = 4 имеем m + 2e = 12 и e 6 1,
противоречие. В случае t = 5 имеем e = 9 и для двух несмежных вершин b, c из Ω(a) подграф [b] ∩ [c]
содержит a и не менее 9 вершин из Ω2 (a), противоречие.
Итак, в Ω нет вершин степени 9. Если a, b – две вершины степени 23 в Ω, то либо a, b не смежны и Ω
содержит a, b, 6 вершин из [a] ∩ [b], по 17 вершин из [a] − [b], [b] − [a] и еще 7t − 40 вершин, либо a, b смежны
и Ω содержит a, b, δ вершин из [a] ∩ [b], по 22 − δ вершин из [a] − [b], [b] − [a] и еще 7t + δ − 44 вершин.
Отсюда t > 6.
Пусть z — число вершин степени 16 в Ω. Тогда число ребер между Ω и Γ − Ω, деленное на 7, равно
2z + (|Ω| − z). В случае |Ω| = 51 указанное число ребер не больше 46, противоречие. Итак, t = 6 и для
двух несмежных вершин a, b степени 23 в Ω подграф Ω содержит a, b, 6 вершин из [a] ∩ [b], по 17 вершин
из [a] − [b], [b] − [a] и 2 вершины вне a⊥ ∪ b⊥ . Противоречие с тем, что степень вершины c из Ω − (a⊥ ∪ b⊥ ) в
графе Ω не больше 1+12. Значит, подграф Ψ на множестве вершин степени 23 в Ω является кликой. Теперь
для двух вершин a, b ∈ Ψ подграф Ω содержит a, b, 11 вершин из [a] ∩ [b], по 11 вершин из [a] − [b], [b] − [a]
и 9 вершин вне a⊥ ∪ b⊥ .
Если a ∈ Ψ, то число ребер между Ω(a) и Ω2 (a) равно 120 = 11m + 4(23 − m), поэтому m = 4 и |Ψ| = 2, 4.
Заметим, что вершина из Γ − Ω смежна не более чем с 6 вершинами из Ω, поэтому число ребер между Ω и
10
Γ − Ω, деленное на 7, не больше 66. С другой стороны, это число не меньше 40 · 2 + 4, противоречие. Лемма
доказана.
Из лемм 3–5 следует теорема 1.
3 Автоморфизмы графа с параметрами (121, 30, 11, 6)
В этом параграфе предполагается, что Γ — дистанционно регулярный граф с массивом пересечений
{121, 90, 1; 1, 30, 121} и спектром 1211 , 11183 , −1121 , −11183 , G = Aut(Γ), g — элемент простого порядка p из
G и Ω = Fix(g) пересекает t антиподальных классов по s вершинам.
Пусть F — антиподальный класс, содержащий вершину a ∈ Ω, F ∩ Ω = {a, a2 , ..., as }, b ∈ Ω(a). Через
F (x) будем обозначать антиподальный класс, содержащий вершину x.
Лемма 6. Если ψ — мономиальное представление группы G в GL(488, C), χ1 — характер проекции ψ
на подпространство собственных векторов размерности 183, отвечающих собственному значению 11, χ2
— характер проекции ψ на подпространство размерности 121, то χ1 (g) = (17α0 (g)+2α1 (g)−5α3 (g))/44−
61/11, χ2 (g) = (α0 (g) + α3 (g))/4 − 1. Далее, χ1 (g) − 183 и χ2 (g) − 121 делятся на p.
Доказательство. Имеем
1 1 1 1
183 183/11 −61/11 −61
Q=
.
121 −1 −1 121
183 −183/11 61/11 −61
Поэтому χ1 (g) = (3α0 (g)+3α1 (g)/11−α2 (g)/11−α3 (g))/8. Подставляя α2 (g) = 488−α0 (g)−α1 (g)−α3 (g),
получим χ1 (g) = (17α0 (g) + 2α1 (g) − 5α3 (g))/44 − 61/11.
Аналогично, χ2 (g) = (121α0 (g) − α1 (g) − α2 (g) + 121α3 (g))/488. Подставляя α1 (g) + α2 (g) = 488 − α0 (g) −
α3 (g), получим χ2 (g) = (α0 (g) + α3 (g))/4 − 1.
Остальные утверждения леммы следуют из [3, лемма 1]. Лемма доказана.
Лемма 7. Выполняются следующие утверждения:
(1) если Ω — пустой граф, то либо p = 61, α1 (g) = 122 и α2 (g) = 366, либо p = 2, α3 (g) = 8l,
α1 (g) = 20l + 12 + 44m и α2 (g) = 476 − 28l − 44m, l 6 61 и 7l + 11m 6 119;
(2) если Ω — антиподальный класс, то p = 11, α1 (g) = 22l;
(3) если Ω — клика, то p = 3, t = 2, 5, 8, 11.
Доказательство. Пусть Ω — пустой граф и αi (g) = pwi для i > 0. Так как v = 61 · 8, то p ∈ {2, 61}.
Пусть p = 61. Тогда α3 (g) = 0 и χ1 (g) = 61(w1 − 2)/22. Отсюда w1 = 22l + 2, α1 (g) = 122 и α2 (g) = 366.
Пусть p = 2. Тогда χ2 (g) = α3 (g)/4 − 1, α3 (g) = 8l и число χ1 (g) = (w1 − 10l − 61)/11 нечетно. Поэтому
w1 = 10l + 6 + 22m и α1 (g) = 20l + 12 + 44m и α2 (g) = 476 − 28l − 44m. В случае α3 (g) = 488 имеем
χ1 (g) = −61.
Пусть Ω — антиподальный класс. Тогда p делит 121, поэтому p = 11. Далее, χ1 (g) = (α1 (g) − 88)/22 и
α1 (g) = 22l.
Если Ω — клика, то p = 3 делит 122 − t, поэтому t = 2, 5, 8, 11. Лемма доказана.
В леммах 8–9 предполагается, что t > 1, s > 1.
Лемма 8. Выполняются следующие утверждения:
(1) если p > 11, то либо p = 23 и Ω — дистанционно регулярный граф с массивом пересече-
ний {29, 21, 1; 1, 7, 29}, либо p = 13 и Ω — дистанционно регулярный граф с массивом пересечений
{17, 12, 1; 1, 4, 17};
(2) если p = 7, то t = 10, 17, 24 и в случае t = 10 подграф Ω является дистанционно регулярным с
массивом пересечений {9, 6, 1; 1, 2, 9};
(3) если p = 5, то t = 2, 7, 12, 17, 22, 27 и в случае t = 7 подграф Ω является объединением четырех
изолированных 7-клик;
(4) если p = 3, то t = 3l + 2, l 6 9 и в случае t = 5 подграф Ω является объединением четырех
изолированных 5-клик.
Доказательство. Если s = 4, то каждая вершина из Γ − Ω смежна точно с t вершинами из Ω.
11
Пусть p > 3, α1 (g) = pw1 . Тогда s = 4, α3 (g) = 0, |Ω| = 4t, Ω — регулярный граф степени t − 1 и p делит
122 − t.
Если p > 29, то Ω — дистанционно регулярный граф с массивом пересечений {t − 1, t − 32, 1; 1, 30, t − 1},
противоречие.
Пусть p = 29. Так как p делит 122 − t, то t = 6, подграф Ω(b) содержит 2 вершины из a⊥ и по вер-
шине из [a2 ], ..., [a4 ]. Отсюда Ω — дистанционно регулярный граф с массивом пересечений {5, 3, 1; 1, 1, 5},
противоречие.
Пусть p = 23. Так как p делит 122−t, то t = 7, 30, подграф Ω(b) содержит 8 вершины из a⊥ и по 7 вершин
из [a2 ], ..., [a4 ]. Отсюда Ω — дистанционно регулярный граф с массивом пересечений {29, 21, 1; 1, 7, 29}.
Пусть p = 19. Так как p делит 122 − t, то t = 8, 27, подграф Ω(b) содержит 12 вершин из a⊥ и по 11
вершин из [a2 ], ..., [a4 ], противоречие.
Пусть p = 17. Так как p делит 122 − t, то t = 3, 20, подграф Ω(b) содержит 14 вершин из a⊥ и по 13
вершин из [a2 ], ..., [a4 ], противоречие.
Пусть p = 13. Так как p делит 122−t, то t = 5, 18, подграф Ω(b) содержит 5 вершин из a⊥ и по 4 вершины
из [a2 ], ..., [a4 ]. Отсюда Ω — дистанционно регулярный граф с массивом пересечений {17, 12, 1; 1, 4, 17}.
Пусть p = 11. Так как p делит 122 − t, то t = 12, 23, подграф Ω(b) содержит 9 вершин из a⊥ и по 8
вершин из [a2 ], ..., [a4 ], противоречие.
Пусть p = 7. Так как p делит 122 − t, то t = 3, 10, 17, 24, подграф Ω(b) содержит 3 вершины из a⊥ и по 2
вершины из [a2 ], ..., [a4 ], поэтому в случае t = 10 подграф Ω является дистанционно регулярным с массивом
пересечений {9, 6, 1; 1, 2, 9}.
Пусть p = 5. Так как p делит 122 − t, то t = 2, 7, 12, 17, 22, 27. В случае t = 7 подграф Ω является
объединением изолированных 7-клик и, быть может, графа ∆ без треугольников. Пусть ∆(a) = {b1 , ..., b6 }.
Без ограничения общности, ∆(bi ) содержит 5 вершин из [ai+1 ]. Противоречие с тем, что вершина из ∆(b1 )∩
[a2 ] должна быть смежна с 5 вершинами из ∆(a).
Пусть p = 3. Тогда s = 4 и α3 (g) = 0. Так как 3 делит 122 − t, то t = 3l + 2, l 6 9.
В случае t = 5 подграф Ω является объединением изолированных 5-клик и, быть может, графа ∆ без
треугольников. Пусть ∆(a) = {b1 , ..., b4 }. Без ограничения общности, ∆(bi ) содержит 3 вершины из [ai+1 ].
Противоречие с тем, что вершина из ∆(b1 ) ∩ [a2 ] должна быть смежна с 3 вершинами из ∆(a).
Лемма 9. Если p = 2, то каждая вершина из Γ − Ω смежна с четным числом вершин из Ω и либо
s = 2, t 6 60, либо s = 4, t 6 30.
Доказательство. Пусть p = 2. Тогда s ∈ {2, 4} и t четно. Заметим, что для любых двух вершин a, b ∈ Ω
имеем |Ω(a) ∩ [b]| ∈ {0, 2, ..., 30}, любая вершина из Γ − Ω смежна с четным числом вершин из Ω.
Так как α3 (g) = t(4 − s), то χ2 (g) = t − 1, t четно, α1 (g) + α2 (g) = 488 − 4t, число χ1 (g) = (17st + 2α1 (g)−
−5t(4 − s))/44 − 61/11 = ((11st + α1 (g))/2 − 5t − 61)/11 нечетно.
Если s = 2, то число ребер между Ω и Γ − Ω равно 2t(122 − t), но не больше 120(122 − t), поэтому t 6 60.
Если s = 4, то t 6 30. Лемма доказана.
Из лемм 7–9 следует теорема 2.
4 Вершинно симметричный случай
Пусть группа G действует транзитивно на множестве вершин графа Γ. Тогда для антиподального класса
F , содержащего вершину a ∈ Γ, подгруппа H = G{F } имеет индекс 122 в G и |H : Ha | = 4. Из теоремы 2
следует, что {2, 61} ⊆ π(G) ⊆ {2, 3, 5, 7, 11, 13, 23, 61} и |G| не делится на 132 и на 113 .
Лемма 10. Выполняются следующие утверждения:
(1) если f — элемент порядка 61 из G, g — элемент простого порядка p 6= 61 из CG (f ), то p = 2 и
α3 (g) = 488;
(2) S(G) = O2 (G) и |O2 (G)| делит 4;
(3) цоколь T̄ группы Ḡ = G/O2 (G) изоморфен L2 (121).
Доказательство. Допустим, что g — элемент простого порядка p 6= 61 из CG (f ). Так как f действует
без неподвижных точек на Ω, то, ввиду теоремы 2, Ω — пустой граф, α1 (f ) = 122, p = 2 и числа α3 (g) = 8l,
α1 (g) = 20l + 12 + 44m, α2 (g) = 476 − 28l − 44m делятся на 61. Если l = 0, то 3 + 11m делится на 61,
противоречие. Значит, l = 61.
12
Заметим, что 236 − 1 не делится на 61.
Пусть Q = O2 (G) 6= 1. Тогда порядки Q-орбит на множестве антиподальных классов делят 2. Если
порядок некоторой Q-орбиты равен 1, то Q фиксирует каждый антиподальный класс и |Q| делит 4, проти-
воречие с утверждением (1). Теперь подгруппа Q0 индекса 2 из Q фиксирует F и подгруппа Q1 индекса 16
из Q фиксирует F поточечно. Так как k = 121, то Q1 фиксирует вершину b из [a]. Подгруппа Q2 индекса
16 из Q1 фиксирует a, b и по 6 вершин из [b] ∩ [x] для x ∈ F . Аналогично, подгруппа Q3 индекса 16 из Q1
фиксирует a, b и по 6 вершин из [a] ∩ [y] для y ∈ F (b). Теперь любая инволюция из Q2 ∩ Q3 фиксирует не
менее 2 + 6 + 36 антиподальных классов и по теореме 2 имеем Q2 ∩ Q3 = 1. Отсюда |Q| 6 36, противоречие
с действием элемента порядка 61 на Q. Из утверждения (1) следует, что S(G) = O2 (G) и |O2 (G)| делит 4.
Пусть T̄ — цоколь группы Ḡ = G/O2 (G). Ввиду теоремы из [4], группа T̄ изоморфна L2 (35 ), U5 (3),
L2 (112 ), U6 (3).
Так как T̄ содержит подгруппу индекса, делящего 122, то группа T̄ изоморфна L2 (121) (и T̄{F } —
расширение группы порядка 121 с помощью группы порядка 60). Лемма доказана.
Докажем следствие. Ввиду леммы 10, подгруппа T изоморфна L2 (121), SL2 (121), Z2 × L2 (121),
Z2 × SL2 (121) или K × L2 (121), где |K| = 4.
Пусть подгруппа H изоморфна SL2 (121) или L2 (121). Тогда наименьший индекс в H её максимальной
подгруппы равен 122, поэтому H действует транзитивно на множестве антиподальных классов. Понятно,
что H — нормальная подгруппа, поэтому G действует на множестве H-орбит, и, значит, H-орбиты являются
изоморфными подграфами порядка не меньше 122. Есть такие варианты:
1. Четыре H-орбиты порядка 122, на которых H действует 2-транзитивно. Нетрудно понять, что это
невозможно.
2. Две H-орбиты порядка 244. Стабилизатор антиподального класса H{F } и стабилизатор вершины
Ha находятся однозначно с точностью до сопряжения, причём Z(H) 6 Ha . Орбиты Ha , лежащие в той
же H-орбите, что и a, имеют порядки 1, 121, 121, 1. Понятно, что две неподвижные относительно Ha
вершины – это пара антиподов. Поэтому окрестность a в соответствующей H-орбите либо пуста, либо
содержит 121 вершину. Первое невозможно потому, что граф не двудольный. Второе невозможно потому,
что граф связный.
3. H действует транзитивно. Тогда стабилизатор антиподального класса и стабилизатор вершины нахо-
дятся однозначно с точностью до сопряжения (при этом Z(H) 6 Ha ) и существует единственный дистан-
ционно регулярный граф с заданным массивом, допускающий H.
Следствие доказано.
Работа выполнена при поддержке РНФ, проект 14-11-00061 (теорема 2 и следствие) и соглашения между
Министерством образования и науки Российской Федерации и Уральским федеральным университетом от
27.08.2013, № 02.A03.21.0006 (теорема 1).
Список литературы
[1] A. A. Makhnev, M. S. Samoilenko. On distance-regular covers of cliques with strongly regular local
subgraphs. Tranzactions of 46 International school-conference, Yekaterinburg, 13–18, 2015.
[2] A. E. Brouwer, A. M. Cohen, A. Neumaier. Distance-Regular Graphs. Springer-Verlag, 1989.
[3] A. L. Gavrilyuk, A. A. Makhnev. On automorphisms of distance-regular graph with the intersection array
{56, 45, 1; 1, 9, 56}. Doklady RAN, 432(5):300–304, 2010.
[4] A. V. Zavarnitsine. Finite simple groups with narrow prime spectrum. Sibirean electr. Math. Reports, 6:1–12,
2009.
13
Automorphisms of distance-regular graph with intersection array
{121, 90, 1; 1, 30, 121}
Konstantin S. Efimov2 , Alexander A. Makhnev1
1 – Krasovskii Institute of Mathematics and Mechanics (Yekaterinburg, Russia)
2 – Ural Federal University (Yekaterinburg, Russia)
Keywords: distance-regular graph, automorphism.
A.A. Makhnev and M.S. Samoilenko determined parameters of strongly regular graphs with at most 1000
vertices, which may be local subgraphs in antipodal distance-regular graph of diameter 3 with λ = µ. They
suggested the program of investigation of antipodal distance-regular graphs of diameter 3 with λ = µ, in which
local subgraphs are strongly regular with at most 1000 vertices. In this paper, we consider distance-regular graph
with intersection array {121, 90, 1; 1, 30, 121}. It is proved that vertex-symmetric graph with intersection array
{121, 90, 1; 1, 30, 121} is arc-transitive with the socle of automorphism group isomorphic Z2 × L2 (121).
14