Об автоморфизмах сильно регулярного графа с параметрами (320, 99, 18, 36)

Автор: Махнев Александр Алексеевич, Кагазежева Алена Мухамедовна

Журнал: Владикавказский математический журнал @vmj-ru

Статья в выпуске: 2 т.15, 2013 года.

Бесплатный доступ

Псевдогеометрический граф для $pG_2(5,32)$ имеет сильно регулярные подграфы --- окрестность вершины (псевдогеометрический граф для $GQ(4,8)$) и вторую окрестность вершины (граф с параметрами $(320,99,18,36)$). В работе найдены возможные порядки и подграфы неподвижных точек автоморфизмов сильно регулярного графа с параметрами $(320,99,18,36)$.

Сильно регулярный граф, автоморфизм

Короткий адрес: https://sciup.org/14318422

IDR: 14318422

Текст научной статьи Об автоморфизмах сильно регулярного графа с параметрами (320, 99, 18, 36)

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

Через k a обозначим степень вершины а, т. е. число вершин в [а]. Граф Г называется регулярным степени k, если k a = k для любой вершины а из Г. Граф Г называется сильно регулярным с параметрами (v,k, А,^), если Г — регулярный граф степени k на v вершинах, в котором каждое ребро лежит точно в λ треугольниках и для любых двух несмежных вершин а,Ь верно равенство |[а] П [b]| = ^.

Через K m x n обозначим полный двудольный граф с m долями порядка n. Граф на множестве пар X х Y называется p х q-решеткой, если | X | = p, | Y | = q, а пары (xi,yi) и (x 2 , y 2 ) смежны тогда и только тогда, когда x 1 = х 2 или y 1 = y 2 .

Пусть Г — псевдогеометрический граф для pG 2 (5, 32), а — вершина графа Г. Тогда Г имеет собственные значения k = 165, r = 3, s = - 33 и достигается равенство во втором условии Крейна

(s + 1)(k + s + 2rs) 6 (k + s)(r + 1)2.

Поэтому [а] является сильно регулярным графом с параметрами (165, 36, 3, 9) (псевдогеометрический граф для GQ(4, 8)), и Г2(а ) — сильно регулярный граф с параметрами (320, 99,18, 36) (см. [1, теорема 8.15]). В работе найдены возможные порядки и подграфы неподвижных точек автоморфизмов сильно регулярного графа с параметрами (320, 99, 18, 36).

  • (0 2013 Махнев А. А., Кагазежева А. М.

  • 1    Работа выполнена при финансовой поддержке Российского фонда фундаментальных исследований, проекты № 12-01-00012, № 12-01-91155-ГФЕН.

Теорема 1. Пусть Γ является сильно регулярным графом с параметрами (320, 99, 18, 36), G = Aut(G), g — элемент простого порядка p из G, Ω = Fix(g). Тогда π(G) ⊆ { 2, 3, 5, 7, 11 } и выполняется одно из следующих утверждений:

  • (1)    Ω — пустой граф, p = 5 и α1(g) ∈ { 0, 120 } или p = 2 и α1(g) ∈ { 0, 48, 96, 144, 192, 240, 288 } ;

  • (2)    Ω является одновершинным графом, p = 11 и α1 (g) = 66;

  • (3)    Ω является m-кокликой, p = 3, m = 3t + 2, 3 6 t 6 14 и α1 (g) - 9m - 6 делится на 72;

  • (4)    Ω — объединение l изолированных ребер, 2 6 l 6 29, p = 2 и α1 (g) - 6l делится на 48;

  • (5)    p = 11 и либо

  • (i)    | | = 67 и α1 (g) = 33, либо

  • (ii)    | | = 78 и α1 (g) = 66, либо

  • (iii)    | | = 89 и α1(g) = 99;

  • (6)    p = 7 и либо

  • (i)    Q = Кз х 4 и a 1 (g) E { 84, 252 } , либо

  • (ii)    | | = 7s + 5 , 2 6 s 6 10 , α1(g) = 21r и s - r + 3 делится на 8 , либо

  • (iii)    | | = 96 и α1(g) = 0 ;

  • (7)    p = 5 и либо

  • (i)    | | = 90 , α1 (g) = 90 , на Γ - имеются 36 пятиугольных h g i -орбит и 10 кокликовых;

  • (ii)    | | = 85 , α1 (g) = 15 , на Γ - имеются 6 пятиугольных h g i -орбит и 41 кокли-ковая;

  • (iii)    | | = 80 , α1 (g ) ∈ { 0, 120 } , на Γ - имеются 48 пятиугольных h g i -орбит или 48 кокликовых;

  • (iv)    | | = 5s , 3 6 s 6 15 , α1(g) = 120r + 15s , r ∈ {- 2, - 1, 0, 1, 2 } ;

  • (8)    p = 3 , | | = 3t + 2 , не содержит вершин степени | | - 2 и либо

  • (i)    Ω является объединением двух изолированных вершин и K 3 , 3 -подграфа, α1 (g) делится на 72 , либо

  • (ii)    | | = 80 или | | = 140 и α1 (g) = 0 , либо

  • (iii)    | | = 3t+2 , 3 6 t 6 25 , α1(g) = 72s+9t+54 и s ∈ {- 3, - 2,...,4 } ;

  • (9)    p = 2 и либо

  • (i)    Ω — куб и α1 (g)/24 — нечетное натуральное число, либо

  • (ii)    α1 (g) = 0 , | | = 16s , s ∈ { 1, 2, . . . , 9 } , либо

  • (iii)    α1 (g) 6 = 0 , | | = 2t , 5 6 t 6 70 и α1 (g) = 48r + 6t .

  • 1.    Предварительные результаты

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

Лемма 1. Пусть Γ — сильно регулярный граф с параметрами (v, k, λ, µ) , — индуцированный подграф с N вершинами, M ребрами и степенями вершин d1 , . . . , d N . Тогда

(v N ) (kN 2M ) + AM + ^^( 2 ^ - M) - ^^ (2 ) = xo + ^^ ( 2 )x i

и ixi 6     xi     i2xi, где xi — число вершин из Γ - ∆, смежных точно с i вершинами из ∆.

C Подсчитав число вершин в Г А, число ребер между А и Г А и число 2-путей с концами в А и средней вершиной в Г А, получим равенства v N = Р X i , kN 2M = P ix , и XM + ^(( N ) M ) E , N=1 (*) = P (2)x i .

Вычитая второе равенство из суммы первого и третьего, получим равенство из заключения леммы.

Квадратный трехчлен ^(i x ) 2 X i = P i2X i 2x^ ix i + X2 P X i неотрицателен. Поэтому дискриминант квадратного трехчлена (Р ix i ) 2 Px i Pi 2 X i неположителен. B

Лемма 2 [2, лемма 2] . Пусть Г является сильно регулярным графом с целыми собственными значениями, g — автоморфизм графа Г простого порядка р, и х — характер проекции мономиального представления на подпространство размерности m собственных векторов матрицы смежности графа, отвечающих неглавному собственному значению. Тогда a i (g) = a i (g l ) для любого l, не кратного р и m x(g), делится на р.

Лемма 3. Пусть Г является сильно регулярным графом с параметрами (320, 99,18, 36). Тогда выполняются следующие утверждения:

  • (1)    порядок коклики в Г не больше 44 и порядок клики в Г не больше 4;

  • (2)    если Г содержит регулярный подграф А степени d на w вершинах, то 21 6 d (99 d)w/(320 w) 6 3, причем в случае равенства каждая вершина из Г А смежна точно с (99 d)w/(320 w) вершинами из А;

  • (3)    значение характера, полученного при проектировании мономиального представления на подпространство размерности 44, на элементе g Е Aut(P) равно X2(g) = (3ao(g) ai(g))/24 + 4, и 44 X2(g) делится на р.

C Ввиду границы Цветковича [3] порядок коклики в Г не больше 44. Ввиду границы Хофмана для клик порядок клики в Г не больше 5. Пусть L является 5-кликой из Г, X i — множество вершин из Г L, смежных точно с i вершинами из L, x i = | X i | . Тогда P X i = 315, P ix i = 475, P (2)x i = 150, поэтому x o + P (i21)x i = 10, противоречие.

Если Г содержит регулярный подграф А степени d на w вершинах, то по лемме 1.2 из [4] имеем 21 6 d (99 d)w/(320 w) 6 3.

По лемме 2.6 из [4] значение характера, полученного при проектировании мономиального представления на подпространство размерности 44, на элементе g Е Aut(P) равно X2(g) = (3ao(g) ai(g))/24 + 4. По лемме 2 число 44 Х2(g) делится на р. в

Лемма 4. Пусть Г является сильно регулярным графом с параметрами (320, 99,18, 36), U — трехвершинный подграф из Г, Y i — множество вершин из Г U, смежных точно с i вершинами из U, y i = | Y i | . Тогда выполняются следующие утверждения:

  • (1)    для двух вершин u, w подграф Г 2 (u) П Г 2 (w) содержит 156 вершин, если u, w не смежны; 140 вершин, если u, w смежны;

  • (2)    число у о + уз равно 128, если U является кокликой; равно 77 , если U является кликой;

  • (3)    число у о + уз равно 95, если U является 2-путем; равно 112, если U — объединение изолированной вершины и ребра.

  • 2.    Автоморфизмы графа с параметрами (320, 99,18,36)

C Для двух несмежных вершин u, w граф Г содержит 36 вершин из [u] П [w], по 63 вершины из [u] [w], [w] [u] и 156 вершин из Г2(u) П Г2(u g ). Для смежных вершин u, w граф Г содержит 18 вершин из [u] П [w], по 80 вершин из [u] w р [w] u p и 140 вершин из Г2(u) П Г2(u g ).

Если U является 3-кокликой, то Г содержит 3(36 уз) вершин из Y2, 3(27+уз) вершин из Yi и 128 у з вершин из Yo , поэтому уо + у з = 128. Аналогично доказывается, что уо + уз = 77, если U является кликой.

Если U является геодезическим 2-путем U1U2из, то Y2 содержит 35 уз вершин из [ui] П [из] и по 18 уз вершин из [u i ] П [u 2 ], [u 2 ] П [из], Y i содержит 61 + уз вершин из [и 2 ] и по 45 + уз вершин из [ui], [из], Y0 содержит 95 уз вершин, поэтому уо + уз = 95.

Если U объединение изолированной вершины u1 и ребра { u2 , u3 } , то Y2 содержит 18 уз вершин из [и 2 ] П [из] и по 36 уз вершин из [ui] П [u 2 ], [ui] П [из], Y i содержит 27 + у з вершин из [ui] и по 44 + у з вершин из [и2], [из], Y o содержит 112 у з вершин, поэтому уо + у з = 112. B

До конца работы будем предполагать, что Г является сильно регулярным графом с параметрами (320, 99,18, 36). Пусть g — автоморфизм простого порядка p графа Г и fi = Fix(g).

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

  • (1)    если fi — пустой граф, то либо p = 5 и ai(g) G { 0,120 } , либо p = 2 и ai(g) 6 { 0,48, 96,144,192, 240,288 } ;

  • (2)    если fi является n-кликой, то n = 1, p = 11 и ai(g) = 66;

  • (3)    если fi является m-кокликой, m > 2, то p = 3, m = 3t+2, 3 6 t 6 14 и ai(g) 9m 6 делится на 72;

  • (4)    если fi — объединение l > 2 изолированных клик, но fi не является кокликой, то p = 2, fi является объединением изолированных ребер, 1 6 29 и a i (g) 61 делится на 48.

  • <1    Пусть fi — пустой граф. Тогда p G { 2, 5 } . Если p = 5, то по целочисленности х2(g) число ai(g) делится на 24. Но в случае ai (g) = 240 на Г возникает кликовая h g i орбита длины 5, противоречие с леммой 3.

Если p = 2, то число 44 X2(g) = 40 + ai(g)/24 четно, поэтому a i (g) делится на 48. Утверждение (1) доказано.

Пусть X i — множество вершин из Г fi, смежных точно с i вершинами из fi, x i = | X i | .

Пусть fi является n-кликой. Тогда n 6 4. Если n = 1, то p делит 99 и 220, поэтому p = 11. По целочисленности X2(g) число ai(g) 3 делится на 24, поэтому ai(g) = 99.

Если n > 2, то p делит 80 и 140, поэтому p G { 2, 5 } . Но в случае p = 5 число 18 (n 2) делится на 5, противоречие. Поэтому p = 2 и n G { 2,4 } . Так как каждая вершина из Г fi смежна с четным числом вершин из fi, то n = 4. Отсюда xo + x 2 + х 4 = 316, x 2 + 2x4 = 192 и x 2 + 6x4 = 96, противоречие. Утверждение (2) доказано.

Пусть fi является m-кокликой, m > 2. Тогда p делит 36 и 63, поэтому p = 3 и m = 3t + 2. По целочисленности X2(g) число ai(g) 9m 6 делится на 24, поэтому ai(g) = 24r + 9m + 6, X2(g) = r + 4. По лемме 3 число 44 X2(g) = r делится на 3. Утверждение (3) доказано.

Пусть fi содержит ребро и является объединением 1 изолированных клик, 1 > 2. Тогда p делит 80 и 36, поэтому p = 2. Если fi содержит изолированную вершину, то p делит 99, противоречие. Пусть fi содержит изолированную 4-клику L, Y i — множество вершин из Г L, смежных точно с i вершинами из L, y i = | Y). Тогда уо + у 2 =316, 2у2 =4 96 = 384, у 2 = 6 16 = 96, противоречие. Итак, fi является объединением 1 изолированных ребер, и по лемме 3 имеем 1 6 29. По целочисленности X2(g) число ai (g) 61 делится на 24, поэтому ai(g) = 24r + 61, X2(g) = r + 4. По лемме 3 число 44 х2 (g) = 40 + r четно. B

В леммах 6-8 предполагается, что fi содержит геодезический 2-путь bac.

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

  • (1)    Γ не содержит собственных сильно регулярных подграфов с λ = 18, µ = 36 и | | не больше 156 (не больше 140, если α1 (g) 6 = 0);

  • (2)    если p > 2 и | | > 95, то α1 (g) = 0;

  • (3)    если α1 (g) = 0, то α0 (g) делится на 8, а по лемме 3 число 40 - α0 (g)/8 делится на p;

  • (4)    для любой вершины a Ω подграф [a] не содержится в Ω.

C Пусть Γ содержит собственный сильно регулярный подграф ∆ с параметрами (v 0 , k 0 , 18, 36). Тогда 4(k 0 - 36) + 18 2 = n 2 для некоторого натурального числа n. Отсюда n ∈ { 18, 20, 22 } и k 0 ∈ { 36, 55, 76 } соответственно. Но в последнем случае 36 не делит k 0 (k 0 - 19), а во втором ∆ имеет собственные значения 1, - 19 и кратность 1 равна 18 · 55 · 74/(20 · 36), противоречие. Значит, n = 18 и ∆ = K 2×18, получили противоречие с леммой 3. Теперь утверждение (1) следует из леммы 4.

Пусть U — трехвершинный подграф из u h g i , Y i — множество вершин из Γ - U, смежных точно с i вершинами из U, y i = | Y i | . Из леммы 4 следует, что | | 6 95, если u h g i содержит геодезический 2-путь, и | | 6 77, если u h g i содержит 3-клику. В случае | | > 95 подграф u h g i не содержит геодезических 2-путей и является кокликой. Утверждение (2) доказано.

Пусть α1 (g) = 0. Тогда по целочисленности χ2 (g) число α0 (g) делится на 8, а по лемме 3 число 40 - α0 (g)/8 делится на p. Утверждение (3) доказано.

Пусть для некоторой вершины a Ω имеем [a] Ω. Тогда для u Γ - Ω получим | [u] | = 36 и u h g i является кокликой, поэтому α1 (g) = 0, и по утверждению (3) имеем | | > 104. Теперь для b - a подграф [b] не пересекает Γ - Ω, поэтому [u] [b] содержится в Ω и совпадает с [a] [u] = [a] [b]. Противоречие с тем, что любые две вершины из [u] - Ω) смежны с u и с 36 вершинами из [a] [b]. B

Лемма 7. Если p > 3, то | | 6 max { 95, 131 - p } . Далее, p 6 17.

C Если p > 36, то Ω — сильно регулярный подграф с параметрами (v 0 , k 0 , 18, 36), противоречие с леммой 6. Если p > 17, то Ω — подграф с λΩ = 18.

Пусть p > 3. Если | | > 95, то по лемме 6 любая орбита u h g i является кокликой. Поэтому для любой 3-коклики U из u h g i подграф X0 (U) X3(U) содержит Ω и p - 3 вершин из u h g i - U. Значит, | | 6 128 - (p - 3).

Пусть p = 31. Тогда степень вершины в графе Ω равна 37 или 68, | | ∈ { 72, 103 } и µΩ ∈ { 5, 36 } . Если | | = 72, то Ω — регулярный граф степени 37 (иначе Ω содержит по крайней мере 2 вершины a, b степени 68 и | Ω(a) Ω(b) | > 72). В этом случае Ω — сильно регулярный граф с параметрами (72, 37, 18, 36), получили противоречие. Значит, | | = 103. По целочисленности χ2 (g) число α1(g) - 3 делится на 24, — противоречие.

Пусть p = 29. Тогда степень вершины в графе Ω равна 41 или 70, | | ∈ { 59, 88 } и µ ∈ { 7, 36 } . Если | | = 59, то Ω — регулярный граф степени 41, получили противоречие. Значит, | | = 88. По целочисленности χ2 (g) число α1 (g) делится на 24, противоречие.

Пусть p = 23. Тогда степень вершины в графе Ω равна 30, 53 или 76, | | ∈ { 44, 67, 90 } и µΩ ∈ { 13, 36 } . Если | | = 44, то Ω — сильно регулярный граф с параметрами (44, 30, 18, 13), получили противоречие с тем, что 13 не делит 30 · 11. Если | | = 67, то Ω — регулярный граф степени 30 и число ребер между Ω(a) и Ω - a равно 30 · 11, но не меньше 36 · 13, — противоречие. Значит, | | = 90. По целочисленности χ2(g) число α1 (g) - 6 делится на 24, — противоречие.

Пусть p = 19. Тогда степень вершины в графе Ω равна 23, 42, 61 или 80, | | ∈

{ 54, 73, 92 } и ^ q G { 17, 36 } . Если | Q | = 54, то по целочисленности Х2(g) число ai(g) 6 делится на 24, получили противоречие.

Если | Q | = 92, то по целочисленности Х2(g) число a i (g) 12 делится на 24, поэтому a i (g) = 228. Противоречие с тем, что каждая h g i -орбита длины 19 является кликой.

Пусть | Q | =73. Тогда степень каждой вершины в Q равна 23 или 42. Допустим, что Q содержит вершину а степени 23. Тогда число ребер между Q(a) и Q а ^ не больше 23 ^ 23+18 ^ 17, но не меньше 49 - 17, — противоречие. Значит, Q — регулярный граф степени 42 на 73 вершинах. Тогда число ребер между Q(a) и Q а ^ равно 23 42 = 36x + 17(30 x). Отсюда x = 24 и Q а ^ содержит 6 вершин степени 25. Для двух смежных вершин d, е степени 25 в Q а ^ подграф Q(d) П [e] содержит не менее 20 вершин из Q а ^ , — противоречие. B

Лемма 8. Верно неравенство p = 17.

C Пусть p = 17. Тогда степень вершины в графе Q равна 14, 31, 48, 65 или 82, | Q | G { 31,48, 65, 82 } , A q G { 1,18 } и G { 2,19, 36 } .

Если | Q | = 31, то Q — сильно регулярный граф с параметрами (31,14,1, 2), получили противоречие с тем, что 31 14 1 не делится на 3.

Если | Q | = 48, то по целочисленности X2(g) число a i (g) делится на 24, — противоречие.

Если | Q | = 65, то по целочисленности X2(g) число ai(g) 3 делится на 24, поэтому a i (g) = 51. Далее, степень вершины в Q равна 14, 31 или 48. Допустим, что Q содержит вершину а степени 14. Тогда число ребер между Q(a) и Q а ^ равно 50, но не меньше 14 12, — противоречие. Значит, Q содержит вершину а степени 48. Тогда любая вершина из Q(a) имеет степень 31 в Q, и число ребер между Q(a) и Q а ^ равно 48 12, но не больше 16 36. Поэтому степень каждой вершины из Q а ± в Q равна 48, получили противоречие.

Если | Q | = 82, то по целочисленности X2(g) число ai(g) 6 делится на 24, поэтому ai(g) = 102. Далее, степень вершины в Q равна 31, 48 или 65. Допустим, что Q содержит вершину а степени 65. Тогда любая вершина из Q(a) имеет степень 31 в Q, и число ребер между Q(a) и Q а ^ равно 65 12, но не больше 16 36, — противоречие.

Если Q — регулярный граф степени 31 на 82 вершинах, то ввиду леммы 3 имеем 31 68 82/238 6 3, получили противоречие.

Значит, Q содержит вершину а степени 48. Пусть Q а ± содержит вершину е, смежную точно с двумя вершинами из Q(a). Тогда [е] содержит 29 вершин из Q а ^ , и для b G Q(a) П [е] подграф Q(b) П [е] содержит 0 или 1 вершину из [а] и от 9 до 12 вершин из Q а ^ , — противоречие.

Пусть Qo подграф из Q, индуцированный вершинами, имеющими степень 48 в Q, A = Qo(a), B = Qo а ± , Ao — множество вершин из Q(a), смежных с 29 вершинами из Q а ^ , B o — множество вершин из Q а ^ , смежных с 36 вершинами из Q(a). Тогда Ao и Bo являются кокликами и число ребер между Q(a) и Q а ^ равно 29x + 12(48 x) = 36y + 19(33 y), поэтому x = y + 3. Если c, d — две вершины из A, то Q(c) П [d] содержит от 25 до 29 вершин из Q а^, поэтому A = Ao и Q(a) — регулярный граф степени 18, содержащий x вершин из Qo .

Покажем, что если | Q(a) П [е] | = 19 для е G Q а ± , то степень е в Q равна 31. В противном случае Q содержит 19 вершин из [а] П [е], по 29 вершин из [а] [е], [е] [а] и 3 вершины f i , f 2 , f3 вне а ± U е ± . Ясно, что [а] П [е] состоит из вершин степени 31 в Q. Пусть Q(e) содержит j вершин bi,..., b j из B. Без ограничения общности j > x. Противоречие с тем, что x = y + 3.

Итак, Qo содержит у + 3 вершин из [а] и у вершин вне а \ получили противоречие с тем, что Qo(c) содержит у + 2 вершин для c Е Qo(a). B

Лемма 9. Число p не равно 13.

C Пусть p = 13. Тогда степень вершины в графе Q равна 21, 34, 47, 60, 73 или 86, | Q | е { 34,47, 60, 73, 86,112 } , A q Е { 5,18 } и Е { 10, 23, 36 } .

Если | Q | = 34, то Q — сильно регулярный граф с параметрами (34, 21,18,10), противоречие.

Пусть | Q | = 47. Тогда степень вершины в Q равна 21 или 34. По целочисленности Х2(g) число ai (g) + 3 делится на 24, поэтому ai(g) = 117. Если Q содержит вершину a степени 21, то число ребер между Q(a) и Q а ^ равно 250 = 15x + 2(21 x), поэтому x = 16. Пусть c i ,... ,С 5 — вершины из Q(a), смежные с парами вершин из Q а ^ . Так как Г не содержит 5-клик, то можно считать, что вершины ci, С2 не смежны, — противоречие с тем, что [ci] П [c 2 ] содержит не менее 17 вершин из Q(a). Значит, Q — регулярный граф степени 34, поэтому Q — сильно регулярный граф с параметрами (47, 34,18, 23), получили противоречие.

Если | Q | = 60, то по целочисленности X2(g) число a i (g) 12 делится на 24, поэтому ai(g) = 156. Далее, степень вершины в Q равна 21, 34 или 47. Если Q содержит вершину а степени 47, то число ребер между Q(a) и Q а ± равно 94 = 36x+23y+ 10(12 x у), — противоречие. Если Q содержит вершину а степени 21, то число ребер между Q(a) и Q а ^ равно 380 = 28x + 15у + 2(21 x у), поэтому 2x + у = 26 и 21 x у = x 5. Так как Q(a) содержит x вершин степени 5, то x четно. В случае x > 9 противоречие получается как и в предыдущем абзаце. Значит, x 6 8, Q(a) содержит 13 вершин степени 18, поэтому Q(a) содержит 4-клику, получили противоречие. Значит, Q — регулярный граф степени 34, и число ребер между Q(a) и Q а ^ равно 34 15 = 23x + 10(25 x), поэтому x = 20 и Q а ± содержит 5 вершин степени 24, образующих клику, — противоречие.

Если | Q | = 73, то | Г Q | = 13 19, по целочисленности X2(g) число a i (g) 3 делится на 24, поэтому ai(g) = 195. Для любой четверки индексов ii,..., i 4 Е { 1, 2,..., 6 } найдутся три h g i -орбиты длины 13, в которых вершина u смежна с u j для j Е { i i ,..., i 4 } . Ввиду леммы 1.5 из [5] каждая такая орбита содержит 4-клику и не попадает в окрестность никакой вершины из Q. Так как число четверок в { 1, 2,... , 6 } равно 15, то 45 орбит вида u h g i не попадают в окрестность никакой вершины из Q. Противоречие с тем, что число h g i -орбит длины 13 равно 19.

Если | Q | = 86, то по целочисленности X2(g) число ai(g) + 6 делится на 24, поэтому ai (g) = 306, — противоречие.

Если | Q | = 112, то | Г Q | = 13 16 и a i (g) = 0. Пусть U является 3-кокликой из u h g i . Тогда Xo(U) U X3 (U) содержит 112 вершин из Q, 10 вершин из u h g i и еще 6 вершин. Пусть w Е Г (Q U u h g i ). Если w смежна не более чем с 2 вершинами из u h g i , то Xo (U) содержит не менее 7 вершин из w h g i . Если w смежна точно с 3 вершинами из u h g i , то для U = [w] П u h g i подграф Xo (U) U X3 (U) содержит 7 вершин из w h g i . В обоих случаях имеем противоречие.

Допустим, что w смежна точно с 4 вершинами из u h g i . Тогда Xo(U) содержит вершину из w h g i . Поэтому для по крайней мере 9 орбит w h g i вершина w смежна по крайней мере с 5 вершинами из u h g i . Таким образом, число 3-лап с концевыми вершинами в u h g i и центральной вершиной в Г (u h g i U Q) не меньше 4 13 6 + 10 13 9 = 13 114. Число троек вершин в u h g i равно 13 22, поэтому некоторая 3-коклика U из u h g i попадает в окрестности 6 вершин из Г (u h g i U Q). Противоречие с тем, что Xo(U) содержит вершину из Г (u h g i U Q).

Теперь каждая вершина из Γ - (u h g i Ω) смежна по крайней мере с 5 вершинами из u h g i , число 3-лап с концевыми вершинами в u h g i и центральной вершиной в Γ - (u h g i Ω) не меньше 10 · 13 · 15. Противоречие с тем, что некоторая 3-коклика U из u h g i попадает в окрестности по крайней мере 7 вершин из Γ - (u h g i Ω). B

Лемма 10. Если p = 11, то верно одно из утверждений:

  • (1)    | | = 67 и α1(g) = 33;

  • (2)    | | = 78 и α1(g) =66;

  • (3)    | | = 89 и α1(g) =99.

C Пусть p = 11. Тогда степень вершины в графе Ω равна 11t, t ∈ { 2, 3, . . . , 8 } , | | ∈ { 34, 45, 56, 67, 78, 89 } , λΩ ∈ { 7, 18 } и µΩ ∈ { 3, 14, 25, 36 } . Заметим, что Ω не содержит вершин степени | | - 1. Если Ω содержит вершину a степени | | - 12, то Ω - a — регулярный граф степени 8 на 11 вершинах. Противоречие с тем, что Ω - a содержит 5-клику. Отсюда, в частности, | | 6 = 34.

Пусть | | = 45. По целочисленности χ2 (g) число α1 (g) + 9 делится на 24, поэтому α1 (g) = 231. Противоречие с тем, что на Γ - Ω имеется кликовая h g i -орбита.

Пусть | | = 56. По целочисленности χ2 (g) число α1 (g) делится на 24, поэтому α1 (g) = 264. Противоречие с тем, что на Γ - Ω имеется кликовая h g i -орбита.

Пусть | | = 67. Тогда степень вершины в Ω равна 22, 33 или 44. По целочисленности χ2 (g) число α1 (g) - 9 делится на 24, поэтому α1 (g) = 33.

Если | | = 78, то по целочисленности χ2 (g) число α1 (g) + 6 делится на 24, поэтому α1 (g) = 66. Далее, степень вершины в Ω равна 22, 33, 44 или 56.

Если | | = 89, то | Γ - | = 11 · 23, по целочисленности χ2 (g) число α1 (g) - 3 делится на 24, поэтому α1(g) = 99. B

Лемма 11. Если p = 7, то верно одно из утверждений:

  • (1)    Ω = K3 × 4 и α1(g) ∈ { 84, 252 } ;

  • (2)    | | = 7s + 5, 2 6 s 6 10, α1(g) = 21r и s - r + 3 делится на 8;

  • (3)    | | = 96 и α1(g) = 0.

  • 3.    Автоморфизмы малых порядков

C Пусть p = 7. Тогда степень вершины в графе Ω равна 7t + 1, t ∈ { 1, 2, . . . , 13 } , | | = 7s+5, s ∈ { 1,2,... ,11 } или s = 13, λΩ ∈ { 4, 11, 18 } и µΩ ∈ { 1, 8, 15, 22, 29, 36 } .

Пусть | | = 12. Тогда любая связная компонента графа Ω является одновершинным графом или сильно регулярным графом с параметрами (v 0 , 8, 4, 8). Поэтому Ω = K3×4 . По целочисленности χ2 (g) число α1 (g) - 12 делится на 24, поэтому α1(g) ∈ { 84, 252 } .

Пусть | | = 96. По лемме 6 имеем α1 (g) = 0.

Пусть | | = 7s + 5, 2 6 s 6 11. По целочисленности χ2 (g) число α1(g) + 3s + 9 делится на 24, поэтому α1(g) = 21r и s - r + 3 делится на 8.

Пусть | | = 82. Тогда h g i -орбиты длины 7 не содержат треугольников. Далее, r = 6 и α1 (g) = 126, поэтому найдутся две h g i -орбиты длины 7, являющиеся графами степени 4. Противоречие с тем, что такая орбита содержит треугольник. B

В этом параграфе предполагается, что Γ является сильно регулярным графом с параметрами (320, 99, 18, 36), g — автоморфизм простого порядка p графа Γ, и подграф Ω = Fix(g) содержит геодезический 2-путь.

Лемма 12. Пусть p = 5 и | | = 5s. Тогда выполняются следующие утверждения:

  • (1)    | | = 90, α1 (g) = 90, на Γ - Ω имеются 36 пятиугольных h g i -орбит и 10 кокликовых;

  • (2)    | | = 85, α1 (g) = 15, на Γ - Ω имеются 6 пятиугольных h g i -орбит и 41 кокликовая;

  • (3)    | Q | = 80, ai(g) G { 0,120 } , на Г Q имеются 48 пятиугольных hg'i-орбит или 48 кокликовых;

  • (4)    | Q | = 5s, 3 6 s 6 15, ai(g) = 120r + 15s, r G {— 2, 1, 0,1, 2 } .

C Пусть p = 5. Тогда степень вершины в графе Q равна 5t + 4, t G { 1, 2,..., 18 } , | Q | = 5s, s G { 3,4,... , 19 } или s = 24, A q G { 3, 8,13,18 } и ^ Q G { 1, 6,11,16, 21, 26, 31, 36 } .

Пусть Q содержит вершину a степени 9. Тогда Q(a) содержит вершину c степени 8. Поэтому либо Q(a) — сумма 3-клики и 6-коклики, либо Q(a) П [b] — восьмиугольник или объединение двух четырехугольников.

Если | Q | = 120, то по лемме 6 имеем ai(g) = 0. Если U является 3-кокликой из u h g i , то Xo(U) U X3(U) содержит 120 вершин из Q и 2 вершины из u h g i . Пусть w G Г (Q U u h g i ). Если [w] содержит не более 1 вершины из u h g i , то Xo(U) содержит не менее 2 вершин из w h g i . Если [w] содержит не менее 3 вершин из u h g i , то для U С [w] подграф X3 (U) содержит w. В обоих случаях имеем противоречие. Значит, [w] содержит точно 2 вершины из u h g i , граф Г Q регулярен степени 78. По лемме 3 выполняются неравенства 21 6 78 21 200/120 6 3, — противоречие.

Если | Q | G { 80, 85, 90, 95 } , то по лемме 6 на Г Q нет кликовых h g i -орбит.

Пусть | Q | = 95. По целочисленности X2(g) число ai(g) + 3 делится на 24, поэтому a1(g) G { 45,165 } . Но в случае a1(g) = 165 на Г Q найдется кликовая h g i -орбита. Значит, на Г Q имеются 18 пятиугольных h g i -орбит и 27 кокликовых, причем ввиду леммы 4 пятиугольная орбита не попадает в окрестность никакой вершины из Q. Пусть A (B) — множество вершин из Г Q, лежащих в пятиугольных (кликовых) h g i -орбитах. Тогда | А | = 90, | В | = 135. Для u G A имеется 95 36 2-путей с началом в u, концом в Q и средней вершиной в B. Поэтому | [u] П B | > 95. Противоречие с тем, что | [u] П [ug] | содержит не менее 55 вершин из B .

Пусть | Q | = 90. По целочисленности X2(g) число a1(g) + 6 делится на 24, поэтому ai(g) = 90, на Г Q имеются 36 пятиугольных h g i -орбит и 10 кокликовых. Ввиду леммы 4 пятиугольная орбита попадает в окрестности не более 5 вершин из Q.

Пусть | Q | = 85. По целочисленности X2(g) число a1(g) + 9 делится на 24, поэтому ai(g) = 15, на Г Q имеются 6 пятиугольных h g i -орбит и 41 кокликовая. Ввиду леммы 4 пятиугольная орбита попадает в окрестности не более 10 вершин из Q.

Пусть | Q | = 80. По целочисленности Х2(g) число ai(g) делится на 24, поэтому ai(g) G { 0,120 } . В случае a1 (g) = 120 на Г Q имеются 48 пятиугольных h g i -орбит, и ввиду леммы 4 пятиугольная орбита попадает в окрестности не более 15 вершин из Q.

Пусть | Q | = 5s, s 6 15. По целочисленности X2(g) число ai(g) 15s делится на 24, поэтому a1 (g) = 120r + 15s, r G {— 2, 1, 0,1, 2 } . B

Лемма 13. Если p = 3 и | Q | = 3t + 2, то Q не содержит вершин степени | Q | — 2 и выполняются следующие утверждения:

  • (1)    Q является объединением двух изолированных вершин и Кз , з -подграфа, ai(g) делится на 72 ;

  • (2)    | Q | = 80 или | Q | = 140 и a1(g) = 0;

  • (3)    | q | = 3t + 2, 3 6 t 6 25, ai(g) = 72s + 9t + 54 и s G {— 3, 2,... , 4 } .

C Пусть p = 3 и | Q | = 3t + 2. Тогда степень вершины в графе Q равна 3i, любое ребро графа Q лежит в 3j треугольниках из Q, а для любых двух вершин a, b, находящихся на расстоянии 2 в Q, имеем | Q(a) П [b] | = 31.

Если Q содержит вершину a степени | Q |— 2, то для b G Q(a) подграф Q(b) содержит a, кратное 3 число вершин из Q(a) и еще не более одной вершины, — противоречие.

Пусть |Q| = 8. Тогда степень вершины в Q равна 0 или 3, поэтому Q является объединением двух изолированных вершин и K3,3-подграфа. Далее, ai(g) = 24r и 44 — Х2(g) = 39 + r делится на 3.

Пусть t > 25. Тогда ai(g) = 0, поэтому | Q | G { 80,104 } .

Пусть | Q | = 3t+2, t 6 25. Тогда ai(g) 9t 6 делится на 24, поэтому ai(g) = 24r+9t+6 и r G {— 9, 8,..., 12 } . Далее 44 x 2 (g) = 40 + r делится на 3, поэтому r = 3s + 2. B

Лемма 14. Пусть p = 2. Тогда верны следующие утверждения:

  • (1)    Q — куб и ai (g)/24 — нечетное натуральное число;

  • (2)    ai(g)=0, | Q | = 16s, s G { 1, 2,..., 9 } ;

  • (3)    a i (g) = 0, | Q | = 2t, 5 6 t 6 70, и a i (g) = 48r + 6t.

C Пусть p = 2 и | Q | = 2t. Тогда степень вершины в графе Q равна 2i + 1, любое ребро графа Q лежит в 2j треугольниках из Q, а для любых двух вершин a, b, находящихся на расстоянии 2 в Q, имеем | Q(a) П [b] | = 21.

Пусть | Q | = 6. Если Q содержит вершину a степени 5, то подграф Q(a) имеет нечетные параметры А 0 и ^ 0 , — противоречие. Значит, любая вершина имеет степень 1 или 3 в Q, снова получили противоречие. Пусть | Q | = 8. Если Q содержит вершину a степени 7, то подграф Q(a) имеет нечетные параметры А 0 и ^ 0 , — противоречие. Если любая вершина имеет степень 1 или 3 в Q, то Q получается удалением из K 4 , 4 максимального паросочетания (Q — куб). Если Q содержит вершину a степени 5, то подграф Q(a) имеет нечетные параметры А 0 и ^ 0 , противоречие. Далее, X2(g) =5 a 1 (g)/24, 44 X2(g) = 39 + ai(g)/24, поэтому ai(g)/24 — нечетное натуральное число. Утверждение (1) доказано.

Пусть ai(g) = 0. По лемме 6 имеем | Q | = 16s, s G { 1, 2,..., 9 } . Утверждение (2) доказано.

Пусть ai(g) = 0. По лемме 6 имеем | Q | 6 140. Далее, X2(g) = (6t ai(g))/24 +4 и число 44 х2(g) =40 (6t a i (g))/24 четно. Поэтому a i (g) = 48r + 6t. Лемма, а вместе с ней и теорема доказаны. B

Список литературы Об автоморфизмах сильно регулярного графа с параметрами (320, 99, 18, 36)

  • Cameron P., Van Lint J. Designs, Graphs, Codes and their Links.-Cambridge: Cambridge Univ. Press, 1981.-240 p.-(London Math. Soc. Student Texts. Vol. 22).
  • Гаврилюк А. Л., Махнев А. А. Об автоморфизмах дистанционно регулярного графа с массивом пересечений $\{56,45,1;1,9,56\}$//Докл. АН.-2010.-Т.~432, \No 5.-С. 512-515.
  • Brouwer A., van Lint J. Strongly regular graphs and partial geometries//Enumeration and Design/Ed. by M. Jackson, S. Vanstone.-New York: Academic Press, 1984.-P. 85-122.
  • Журтов А. Х., Махнев А. А., Нирова М. С. Об автоморфизмах 4-изорегулярных графов//Тр. Ин-та мат. и мех. УрО РАН.-2010.-Vol. 16, \No 3.-С. 94-102.
  • Cameron P. Permutation Groups.-Cambridge: Cambridge Univ. Press, 1999.-220 p.-(London Math. Soc. Student Texts. Vol. 45).
Статья научная