Дистанционно регулярный граф с массивом пересечений {140,108,18;1,18,105} не существует

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

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

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

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

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

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

Предложение 1. Пусть Г — граф Шилла с b2 = С2 и 6з = — b(b + 1)/2. Тогда b четно, для b = 2r и С2 = r(t + r) граф Г имеет массив пересечений

{2rt(2r + 1), (2r — 1)(2rt + t + 1), r(r + t); 1, r(r + t), t(4r2 — 1)}, для любой вершины u из Г подграф Fз(u) является антиподальным дистанционно регулярным с массивом пересечений

^{ t(2r + 1), (2r — 1)(t + 1), 1; 1, t + 1, t(2r + 1) ^} , t ^ 2r(r + 1)(2r — 1) — r.

В случае t = r имеем r = 1.

В [3] доказано, что массивы пересечений

{ 2rt(2r + 1), (2r — 1)(2rt + t + 1), r(r + t); 1, r(r + t), t(4r ² — 1) }

и

{t(2r + 1), (2r — 1)(t + 1), 1; 1, t + 1, t(2r + 1)} являются допустимыми при t = 2r2 — 1. В случае r = 2 получим массивы пересечений {140,108,18; 1,18,105} и {35, 24,1; 1, 8, 35} соответственно.

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

Теорема 1. Дистанционно регулярный граф с массивом пересечений { 140,108,18; 1,18,105 } не существует.

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

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

Пусть Г — дистанционно регулярный граф диаметра d . Если ui , u2 , u з — вершины графа Г , ri , r2 , г з — неотрицательные целые числа, не большие d , то через {^lU l u ³} обозначим множество вершин w € Г таких, что d(w,ui) = ri , а через [^l U l u ³] — число вершин в ^{u 1 u 2 u 3} . Числа ^{u 1 u 2 u 3} называются тройными числами пересечений. Для r 1 r 2 r 3                    r 1 r 2 r 3

фиксированной тройки вершин ui, U2, U3 вместо [u^U3] будем писать [г1Г2Гз]. К сожалению, для чисел [г1Г2Гз] нет общих формул. Однако, в [4] предложен метод вычисления некоторых чисел [г1Г2Гз].

Пусть 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 S jv .

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

ddd

Е [ljh| = pjh — j E[ilh= PV — I'M XJ     PW — (

l=1                           l=1

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

Положим

d uvw rst .

Sijh(u,v,w) = У^ QriQsjQth r,s,t=0

Если параметр Крейна qj = 0, то Sijh(u, v,w) = 0.

Зафиксируем вершины u, v, w дистанционно регулярного графа Г диаметра 3 и по ложим

{ijh} = |uvw |, [ijh| = [uvw], [ijh|‘ = [uwv], [ijh|* = M, [ijh|~ = ijh              ijh              ihj               jih wvu hji или d(u, v) = d(u, w) = d(v, w) = 3 вычисление

В случаях d(u, v) = d(u, w) = d(v, w) = 2 чисел

[ijh|‘ =

uwv ihj ,

[ijh|*

vuw jih

и [ijh|~

wvu hji

(симметризация массива тройных чисел пересечений) может дать новые соотношения, позволяющие доказать несуществование графа.

• 3.    Граф с массивом пересечений {140,108,18; 1,18,105}

  В этом разделе Г — дистанционно регулярный граф с массивом пересечений {140,108,18; 1,18,105}, u, v, w — вершины графа Г и [rst| = [uVW]. Тогда v = 1 + 140 + 840 + 144 = 1125, Г имеет спектр 1401, 3560 , 5⁵⁶⁰, —10⁵⁰⁴и дуальная матрица собственных значений графа Г равна

  /1  60   560  504

1   15   20

Q = 1   0   —10   9"

1  —15  35

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

• ⁽¹⁾    P11 = ^31,P21 = ^108,P32 = ^108,P22 = ^624,P33 = ³⁶;

• (2)    P11 = 18, р^ = 104, р1з = 18, p22 = 627, p^2 = 108, рЗз = 18;

• (3)    p32 = 105, p32 = 630, рЗз = 35, рЗз = 105 и рЗз = 3.

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

Пусть u, v, w — вершины графа Г и [ijh| = [uv^]• Положим А = Гз(u), Л = А2. Тогда Л — регулярный граф степени 105 на 144 вершинах.

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

• (1)    [122| = —2ri/3 + 136, [123| = [132| = 2ri/3 — 31, [133| = —2ri/3 + 66;

• (2)    [211| = —2ri/3 + 73, [212| = [221| = 2ri/3 + 32, [222| = —ri/3 + 488, [223| = [232| =

—ri/3 + 110, [233| = ri/3 — 5;

• (3)    [311] = 2ri/3-42, [312] = [321] = -2ri/3 + 76, [322] = ri, [323] = [332] = -ri/3+29, [333] = ri/3 - 26, где ri G {78, 81, 84, 87}.

• <1    Компьютерные вычисления. >

По лемме 2 имеем 78 С [322] С 87.

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

• (1)    [122] = 2r2 + 8гз - 879, [123] = [132] = -2r2 - 8гз + 984, [133] = 2r2 + 8гз - 949;

• (2)    [211] = 2r2 + 7гз - 945, [212] = [221] = -2r2 - 6гз + 1032, [213] = [231] = -гз + 18, [222] = Г2, [223] = [232] = Г2 + 6гз - 402, [231] = -гз + 18, [233] = -Г2 - 5гз + 489;

• (3)    [311] = -2r2 - 7r3 + 963, [312] = [321] = 2r2 + 6r3 - 928, [313] = [331] = r3, [322] = -3г2 - 8гз + 1506, [323] = [332] = Г2 + 2гз - 474, [333] = -Г2 - 3гз + 477, где r2 G {468,469,... , 477}, гз G {0,1,... , 3}.

• < Компьютерные вычисления. >

  По лемме 3 имеем 68 С [322] = -3r2 - 8гз + 1506 С 102.

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

• (1)    [122] = 2r4/5 + 42, [123] = [132] = -2r4/5 + 63, [133] = 2r4/5 - 28;

• (2)    [212] = [221] = 2r4/5 + 42, [213] = [231] = -2r4/5 + 63, [222] = -7r4/5 + 588, [223] = [232] = r4, [233] = -3r4/5 + 42;

• (3)    [312] = [321] = -2r4/5 + 63, [313] = [331] = 2r4/5 - 28, [322] = r4, [323] = [332] = -3r4/5 + 42, [333] = r4/5 - 12.

• < Компьютерные вычисления. >

  По лемме 4 [233] = -3^/5 + 42 дает 3r4/5 С 42, [313] = 2r4/5 - 28 дает 42 С 3r4/5 и Г4 = 70. Отсюда [333] = Г4/5 - 12 = 2 и Л — реберно регулярный граф с параметрами (144,105,2), причем 68 С ^(Л) С 102. Противоречие с тем, что число ребер между Л(v) и Л - ({v} U Л(v)) не меньше 105 • 102 = 4420, но не больше 38 • 102 = 3876.

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