Об автоморфизмах дистанционно регулярного графа с массивом пересечений {39, 30, 4; 1, 5, 36}

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

Пусть Г — г]заф. a, b Е Г. Тогда число вершин в [a] П [b] обозначавтея через ^(a, b) (через X(a, b)), если a, b находятся на расстоянии 2 (смежны) в Г. Далее, индуцированный [a] П [b] подграф иазывается цподграфюм Д-поОграфом). Если Г — граф ,диаметра, d. то через Г_i. г,де i 6 d. обозначается граф е тем же множеством вершин, что и Г. в котором две вершины смежны тогда и только тогда, когда они находятся на расстоянии i в Г.

Если вершины u. w находятся на расстоянии i в Г. то ^т юрез bi(u, w) (нерез ci(u, w)) обозначим число вершин в пересечении Ц+Ди) (Ц-Ди)) с [w]. Граф Г диаметра d называется дистанционно регулярным с массивом пересечений {bo , bi,..., bd-i; ci,..., Cd }, если значения bi (и, w) 11 ci (u, w) ne зависят от выбора, вершин и. w на расстоянии i в Г для любого i = 0,..., d. Положим ai = k — bi — ci. Заметим, что для дистанционно регулярного графа. bo = k — ото степень графа. C1 = 1. Дпстаптщоппо регулярный граф Г диаметра. 2 называется сильно регулярным с параметрами (v,k,X, ц). г де X = П1,ц = C2.

Далее, через pij-(х, у) обозначим число вершин в подграфе Г_i(x) П Г (у) для вершин х, у, находящихся на расстоянии l в графе Г. В дистанционно регулярном графе числа pij(х, у) нс зависят от выбора, вершин х. у. обозначаются pij и называются числами пересечений графа Г.

Пусть Г является дистанционно регулярным графом диаметра 3 с собственными значениями 0о >01 >02 > 0з- Ес -ли 02 = —1. то по предложению 4.2.17 из [1] граф Г3 сильно регулярен и Г — антиподальный граф тогда, и только тогда, когда. Г3 — коклика.

Пусть Г является дпсташщошю регулярным графом и графы Г2. Г3 сильно регулярны. Если к <  44. то Г имеет массив пересечений {19,12, 5; 1,4,15}. {35, 24, 8; 1, 6, 28} или {39, 30,4;1,5, 36}. В первых двух случаях согласно [2, с. 211] и [3] граф не существует. В данной работе найдены возможные автоморфизмы дистанционно регулярного графа с массивом пересечений {39, 30,4; 1, 5, 36}.

Пусть Г является дистанционно регулярным графом с массивом пересечений {39, 30,4;1,5, 36}. Тогда Г имеет спектр 391,978, -1117, —6104 11 v = 1 + 39 + 234 + 26 = 300 вершин.

Теорема 1. Пусть Г — дистанционно регулярный граф с массивом пересечений {39, 30,4; 1,5, 36}. G = Aut(F). g — злемент простого порядка из G 1 1 Q = Fix(g). Тогда n(G) С {2, 3,5,13} и выполняется одно из следующих утверждений:

• (1)    Q — пустой г]>аф. либо p = 5. a₃(g) = 50s 11 a₂(g) = 75t либо p = 3. a₃(g) = 30s 11 02(g) = 45t. либо p = 2. a₂(g) = 0 11 03(g) = 20s:

• (2)    Q является п-кликой. либо p = 13. n = 1. 03(g) = 130s + 26 11 02(g) = 195t + 39. либо p = 2. n = 2,4, 6. a₃(g) = 20s — 4n 11 02(g) = 30t — 6n:

• (3)    Q состопт из m вершин, попарно иахо,тяпшхся па расстоянии 3 в Г. p = 3 11 либо m = 3. аз(д) = 30s — 12 6 180. s = 1, 2,..., 6. a₂(g) = 45t — 18. .п 160 m = 6. аз(g) = 6, 36. a₂(g) = 45t — 36:

• (4)    Q содержит вершины b, c. находящиеся па расстоянии 2 в Г. p = 2, 3 11 |Q| 6 60.

Следствие 1. Пусть Г — дистанционно регулярный граф с массивом пересечений {39, 30,4; 1,5, 36}, грушпа G = Aut(P) действует транзитивно на множестве вершин графа Г. T — поколь группы G = G/S(G). Тогда 13 нс д< лит |G|- В час tiioctii. G действует интранзитивно на множестве дуг графа Г.

Лемма 1. Дистанционно регулярный граф с массивом пересечений {39, 30,4; 1, 5, 36} имеет следующие числа пересечений:

• ⁽¹⁾    pii = 8, pi2 = ³⁰ p23 = ²⁴ p22 = ¹⁸⁰ p33 = 2;

• (2)    p²₁₁ = 5 p²₁₂ = 30 p²₁₃ = 4 p²₂₂ = 183 p²₂₃ = 20 p²₃₃ = 2;

• (3)    p³2 = 36, p^ = 3, p33 = 18, p32 = 180, p33 = 4.

C Вычисления с помощью леммы 4.1.7 из [1]. B

Лемма 2. Пусть Г — дистанционно регулярный граф с массивом пересечений {39, 30,4; 1,5, 36}. Тогда выполняются следующие утверждения:

• (1)    граф Г3 сильно регуляреи с параметрами (300, 26,4, 2) и спектром 261,6¹¹⁷, —4¹⁸²;

• (2)    пополнительный граф) Е для Г₂ сильно регуляреи с параметрами (300, 65,10,15) и спектром 651,5¹⁹⁶, —10¹⁰³. окрестиоств вершины а в гр афе Е имеет разбиение двумя регулярными подграфами: Д1 степени 7 на 26 вершинах и Д₂ степени 8 на 39 вершинах, вершина из А1 смеята с 3 вершинами из Д₂. вернита из Д₂ смелта с 2 вершинами из Д1;

• (3)    вершина из Е2(а) смежна, с 6 вершинами из А1 и с 9 вершинами из Д₂.

C Поло жим Д = Г3. По замечанию после предложения 4.2.18 из [1] собственные значения графа Д равны (0² + (c₂ — а1)0 — k)/c₂, когда 0 пробегает множество собственных значений графа Г. При 0 = — 1 пола "ним 02 (Д) = — (b1 + c₂)/c₂ 11 c₂ де.тит Ь1.

Заметим, что к(Д) = к + к2 = к(1 + b1/c2) делится на 02(Д). поэтому Д — псевдо-геометрический граф для pGc3 (k,b1/c2)• Отсюда Д — псевдогеометрический граф для pG36(39 , 6) 11 граф Г3 сильно регуляреи е параметрами (300, 26,4, 2).

Далее, дополнительный граф Е для Г2 сильно регулярен с параметрами (300, 65,10,15) II спектром 651. 5196. —10103.

Для вершины a Е X подграф Гз(а) индуцирует в X граф А1 степени 7 на 26 вершинах II Г1(а) индуцирует в X граф А2 степени 8 на. 39 вершинах. B

Лемма 3 [4, теорема 3.2]. Пусть Г является сильно регулярным графом с параметрами (v,k,X,p) и собственныеш значениями k. r, —m. Если g — автоеюрфпзм Г и Q = Fix(g). то |Q| 6 v • max{A, ц}/(к — r).

Пусть g — иеедшшчиый автоморфизм диеташщоиио регулярного графа Г и Q = Fix(g). Если Г имеет массив пересечений {39,30,4; 1,5,36}. то ввиду леммы 3 имеем |Q| 6 60.

Доказательство теоремы 1. Доказательство теоремы опирается на метод Хиг-мена работы с автоморфизмами дистанционно регулярного графа. При этом граф Г рассматривается как симметричная схема отношений (X, R ) с d классами, где X — множество вершин графа. Ro — отношение равенства, на X и для i >  1 кл;кт Ri состоит из пар (u, w) таких. что d(u, w) = i. Для u Е Г поло жим ki = |Гi(u)|. v = |Г|. Классу Ri отвечавт граф Г_i на. множентве вершин X. в котором вершины u. w смежны, если (u, w) Е Ri. Пусть Ai — матрица смежностн графа Г_i д.тя i >  0 1i Ao = I — единичная матрица. Тогда AiAj = P pjAi для чисел псрсссчешш pj.

Пусть Pi — матрица, в которой на месте (j, 1) стоит pj. Тогда собственные значения pi (0),..., pi (d) мату шцы P1 являются собственны мн значениями графа, Г кратностей mo = 1,... ,md- Матрицы P и Q. у которььт на месте (i, j) ста)ят pj (i) 1i qj (i) = mjpi(j)/ni соответственно, называются первой и второй матрицей собственных значений схемы и связаны равенством PQ = QP = vI.

Пусть uj 11 wj — левый и правый собственные векторы матрицы P1. отвечающие собственному значению p1(j ) и имеющие первую координату 1. Тогда кратность mj собственного значения p1(j ) равна v/huj,wj i, где ф, •) — скалярное произведение в евклидовом пространстве R^d+1 (см. [4, теорема 17.12]). Фактически, из доказательства теоремы 17.12 следует, что wj являются стош'шамн матрицы P и mjuj являются строками матрицы Q.

Подстановочное представление группы G = Aut(F) на вершинах графа Г обычным образом дает матричное представление ф группы G в GL(v, C). Пространство Cv является ортогональной прямой суммой собственных подпространств Wo,..., Wd матрицы смежности A = A1 графа Г. Для .любого g Е G матрица ф(g) перестановочиа с A. поэтому подпространство Wi являстся ф(G)-ннвapнaнтIibim. Пуств xi ~ характер представления фwi. Тогда (см. [5. §3.7]) для g Е G получим d xi(g) = n-1 ^2Qij aj (g), j=0

где aj(g) — число точек x из X таких, что d(x, x^g) = j. Заметим, что значения характеров являются целыми алгебраическими числами, и если правая часть выражения для xi(g) ^— число рациональное, то Xi(g) ^— целое число.

Лемма 4. Пусть Г — дистанционно регулярный граф с массивом пересечений {39, 30,4; 1,5, 36}. G = Aut(F). Ес 'ли g Е G. Х2 ^— характер проектшп представления ф на подпространство размерности 117, хз ^— характер проект щи представления ф на подпространство размерности 104. то ai(g) = ai(g^l ) для любого патт"])алвного числа 1. взаимно простого с |g|.

4ao (g) + a3(g)             6ao (g) + a2(g)

^x2(g) =----10—3----’ ^X3(g) =     15 — 16    •

Если |g| = р — простое число, то x2(g) - 117 ¹¹ Хз(д) - 104 лепятся па р. C Имеем

/  1     1     1     1\

78   18   -2-12

Q =   117  -3  -3  27‘

\ 104  -16  4  -16/

Поэтому Х2(g) = (39ао(g) - 01(g) - 02(g) + 9аз(д))/100. Полотявляя 01(g) + 02(g) = 300 - 00(g) - 03(g). поло-ним X2(g) = (4ао(g) + аз(g))/10 - 3.

Далее. X3(g) = (26ао(g) - 401 (g) + 02(g) - 4аз(g))/75. Учитывая равенство 00(g) + 01(g) + 02(g) + 03(g) = 300. поло-ним хз(g) = (600(g) + 02(g))/15 - 16.

Остальные утверждения леммы следуют из [6, лемма 1]. в

• 2.    Автоморфизмы графа с массивом пересечений {39, 30,4;1, 5, 36}

До конца параграфа предполагается, что Г является дистанционно регулярным графом с массивом пересечений {39, 30,4; 1, 5, 36}, G = Aut(r), g — элемент простого порядка р из G 1i Q = Fix(g).

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

• (1)    если Q — пустой граф. то либо р = 5. аз(g) = 50s и 0₂(g) = 75t ii G не содержит элементов порядка 25, либо р = 3, аз(g) = 30s, 02(g) = 45t, либо р = 2, 02(g) = 0 и 03(g) = 20s:

• (2)    если Q яв.тяется n-кликой. то лпоо р = 13. n = 1. 03(g) = 130s + 26 i1 02(g) = 195t + 39. .tiioo р = 2. n = 2,4, 6. 03(g) = 20s - 4n n 0₂(g) = 30t - 6n:

• (3)    если Q cocto пт из m вершин, попарно иахо_:тяпшхся па расстоянии 3 в Г. то р = 3 и либо m = 3. 03(g) = 30s - 12 6 180. s = 1, 2,..., 6. a₂(g) = 45t - 18. ni 160 m = 6. 03(g) = 6, 36. 02(g) = 45t - 36.

• (4)    если [a] С Q .тля иекоторой вершины a. то р = 2.

C Пусть Q — пустой граф. Так как 300 = 12 • 25. то р = 2, 3 пли б . Для i > 0 положим 0 (g) = pwi.

Пусть р = 5. Так как X2(g) - 117 делится па 5. то 03(g) = 50s. Далее. X3(g) -104

делится па 5. поэтому 02(g) = 75t. Допустим, что G содержит элемент f nopiтдка25.

g = f5- Тогда X2(g) = 03(g)/10 - 3 11 X2(g) - 117 делится на 25. поэтому 03(g) = 200. Хз(g) = 02(g)/15 - 16 11 X3(g) - 104 делится па 25. поэтому 02(g) = 300. противоречие.

Пусть р = 3. Так как X2(g) - 117 делится па 3. то 03(g) = 30s. Далее. X3(g) -104

делится па 3. поэтому 02 (g) = 45t.

Пусть р = 2. Так как С2 = 5. то 02(g) = 0. Далее. число %2(g) = (400(g) + 03(g))/10 -3 нечетно, поэтому 03(g) = 20s.

Пусть Q яв.тяется n-кликой. Если n = 1. то р делит 39 и 26. поэтому р = 13. Далее. х2(g) = (4+Q3(g))/10-3i 1 °3(g) = 130s+26. x3(g) = (б+аЮШН-ЮIQ2(g) = l95t+39

Пусть n > 1. Ввиду границы Дельсарта. имеем n 6 1 + 39/6 11 р делит■ 26 ii 300 - n. Так как a1 = 8. то р дел нт 10 - n. р = 2. n = 2,4, 6. ни ело X2(g) = (4n + 03 (g))/10 - 3 нечетно

• ¹¹ 03(g) = 20s - 4n. Далее, число X3(g) = (6n + 02(g))/15 - 16 чет:io 11 02(g) = 30t - 6n.

Пусть Q coctoiit из m вершин, попарно паходятпихея на. расстоянии 3. Тогда Q является кликой в Г3 1i m 6 6. Да. лее. р делит 39. 300 - mi 16 - m. поэтому р = 3. число X2(g) = (4m + 03(g))/10 - 3 делится на 3. поэтому 03(g) = 30s - 4m. Отсюда. m = 3. 03 (g) = 30s - 12 6 180 1 is = 1, 2,..., 6 11. th m = 6. 03(g) = 6, 36. Пиело Хз(g) - 104 = (6m + 02(g))/15 - 120 делится на 3. поэтому 02(g) = 45t - 6m.

Пусть [а] С И для пекоторой вершины a. Если p > 5. то [u] П [а] является 5-кликой для u Е Г2(а) — И. противоречие с тем. что для двух вершин b,c Е [u] П [а] подграф [b] П [c] содержит а. 3 верш ины из [u] П [а] и 5 вер шин из uhgi. Ес ли p = 3. то с учетом равенств рЗз = 8 и р1з = 3 имеем Гз(а) С И. Противоречие с тем, что |И| 6 60. B

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

• (1)    если И содержит вершины b. c. находящиеся па расстоянии 2 в Г. то p 6 3:

• (2)    ее. тп p = 3 11 |CG(g) | пелится па 25. то И — пустой грас}) и либо aз(g) = 300. либо aз(g) = a₁(g) = 150. niioo a₂(g) = 225. a₁(g) = 75.

• 3.    Граф с массивом пересечений {39, 30,4;1, 5, 36}: вершинно симметричный случай

C Ее ли p >  11. то И — вполне рогутярный граф с А = 8. ц = 5 и отсшеии к' >  10. В случае Гз(а) С Ис учетом равенств p33 = 3 и p33 = 2, получим [а] С И, противоречие с леммой 11. Значит, p = 11 1i |Гз(а) П И| =4 для любо!1 вершины а Е И. Противоречие с тем, что в этом случае получим |И(а) | = 6.

В случае p = 7 д.ля а Е И подграф Гз(а) ПИ имеет 12 вершин. |И(а)| = 18 и 5|И2(а)| = 16у + 9(18 — у), поэтому у = 4 1i |И2(а)| = 38. противореч!ю с тем. что |И| 6 60.

В случае p = 5 д.тя а Е И подграф Гз(а) П И имеет 16 вершин. |И(а)| = 24 1i |И2(а) | > 24•15/5. противоречие.

Итак, p = 2, 3.

Пусть p = 3 11 |CG(g)| делится на 25. Если И — непусто!i граф. то |И| делится на 75. противоречие. Значит. И — пустой гд>аф и числа 03(g) = 30s. а₂(g) = 45t делятся на 2-5. Отсюда либо аз(g) = 300. hiioo 03(g) = ai(g) = 150. hiioo o₂(g) = 225. oi(g) = 75. B

До конца работы будем предполагать, что G действует транзитивно на множестве вершин графа Г и 13 ,делит |G|. Тогда |G : Ga | = 300 1i n(G) = {2, 3, 5,13}.

Лемма 7. Если f — элемент порядка 13 из G, g — элемент простого порядка p = 13 из Cof ) и И = Fix(g). то p = 2. |И| = 14. 03(g) = 104. а₂(g) = 156 ii а₂(g) = 26. в частности. |Cg(/ )| по леигтся па 4.

C Ввиду тс юремы 1 Fix(f) = {а} — одиоверш!шный грае!), аз(f) = 130s + 26 1i а₂(f) = 195t + 39.

Если И яв.тяетея n-к.тикой. то p = 2. n = 2,4, 6. Противоречис с действием f ii а И.

Пусть И содержит вершины b,c. находящиеся шi расстоянии 2 в Г. Тогда |И| = 131 + 1. Если p = 3. то 1 = 2. Х2(g) = (521+4+аз(д))/10 —3 делится на 3. поэтому 03(g) = 30m+12. Далее. хз(д) = (781 + 6 + a₂(g))/15 — 16 1i а₂(g) = 45n + 18. Так как числа аз(g). а₂(g) делятся на 13. то 5m + 2 ii 5n + 2 делятся на 13. поэтому m = n = 10. противоречие.

Если p = 2. то 1 = 1, 3. чиело X2(g) = (521 + 4 + аз(у))/10 — 3 нечетно, поэтому 03(g) = 20m + 81 — 4. Далее. число хз (g) = (781 + 6 + a₂(g))/15 — 16 четтю ii а₂(g) = 30n + 121 — 6. Так как числа аз(g), o₂(g) делятся на 13, то 5m + 21 — 1 и 5n + 21 — 1 делятся на 13. Если 1 = 1. то m = n = 5. а еели 1 = 3. то m = n = 10. Отоюда aз(g) = 104. а2(g) = 156. B

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

• (1)    раврешимв 1Й ])алпкал S(G) явл>тется {2, 3}-группой:

• (2)    цоколь T группы G = G/S (G) изомopen L2(25), Ta — диэдральная группа порядк-са 26 11 S(G) = 1.

C Так как v = 300. то S (G) являстся {2, 3, 5}-группой. Ввиду леммы 7 число |S(G)| не делится на 5.

Пусть T - поколь группы 0 = 0/8(0) По [7. теорема 1] группа T изоморфна. L2(25). из(4), 2F4 (2)0. Да лее, |T : Ta| делится на 25 и делит 300. Поэтому T = L2(25), Ta — диэдральная группа порядка 26 индекса 300 в T. Отсюда S(G) = 1. B

Завершим доказательство следствия 1. По лемме 8 цоколь T группы G изоморфен L2(25) и Ta — диэдральная группа порядка 26. Компьютерные вычисления показывают, что дистанционно регулярный граф с массивом пересечений {39, 30,4;1, 5, 36} не возникает. Следствие 1 доказано.