О двудольных Q-полиномиальных графах диаметра, не большего 5

Рассматриваются неориентированные графы без петель и кратных ребер. Если вершины u, w находятся на расстоянии i в графе Г, то через bi(u, w) (через Ci(u, w)) обозначим число вершин в пересечении ri+i(u) (в пересечении ri-i(u)) с [w]. Граф диаметра d называется дистанционно регулярным с массивом пересечений {bo,..., bd-i; ci,... ,Cd}, если значения bi = bi(u,w) и Ci = Ci(u,w) не зависят от выбора вершин u, w на расстоянии i. Положим ai = k — bi — ci и ki = |ri(u)| (значение ki не зависит от выбора вершины u). Числа пересечений графа pj, параметры Крейна qij и Q-полиномиальный граф определены в [1] (стр. 43 и 48 соответственно).

Для двудольного дистанционно регулярного графа Γ половинным графом называется связная компонента в Γ 2 . Для антиподального дистанционно регулярного графа Γ антиподальным частным Γ ^′ называется граф, вершинами которого являются антиподальные классы графа Г и две вершины u ' , w ‘ смежны, если некоторые вершины u G u ' , w G w' смежны в Г. Пусть u — вершина двудольного Q-полиномиального дистанционно регулярного графа Г диаметра D >  3, X = r D (u) и Л = S 2 . Тогда Л — дистанционно регулярный Q-полиномиальный граф (Джон Кохман [2]). Имеется два допустимых массива пересечений Q-полиномиальных графов: { 10, 9, 8, 7, 6; 1, 2, 3,4,10 } (свернутый 10-куб) и { 55, 54, 50, 35,10; 1, 5, 20,45, 55 } . Эти графы имеют сильно регулярные графы Л (параметры (126, 25, 8, 4) и (210, 99, 48, 45)) и окрестности вершин в Л (параметры (25, 8,4, 2) и (99, 48, 22, 24)). В [3] доказано, что дистанционно регулярный граф с массивом пересечений { 55, 54, 50, 35,10; 1, 5, 20, 45, 55 } не существует. Имеются два допустимых массива пересечений, отвечающих графам на 704 вершинах: { 26, 25, 24, 2,1; 1, 2, 24, 25, 26 } и { 36, 35, 32,4,1; 1,4, 32, 35, 36 } . Антиподальные частные этих графов сильно регулярны с параметрами (352, 26, 0, 2) и (352, 36, 0, 4) соответственно.

Теорема 1. Дистанционно регулярный граф с массивом пересечений { 26, 25, 24, 2,1; 1, 2, 24, 25, 26 } не существует.

Теорема 2. Дистанционно регулярный граф с массивом пересечений { 36, 35, 32,4,1; 1, 4, 32, 35, 36 } не существует.

Напомним, что сильно регулярный граф без треугольников существует тогда и только тогда, когда существует его двудольное удвоение диаметра 5 (см. из [1, теорема 1.11.1, п. (vi)]). Отсюда имеем следствие.

Следствие. Сильно регулярные графы с параметрами (352, 26, 0, 2) и (352, 36, 0,4) не существуют.

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

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

и матрицу Q дуальных собственных значений

Пусть u, v, w — вершины графа Г, {ijh} =

1 143 208 208 143 1 1 33 32 —32 —33 —1 1 11 16 16 11 1 5 5 5 5 1 11 16 16 11 —1 5 5 5 5 1 —33 32 32 —33 1 \ 1 —143 208 —208 143 —1 uvw           uvw

{ ijh ), [ijh] = [ijh] ■

Положим X = Г2(и), Л = ^2. Тогда Л — регулярный граф степени p22 = 300 на к2 = 325 вершинах.

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

• [113]    = [131] = 2 , [133] = 22;

• [222]    = 277 , [224] = [242] = 23;

• [313]    = [331] = 23 , [315] = [351] = 1 , [333] = 277;

• [422]    = 22 , [424] = [442] = 2;

• [533]    = 1 .

• <1 Упрощения формул ( * ). >

По лемме 2.1 имеем [222] = 277.

Пусть d(u,v) = 2. Напомним, что p 42 = 300, p 24 = 25, поэтому число ребер между Л(v) и Л 2 (v) в графе Л равно 277 • 25 = 6925.

С другой стороны, указанное число равно 300(299 — А), где А — среднее значение параметра А(Л), поэтому 299 — А = 23.083 и А = 275.917.

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

• [111]    = r i — 22 , [113] = [131] = — r i + 24 , [133] = r i ;

• [222]    = —r 1 + 299 , [224] = [242] = r 1 , [244] = —r 1 + 24;

• [311]    = — r i + 24 , [313] = [331] = r i , [333] = — r i + 299 , [335] = [353] = 1;

• [422]    = r _i , [424] = [442] = — r _i + 24 , [444] = r _i — 22;

• [533]    = 1,

где 22 <  r _i <  24 .

• <    Положив r i = [224] и упростив формулы ( * ) согласно [3], получим требуемые равенства. >

По лемме 2.2 имеем 275 ^ [222] ^ 277.

• <    Доказательство теоремы 1. Пусть d(u, v) = 2. Подсчитаем число f 4 пар вершин y, z на расстоянии 4 в графе X, где y G {24} и z G {2V }. С одной стороны, по лемме 2.1 имеем [224] = 23, поэтому f 4 = 25 • 23 = 575. С другой стороны, по лемме 2.2 имеем [244] = — r i + 24, поэтому f 4 = — £ i r { + 24 • 300 = 575, £ i r { = 6625 и £ i r i /300 = 22.083.

3. Граф с массивом { 36, 35, 32,4,1; 1, 4, 32, 35, 36 }

Подсчитаем число f 2 пар вершин y, z на расстоянии 2 в графе X, где y G {U4} и z G {Uv }. С одной стороны, по лемме 2.1 имеем [222] = 277, поэтому f 2 = 25 • 277 = 6925. С другой стороны, по лемме 2.2 имеем [242] = r i , поэтому f 4 = _i r _i ⁱ = 6925 и £ i r i /300 = 23.083.

Противоречие с тем, что    _i r _i ⁱ /300 = 22.083.

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

Пусть Г является дистанционно регулярным графом с массивом пересечений { 36, 35, 32,4,1; 1,4, 32, 35, 36 } . Тогда антиподальное частное — сильно регулярный граф с параметрами (352,36,0,4), половинный граф сильно регулярен с параметрами (352,315,282,280). Далее, Г имеет 1 + 36 + 315 + 315 + 36 + 1 = 704 вершин, спектр: 36 1 ,8 ¹²⁰ ,4 ²³¹ , — 4 ²³¹ , — 8 ¹²⁰ , - 36 1 , числа пересечений:

Р11 = 0, Р12 = 35, Р22 = 0, Р23 = 280, Р33 = 0, Р34 = 35, Р45 = p211 = 4, p213 = 32, p222 = 282, p224 = 32, p233 = 282, p244 = 4, p235

p ³ ₁₂ = 32, p ³ ₁₄ = 4, p ³ ₂₃ = 282, p ³ ₃₃ = 0, p ³ ₃₄ = 32, p ³ ₂₅ = 1;

p413 = 35, p422 = 280, p424 = 35, p433 = 280, p444 = 0, p415 =1

p ⁵ 14 = 36, p ⁵ 23 = 315,

и матрицу Q дуальных собственных значений

80 3

77 3 11 3 11 3

77 3

77 3 11 3 11 3

77 3

80 3

Пусть u, v, w — вершины графа Г, {ijh} = “VW |, [ijh] = [“^] .

Положим X = Г 2 (и), Л = S 2 . Тогда Л — регулярный граф степени p 22 = 282 на k 2 = 315 вершинах.

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

• [113]    = [131] = 4 , [133] = 28;

• [222]    = 251 , [224] = [242] = 31;

• [313]    = [331] = 31 , [315] = [351] = 1 , [333] = 251;

• [422]    = 28 , [424] = [442] = 4;

• [533]    = 1 .

<1 Упрощения формул ( * ). >

По лемме 3.1 имеем [222] = 251.

Пусть d(u, v) = 2. Напомним, что p 22 = 280, p 24 = 35, поэтому число ребер между Л(v) и Л ₂ (v) в графе Л равно 251 • 35 = 8785.

С другой стороны, указанное число равно 280(279 — А), где А — среднее значение параметра А(Л), поэтому 279 — А = 31.375 и А = 247.625.

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

• [111]    = r i — 28 , [113] = [131] = — r i + 32 , [133] = r i ;

• [222]    = — r 1 + 281 , [224] = [242] = r 1 , [244] = — r 1 + 32;

• [311]    = — r 1 + 32 , [313] = [331] = r 1 , [333] = — r 1 + 281 , [335] = [353] = 1;

• [422]    = r 1 , [424] = [442] = — r 1 + 32 , [444] = r 1 — 28;

[533] = 1, где 28 C r 1 C 32 .

< Упрощения формул ( * ). >

По лемме 2.2 имеем 249 С [222] С 253.

<1 Доказательство теоремы 2. Пусть d(u, v) = 2. Подсчитаем число f 4 пар вершин y, z на расстоянии 4 в графе X, где y G {U 4} и z € {UV }• С одной стороны, по лемме 3.1 имеем [224] =31, поэтому f 4 = 35 • 31 = 1085. С другой стороны, по лемме 3.2 имеем [244] = - r i +32, поэтому f 4 = - £ i r [ +32 ^ 280 = 1085, £ i r l = 7875 и £ i Г 1 /280 = 28.125.

Подсчитаем число f ? пар вершин y, z на расстоянии 2 в графе X, где y G {U4} и z G {Uv }. С одной стороны, по лемме 3.1 имеем [222] = 251, поэтому f ? = 35 • 251 = 8785. С другой стороны, по лемме 3.2 имеем [242] = r 1 , поэтому f 2 = _i r ₁ ⁱ = 8785 и £ i r i /280 = 31.375.

Противоречие с тем, что    _i r ₁ ⁱ / 280 = 28 . 125.

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