Q-полиномиальных графах Шилла с b=6

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

Пусть Г — граф, а, b Е Г , число вершин в [а] П [b] обозначается через ^(а, b) (через Х(а, b)) , если а , b находятся на расстоянии 2 (смежны) в Г . Далее, индуцированный [а] П [b] подграф называется ц-подграфом (Х-подграфом). Пусть Г — граф диаметра d , i Е { 1, 2, 3,... , d } . Граф P i имеет то же самое множество вершин, и вершины u, w смежны в Г , если dr(u, w) = i .

Если вершины u, w находятся на расстоянии i в Г , то через b i (u, w) (через c i (u, w) ) обозначим число вершин в пересечении Г i +1(u) ( Г i_- 1(u) ) с [w] . Граф Г диаметра d называется дистанционно регулярным с массивом пересечений { bo, bi,..., b d - i; ci,..., C d } , если значения b i (u, w) и c i (u, w) не зависят от выбора вершин u, w на расстоянии i в Г

• ^#    Исследование выполнено при финансовой поддержке Российского фонда фундаментальных исследований и Государственного фонда естественных наук Китая, проект № 20-51-53013, и Естественно научного фонда Китая провинции Хайнань, проект № 120RC453.

(0 2022 Махнев А. А., Чжиган Ван.

для любого i = 0,..., d . Положим a i = к — b i — c i . Заметим, что для дистанционно регулярного графа bo — это степень графа, ci = 1 . Далее, через p ij (х, у) обозначим число вершин в подграфе r i (х) П F j (у) для вершин х,у , находящихся на расстоянии l в графе Г . В дистанционно регулярном графе числа p ij (х, у) не зависят от выбора вершин х , у , обозначаются p ij и называются числами пересечений графа Г (см. [1]).

Графом Шилла называется дистанционно регулярный граф Г диаметра 3, имеющий второе собственное значение 0i , равное a = аз . В этом случае а делит к и полагают b = Ь(Г) = к/a . Далее, a i = а — b и Г имеет массив пересечений { ab, (a + 1)(b — 1), b2; 1, C2, a(b — 1) } (см. [2]). И. Н. Белоусов и А. А. Махнев нашли допустимые массивы пересечений Q -полиномиальных графов Шилла с b = 6 [3].

Предложение 1. Q-полиномиальный граф Шилла с b = 6 имеет массив пересечений:

• (1)    { 42t, 5(7t + 1), 3(t + 3);1, 3(t + 3), 35t } , где t E { 7,12,17, 27, 57 } ;

• (2)    { 372,315,75;1,15, 310 } , { 744,625,125;1,25,620 } или { 930, 780,150; 1, 30, 775 } ;

• (3)    { 312, 265,48; 1, 24, 260 } , { 624, 525, 80;1,40, 520 } , { 1794,1500, 200;1,100,1495 } или { 5694, 4750, 600; 1, 300, 4745 } .

• 2.    Тройные числа пересечений

Следующие теоремы являются основными результатами работы.

Теорема 1. Дистанционно регулярные графы с массивами пересечений { 372, 315, 75; 1,15, 310 } и { 744, 625,125; 1, 25, 620 } не существуют.

Теорема 2.   Дистанционно регулярный граф с массивом пересечений

{ 1794, 1500, 200; 1, 100, 1495 } не существует.

В доказательстве теоремы используются тройные числа пересечений [4].

Пусть Г — дистанционно регулярный граф диаметра d . Если ui , U2 , U 3 — вершины графа Г , ri , Г2 , Г3 — неотрицательные целые числа, не большие d , то через {^2 ^ 33} обозначим множество вершин w E Г таких, что d(w,u i ) = r i , а через [Ц^Г З ³] — число вершин в ^u _r ¹ ₁ ^u _{r 2} ² _r ^u ₃ ³ . Числа ^u _r ¹ ₁ ^u _{r 2} ² _r ^u ₃ ³ называются тройными числами пересечений. Для фиксированной тройки вершин ui , u 2 , U3 вместо pr^u /j будем писать [п^ гз ] . К сожалению, для чисел [rir2r3] нет общих формул. Однако в [4] предложен метод вычисления некоторых чисел [rir2r3] .

Пусть u , v , w — вершины графа Г , W = d(u, v) , U = d(v,w) , V = d(u, w) . Так как имеется точно одна вершина х = u такая, что d(x,u) = 0 , то число [0jh] равно 0 или 1 . Отсюда [0jh] = 5 jw S hv . Аналогично [i0h] = S iw S hu и [ij0] = S iU 5 jv .

Другое множество уравнений можно получить, фиксируя расстояние между двумя вершинами из { u, v, w } и сосчитав число вершин, находящихся на всех возможных расстояниях от третьей:

ddd

^[ljh] = PUh — PjhL ^[ilh] = PV — [i0hL ^[ijl] = PW — [ij0]- l=1                           l=1

При этом некоторые тройки исчезают. При | i — j | > W или i + j < W имеем p W = 0 , поэтому [ijh] = 0 для всех h E { 0,... , d } .

Положим S ijh (u,v,w) = £ d,_s,_{t =0} Q ri Q sj Q th [urvsW]• Если параметр Крейна q h = 0 , то S ijh (u, v, w) = 0 .

Зафиксируем вершины u, v, w дистанционно регулярного графа Г диаметра 3 и положим { ijh } = ( ^uvw ) , [ijh] = [ ^uvw 1 , [ijhV = [ uvw 1 , [ijh] * = [ ^uvw 1 и [ijhT = [ uvw 1 .

ijh ^,                 ijh   ^,                  ihj    ^,                   jih                         hji ^.

В случаях d(u, v) = d(u, w) = d(v, w) = 2 или d(u, v) = d(u, w) = d(v, w) = 3 вычисление uvw             uvw               uvw чисел [ijh] = ihj , [ijh] = jih и [ijh] = hji (симметризация массива тройных чисел пересечений) может дать новые соотношения, позволяющие доказать несуществование графа.

• 3.    Графы с массивом пересечений { 372, 315, 75; 1,15, 310 } и { 744, 625,125; 1, 25, 620 }

• 4.    Граф с массивом пересечений { 1794,1500, 200; 1,100,1495 }

  В этом разделе Г — дистанционно регулярный граф с массивом пересечений { 294, 250, 30; 1, 30, 245 } . Пусть Г — дистанционно регулярный граф с массивом пересечений { 1794,1500, 200; 1,100,1495 } . Так как многочлен Тервиллигера (см. [5]) равен — 5(x² — 153x + 1346)(x + 6)(x — 59) , то неглавные собственные значения локального подграфа лежат в [ — 6, — 5/2 ^ 721 + 153/2] U { 59 } U { 293 } .

Пусть Г — дистанционно регулярный граф с массивом пересечений { 372,315,75; 1,15,310 } , и — вершина графа Г и X = [и] . Тогда многочлен Тервиллигера (см. [5]) графа Г равен — 15(2x — 19)(x + 6)(x + 1)(x — 44) , поэтому собственные значения локального подграфа X содержатся в множестве [ — 6, — 1] U (19/2,44] . С другой стороны, по предложению 4.4.3 из [1] собственные значения локального подграфа содержатся в [ — 6,19/2) . Отсюда локальный подграф является объединением изолированных (ai + 1) -клик, противоречие с тем, что ai + 1 = 57 не делит k = 372 .

Пусть Г — дистанционно регулярный граф с массивом пересечений { 744,625,125; 1,25,620 } . Тогда многочлен Тервиллигера графа Г равен — 5(6x — 119)(x +6)(x + 1)(x — 94) . Отсюда собственные значения локального подграфа содержатся в [ — 6, — 1] U (119/6,94] . С другой стороны, по предложению 4.4.3 из [1] собственные значения локального подграфа содержатся в [ — 6,119/6) . Отсюда локальный подграф является объединением изолированных (ai + 1) -клик, противоречие с тем что ai + 1 = 119 не делит k = 744 .

Теорема 1 доказана.

Далее, Г имеет 1 + 1794 + 26910 + 3600 = 32305 вершин, спектр 17941 , 299⁴²⁶ , 19¹⁵⁵⁴⁸ , — 26¹⁶³³⁰ и дуальную матрицу собственных значений

		1	426	15548	16330
		1	71	494	710
Q =		1	0	3 364	3 355
				9	9
		1	71	3887	1633
			2	18	9 /

Лемма 1. Для чисел пересечений графа Г выполняются равенства:

• (1)    pii = 293 , p2i = 1500 , p32 = 3000 , p22 = 22410 , рЗз = 600 ;

• (2)    p²ii = 100 , p²i2 = 1494 , p²i3 = 200 , p²22 = 22415 , p²23 = 3000 , p²33 = 400 ;

• (3)    p³i2 = 1495 , p³i3 = 299 , p³22 = 22425 , p³23 = 2990 , p³33 = 310 .

⊳ Прямые вычисления. ⊲

Пусть u Е Г , A = P2(u) , Л = A2 . Тогда Л — регулярный граф степени 22415 на 26910 вершинах.

Лемма 2. Пусть d(u,v) = d(u, w) = 2,d(v,w) = 1 . Тогда выполняются равенства:

• [111]    = г з , [112] = [121] = - г з + 100, [122] = (23гз + 4г 4 + 3082)/3, [123] = [132] = ( - 20гз - 4г4 + 1100)/3, [133] = (20гз + 4г4 - 500)/3;

• [211]    = (7гз + 2г4 + 479)/3, [212] = [221] = ( - 7гз - 2г4 + 4000)/3,

  • [222]    = ( - 13гз - 5г4 + 56545)/3,

  • [223]    = [232] = (20гз + 7г4 + 6700)/3, [233] = ( - 20гз - 7г4 + 2300)/3; [311] = ( - 10гз - 2г4 + 400)/3, [312] = [321] = (10гз + 2г4 + 200)/3, [322] = ( - 10гз + Г4 + 7600)/3, [323] = [332] = - Г4 + 400, [333] = Г4,

где г з Е { 0,1,... , 40 } , Г4 6 { 0,1,... , 200 } , 5гз + Г4 ^ 200 и число - гз + Г4 +1 делится на 3 .

<1 Упрощение формул (+) с учетом равенств 5п з(и, v,w) = S1з1(u, v,w) = SaxxCu, v, w) = 0 .

Так как [122] = (23гз + 4г4 + 3082)/3 , то 2гз + Г4 + 1 делится на 3 .

По лемме 2 имеем 18342 ^ [222] = ( - 13г_з - 5г₄ + 56545)/3 ^ 18848 . ▻

Лемма 3. Пусть d(u,v) = d(u, w) = 2 , d(v, w) = 3 . Тогда выполняются равенства:

• [112]    = - Г12/6 + 2г1з/3 - 2г_м/9 + 320/9, [113] = Г12/6 - 2г^/3 + 2г_м/9 + 580/9, [121] = 7Г12/12 + Г1з/6 + Г14/9 + 65/9, [122] = - 7Г12/12 - 7г_и/6 - г_м/9 + 13381/9, [123] = гхз, [131] = - 7Г12/12 - гхз/6 - Г14/9 + 835/9,

• [132]    = 3Г12/4 + Г1з/2 + Г14/3 - 85/3, [133] = - Г12/6 - г₄з/3 - 2г_м/9 + 1220/9;

• [212]    = 7г12/6 - 2г1з/3 + 2Г14/9 + 11335/9, [213] = - 7г12/6 + 2г_и/3 - 2г_и/9 + 2111/9, [221] = - 13г12/12 +5г1з/6 - 7г14/9+12100/9, [222] = - Г12/12 - г^/6 + 14г_м/9 +164755/9, [223] = 7г12/6 - 2г1з/3 - 7г14/9 + 24880/9, [231] = 13г_п/12 - 5г1з/6 + 7г.„ 9 + 1346/9, [232] = - 13Г12/12 + 5г1з/6 - 16Г14/9 + 25645/9, [233] = г_к;

• [312] = - Г12 + 200, [313] = Г12, [321] = г^/2 - г1з + 2г_м/3 + 430/3,

  • [322]    = 2г12/3 + 4г1з/3 - 13г14/9 + 23680/9, [323] = - 7г12/6 - г1з/3 + 7г14/9 + 2030/9, [331] = - Г12/2 + пз - 2Г14/3 + 170/3, [332] = Г12/3 - 4г1з/3 + 13г_м/9 + 1520/9, [333] = Г12/6 + Г1з/3 - 7г14/9 + 1570/9,

где Г12 6 { 0, 2,... , 152 } , Г1з 6 { 0,1,..., 200 } , Г14 Е { 1,4,... , 310 } , числа Г12 и 3г₃2/2 + Г1з четны, а число г14 - 1 делится на 3 .

• < Упрощение формул (+) с учетом равенств S11з(u, v,w) = S131(u, v,w) = Sз11(u, v, w) = 0 .

Так как [112]  =   - Г12/6 + 2г^з/3 - 2г^/9 + 320/9 , то Г12 четно. Далее,

• [132] = 3г12/4 + Г1з/2 + Г14/3 - 85/3 , поэтому 3г₃2/2 + г^з четно. Аналогично 3[323] = - 7г12/2 - г1з + 7г14/3 + 2030/3 и г14 - 1 делится на 3 .

Симметризация. [233] = г₁₄ = г ‘ 4 , [132] = 3г₁₂/4 + г 1з /2 + г₁₄/3 - 85/3 = [123] ’ = г1 з , поэтому 9г₁₂ + 6г1з + 4г₁₄ - 12г1₃ = 340 , [331] = - г₁₂/2 + г1з - 2г₁₄/3 + 170/3 = [313] ’ = г ‘ 2 и 3г₁₂ - 6г1з + 4г₁₄ + 6г ‘ ₂ = 340 . Отсюда г₁₂ + 2г1з = 2г ‘ з + г ‘ 2 .

По лемме 3 имеем

18261 ^ [222] = - Г12/12 - Г1з/6 + 14г14/9 + 164755/9 ^ 14 • 310/9 + 164755/9 = 18788.

Напомним, что р^ = 1494 , Р22 = 224 15 , р2з = 3000 , поэтому число d ребер между Л(w) и Л — ( { w } U Л(w)) удовлетворяет неравенствам

82185948 = 1494 • 18342 + 3000 • 18261 С d С 1494 • 18848 + 3000 • 18788 = 84522912.

С другой стороны, d = 22415(22414 — А) , где Л — среднее значение параметра А(Л) . Поэтому 3666.56 С 22414 — Л С 3770.82 и 18643.18 С Л С 18747.44 . ▻

Лемма 4. Пусть d(u,v) = d(u, w) = d(v, w) = 2 . Тогда выполняются равенства:

• [111]    = — rio/5 + 3r_n/20 + Г7/2 + 2r8/5 — 3rg/10,

• [112]    = rio/5 — 3r_n/20 — Г7/2 — 2^/5 — 7r9/10 + 100, [113] = rg,

  • [121]    = rio/5 + 7r_n/20 — 3r7/2 — 9^/10 + 3r9/10 + 100,

  • [122]    = — rio/5 — 7r_n/20 + 3Г7/2 + 19rs/10 + 7^/10 + 1194, [123] = — Г8 — Г9 + 200,

• [131]    = — r_n/2 + Г7 + r₈/2, [132] = rii/2 — Г7 — 3^/2 + 200, [133] = r8;

• [211]    = rio/5 — 3r_n/20 — 3r7/2 — 2r8/5 + 3r9/10 + 100,

• [212]    = — rio/5 + 23r_n/20 + 3r7/2 + 2r8/5 + 7r9/10 + 1194, [213] = — r_n — r9 + 200,

  • [221]    = — rio/5 — 7r_n/20 + 9r7/2 + 19 г ₈ / 10 — 23r9/10 + 1194,

  • [222]    = — 4rio/5 — 13r_n/20 — 9r7/2 — 29r8/10 + 13r₉/10 + 18820,

  • [223]    = rio + rii + r8 + r9 + 2400, [231] = r ii /2 — 3r7 — 3^/2 + 2r9 + 200,

  • [232]    = — rii/2 + 3r7 + 5r8/2 — 2r9 + 2400, [233] = — r_w — r8 + 400; [311] = г ₇ ,

    • [312]    = — rii — r7 + 200, [313] = rii, [321] = — 3r7 — r8 + 2r9 + 200,

    • [322]    = rio + rii + 3r7 + r8 — 2r9 + 2400, [323] = — r_w — r_n + 400,

    • [331]    = 2r7 + r8 — 2r9, [332] = — rio — 2r7 — r8 + 2r9 + 400, [333] = r_w,

где r₇, r₉ G { 0,1,... , 100 } , r_io G { 0,1,..., 320 } , r₈, r_ii G { 0,1,..., 200 } и r₈ — r_ii четно.

• <1 Упрощение формул (+) с учетом равенств 5цз(и, v,w) = Si3i(u,v,w) = S3ii(u, v, w) = 0 дает требуемые равенства.

Далее, [132] = гц/ 2 — r7 — 3r8/2 + 200 , поэтому r8 — гц четно.

Симметризация. [113] = r9 = r9 , [133] = r8 = r8 , [311] = r7 = r7 , [313] = r_ii = г Ц , ^[333] = rio = ^r‘ o = ^r * o = ^rio ^.

Далее, [131] = — r₇i/2 + r7 + r8/2 = [113] ’ = r9 , поэтому 2r7 + r8 = 2r9 + rii ,

• [133] = r8 = [313] = r * i , [113] = r9 = [311] = r i .

По лемме 12 имеем

13117 ^ [222] = — 109rio/6 + 109rii/30 — 36r7 — 13r8/6 + 109r9/30 + 16198 ^ 17288.

Так как { v,w } U Л(v) U Л(v) содержит 39298 — [222] вершин, то 15118 С [222] .

Противоречие с тем, что 18643.18 С Л С 18747.44 . ▻

Теорема 2 доказана.