Доклады Российской академии наук. Математика, информатика, процессы управления, 2021, T. 498, № 1, стр. 45-50

Мы рассматриваем неориентированные графы без петель и кратных ребер. Если a, b – вершины графа $\Gamma $, то через $d(a,b)$ обозначается расстояние между a и $b$, а через ${{\Gamma }_{i}}(a)$ – подграф графа $\Gamma $, индуцированный множеством вершин, которые находятся на расстоянии i в $\Gamma $ от вершины a. Подграф ${{\Gamma }_{1}}(a)$ называется окрестностью вершины $a$ и обозначается через [a]. Дистанционно-регулярные графы с массивом пересечений $\{ {{b}_{0}},...,{{b}_{{d - 1}}};{{c}_{1}},...,{{c}_{d}}\} $ определены в [1]. Пусть $k = {{b}_{0}}$, ${{a}_{i}} = k - {{b}_{i}} - {{c}_{i}}$.

Для дистанционно-регулярного графа диаметра 3 второе собственное значение ${{\theta }_{1}}$ не меньше $\max \{ {{a}_{3}},({{a}_{1}} + \sqrt {4k + a_{1}^{2}} ){\text{/}}2\} $, причем в случае ${{\theta }_{1}} = {{a}_{3}}$ по [2] имеем ${{\theta }_{1}} = ({{a}_{1}} + \sqrt {4k + a_{1}^{2}} ){\text{/}}2$. Графом Шилла называется дистанционно-регулярный граф диаметра 3 со вторым собственным значением ${{\theta }_{1}}$, равным ${{a}_{3}}$. Для графа Шилла $\Gamma $ число $a = {{a}_{3}}$ делит $k$ и полагают $b = b(\Gamma ) = k{\text{/}}a$.

Пусть $\Gamma $ является графом Шилла. Тогда ${{a}_{1}} = a - b$, $\Gamma $ имеет массив пересечений {ab, $(a + 1)(b - 1),{{b}_{2}}$; $1,{{c}_{2}},a(b - 1)\} $ и собственные значения ${{\theta }_{2}},\;{{\theta }_{3}}$, являющиеся корнями уравнения x² – ‒ $({{a}_{2}} + a - b - ab)x + (b - 1){{b}_{2}} - {{a}_{2}}$ = 0. Если ${{\theta }_{2}},{{\theta }_{3}}$ – целые числа, то ${{({{a}_{2}} + a - b - ab)}^{2}} - 4((b - 1){{b}_{2}} - {{a}_{2}})$ является квадратом натурального числа, в противном случае кратности ${{\theta }_{2}}$ и ${{\theta }_{3}}$ совпадают.

Известные графы Шилла – это нечетный граф $O(4)$ с массивом пересечений $\{ 4,3,3;1,1,2\} $, граф Хэмминга $H(3,3)$ с массивом пересечений $\{ 6,4,2$; 1, 2, 3}, обобщенный шестиугольник $GH(2,2)$ с массивом пересечений $\{ 6,4,4;1,1,3\} $, граф Тервиллигера с массивом пересечений $\{ 10,6,4;1,2,5\} $, граф Доро с массивом пересечений $\{ 12,10,3;1,3,8\} $, унитарные графы на множестве неизотропных векторов с массивами пересечений $\{ q(q + 1)$, (q + + 2)(q – 1), $q + 2;1,1,{{q}^{2}} - 1\} $, $q$ – степень простого числа, или граф Джонсона $J(9,3)$ с массивом пересечений $\{ 18,10,4;1,4,9\} $.

Пусть $\Gamma $ является графом Шилла с ${{b}_{2}} = {{c}_{2}}$. Если собственные значения графа ${{\theta }_{2}},\;{{\theta }_{3}}$ графа $\Gamma $ имеют одинаковые кратности, то $\Gamma $ имеет массив пересечений $\{ {{b}^{2}}(b - 1){\text{/}}2,(b - 1)({{b}^{2}} - b + 2){\text{/}}2,$ b(b – 1)/4; 1, $b(b - 1){\text{/}}4$, b(b – 1)²/2}, $b$ сравнимо с 0 или 1 по модулю 4 [2].

Графы Шилла с ${{b}_{2}} = {{c}_{2}}$ изучались также в [3, 4]. Для двупараметрического семейства массивов пересечений $\{ 2{{r}^{2}}(2r + 1)(2lr - (l + 1)),$ (2r – 1)$(2{{r}^{2}}(2lr$ – – (l + 1)) + $r(2lr - (l + 1)) + 1),$ ${{r}^{2}}l(2r - 1);1$, r²l(2r – 1), $r(2lr - (l + 1))(4{{r}^{2}} - 1)\} $ существует лишь конечное число графов ($(l,r) \in \{ (1,2),(2,1),(4,1),(6,1)\} $) (см. [4, теорема 2]).

В работе [5] найдены следующие бесконечные серии допустимых массивов пересечений графов Шилла:

(1) $\{ (2{{c}_{2}} - 1){{c}_{2}}(2c_{2}^{2} - 1),2c_{2}^{2}((2{{c}_{2}} - 1){{c}_{2}} - 1),2c_{2}^{2};$ 1, c₂, (2$c_{2}^{2}$ – 1)((2c₂ – 1)c₂ – 1};

(2) $\{ b({{b}^{2}} - 1),{{b}^{2}}(b - 1),{{b}^{2}};1,1,({{b}^{2}} - 1)(b - 1)\} $;

(3) $\{ b(b + 1),(b + 2)(b - 1),b + 2;1,1,{{b}^{2}} - 1\} $;

(4) $\{ 2b(b - 1),(2b - 1)(b - 1),2b - 1;1,1,2{{(b - 1)}^{2}}\} $;

(5) $\{ (s + 1)({{s}^{3}} - 1),{{s}^{4}},{{s}^{3}};1,{{s}^{2}},s({{s}^{3}} - 1)\} $, $s > 2$.

Предлагается программа изучения графов Шилла с массивами пересечений из этих серий.

Заметим, что в серии {2b(b – 1), (2b – 1)(b – 1), $2b - 1;1,1,2{{(b - 1)}^{2}}\} $ имеется только 3 допустимых массива пересечений $\{ 4,3,3;1,1,2\} $, $\{ 12,10,5;1,1,8\} $ и $\{ 84,78,13;1,1,72\} $.

Теорема 1. Пусть $\Gamma $ является дистанционно-регулярным графом с массивом пересечений $\{ b({{b}^{2}}\, - \,1),{{b}^{2}}(b\, - \,1),{{b}^{2}};1,1,({{b}^{2}}\, - \,1)(b\, - \,1)\} $. Тогда $b\, \in \,\{ 2,3\} $.

Следствие 1. Пусть $\Gamma $ является дистанционно-регулярным графом с массивом пересечений $\{ b({{b}^{2}} - 1),{{b}^{2}}(b - 1),{{b}^{2}};1,1,({{b}^{2}} - 1)(b - 1)\} $. Тогда $b = 2$ и $\Gamma $ – обобщенный шестиугольник порядка $(2,2)$ с массивом пересечений $\{ 6,4,4;1,1,3\} $.

Теорема 2. Дистанционно-регулярный граф с массивом пересечений $\{ {{b}^{2}}(b - 1){\text{/}}2$, (b – 1)(b² – ‒ $b + 2){\text{/}}2,$ $b(b - 1){\text{/}}4;1,b(b - 1){\text{/}}4,b{{(b - 1)}^{2}}{\text{/}}2\} $ не существует.

Граф Шилла $\Gamma $ с массивом пересечений $\{ (s + 1)({{s}^{3}} - 1),{{s}^{4}},{{s}^{3}};1,{{s}^{2}},s({{s}^{3}} - 1)\} $ является Q-полиномиальным.

Теорема 3. Дистанционно-регулярный граф с массивом пересечений $\{ (s + 1)({{s}^{3}} - 1),{{s}^{4}},{{s}^{3}}$; 1, s², $s({{s}^{3}} - 1)\} $ не существует.

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

Пусть $\Gamma $ – дистанционно-регулярный граф диаметра d. Если ${{u}_{1}},\;{{u}_{2}},\;{{u}_{3}}$ – вершины графа $\Gamma $, ${{r}_{1}},{{r}_{2}},{{r}_{3}}$ – неотрицательные целые числа, не большие d. Через $\left\{ {\begin{array}{*{20}{c}} {{{u}_{1}}{{u}_{2}}{{u}_{3}}} \\ {{{r}_{1}}{{r}_{2}}{{r}_{3}}} \end{array}} \right\}$ обозначим множество вершин $w \in \Gamma $ таких, что $d(w,{{u}_{i}}) = {{r}_{i}}$, а через $\left[ {\begin{array}{*{20}{c}} {{{u}_{1}}{{u}_{2}}{{u}_{3}}} \\ {{{r}_{1}}{{r}_{2}}{{r}_{3}}} \end{array}} \right]$ – число вершин в $\left\{ {\begin{array}{*{20}{c}} {{{u}_{1}}{{u}_{2}}{{u}_{3}}} \\ {{{r}_{1}}{{r}_{2}}{{r}_{3}}} \end{array}} \right\}$. Числа $\left[ {\begin{array}{*{20}{c}} {{{u}_{1}}{{u}_{2}}{{u}_{3}}} \\ {{{r}_{1}}{{r}_{2}}{{r}_{3}}} \end{array}} \right]$ называются тройными числами пересечений. Для фиксированной тройки вершин ${{u}_{1}},{{u}_{2}},{{u}_{3}}$ вместо $\left[ {\begin{array}{*{20}{c}} {{{u}_{1}}{{u}_{2}}{{u}_{3}}} \\ {{{r}_{1}}{{r}_{2}}{{r}_{3}}} \end{array}} \right]$ будем писать $[{{r}_{1}}{{r}_{2}}{{r}_{3}}]$. К сожалению, для чисел $[{{r}_{1}}{{r}_{2}}{{r}_{3}}]$ нет общих формул. Однако в [6] предложен метод вычисления некоторых чисел $[{{r}_{1}}{{r}_{2}}{{r}_{3}}]$.

Пусть $u,{v},w$ – вершины графа $\Gamma $, $W = d(u,{v})$, $U = d({v},w)$, $V = d(u,w)$. Так как имеется точно одна вершина x = u такая, что $d(x,u) = 0$, то число $[0jh]$ равно 0 или 1. Отсюда $[0jh] = {{\delta }_{{jW}}}{{\delta }_{{hV}}}$. Аналогично, $[i0h] = {{\delta }_{{iW}}}{{\delta }_{{hU}}}$ и $[ij0] = {{\delta }_{{iU}}}{{\delta }_{{jV}}}$.

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

При этом некоторые тройки исчезают. При $\left| {i - j} \right| > W$ или $i + j < W$ имеем $p_{{ij}}^{W} = 0$, поэтому $[ijh] = 0$ для всех $h \in \{ 0,...,d\} $.

Положим ${{S}_{{ijh}}}(u,v,w) = \sum\limits_{r,s,t = 0}^d {{{Q}_{{ri}}}{{Q}_{{sj}}}{{Q}_{{th}}}} \left[ {\begin{array}{*{20}{c}} {u{v}w} \\ {rst} \end{array}} \right]$. Если параметр Крейна $q_{{ij}}^{h} = 0$, то ${{S}_{{ijh}}}(u,v,w) = 0$.

Зафиксируем вершины $u,v,w$ дистанционно-регулярного графа $\Gamma $ диаметра 3 и положим $\{ ijh\} = \left\{ {\begin{array}{*{20}{c}} {uvw} \\ {ijh} \end{array}} \right\}$, $[ijh] = \left[ {\begin{array}{*{20}{c}} {uvw} \\ {ijh} \end{array}} \right]$, $[ijh]{\kern 1pt} ' = \left[ {\begin{array}{*{20}{c}} {uwv} \\ {ihj} \end{array}} \right]$, [ijh]* = = $\left[ {\begin{array}{*{20}{c}} {vuw} \\ {jih} \end{array}} \right]$ и ${{[ijh]}^{ \sim }} = \left[ {\begin{array}{*{20}{c}} {wvu} \\ {hji} \end{array}} \right]$. В случаях $d(u,v)$ = = $d(u,w)\, = \,d(v,w)$ = 2 или $d(u,v)\, = \,d(u,w)\, = \,d(v,w)$ = 3 вычисление параметров $[ijh]{\kern 1pt} ' = \left[ {\begin{array}{*{20}{c}} {uwv} \\ {ihj} \end{array}} \right]$, [ijh]* = = $\left[ {\begin{array}{*{20}{c}} {vuw} \\ {jih} \end{array}} \right]$ и ${{[ijh]}^{ \sim }} = \left[ {\begin{array}{*{20}{c}} {wvu} \\ {hji} \end{array}} \right]$ (симметризация массива тройных чисел пересечений) может дать новые соотношения, позволяющие доказать несуществование графа.

Пусть $\Gamma $ является дистанционно-регулярным графом с массивом пересечений {b(b² – 1), ${{b}^{2}}(b - 1),{{b}^{2}};1,1,({{b}^{2}} - 1)(b - 1)\} $. Тогда ${{a}_{1}} = {{b}^{2}} - b - 1$ и окрестность любой вершины в $\Gamma $ является объединением b + 1 изолированных $({{b}^{2}} - b)$-клик.

Пусть a, z – вершины, находящиеся на расстоянии 3 в $\Gamma $. Если $[z] \cap {{\Gamma }_{2}}(a)$ содержит $(b + 2)$-клику K, то две подходящие вершины из K смежны с вершинами некоторой клики из $[a] \cap {{\Gamma }_{2}}(z)$. Противоречие с тем, что тогда $\Gamma $ содержит четырехугольник.

Значит, порядок любой клики из $[z] \cap {{\Gamma }_{2}}(a)$ не больше $b + 1$ и $({{b}^{2}} - 1)(b - 1){\text{/}}(b + 1) \leqslant b + 1$. Отсюда ${{(b - 1)}^{2}} \leqslant b + 1$ и $b \leqslant 3$. Теорема 1 доказана.

Пусть $b = 3$ и $\Gamma $ – дистанционно-регулярный граф с массивом пересечений $\{ 24,18,9;1,1,16\} $. Тогда $\Gamma $ имеет $1 + 24 + 432 + 243 = 700$ вершин, спектр: 24¹, ${{8}^{{175}}},$ $ - {{1}^{{224}}},$ $ - {{4}^{{300}}}$ и дуальную матрицу собственных значений

Лемма 1. Числа пересечений графа $\Gamma $ равны

1) $p_{{11}}^{1} = 5$, $p_{{21}}^{1} = 18$, $p_{{32}}^{1} = 162$, $p_{{22}}^{1} = 252$, $p_{{33}}^{1}$ = 81;

2) $p_{{11}}^{2} = 1$, $p_{{12}}^{2} = 14$, $p_{{13}}^{2} = 9$, $p_{{22}}^{2} = 264$, $p_{{23}}^{2} = 153$, $p_{{33}}^{2} = 81$;

3) $p_{{12}}^{3} = 16$, $p_{{13}}^{3} = 8$, $p_{{22}}^{3} = 272$, $p_{{23}}^{3} = 144$, $p_{{33}}^{3}$ = 90.

Доказательство. Прямые вычисления.

Пусть $u,\;{v},\;w$ – вершины графа $\Gamma $, $[rst] = \left[ {\begin{array}{*{20}{c}} {u{v}w} \\ {rst} \end{array}} \right]$, $\Delta = {{\Gamma }_{2}}(u)$ и $\Lambda = {{\Delta }_{2}}$. Тогда $\Lambda $ – регулярный граф степени 264 на 432 вершинах.

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

$[111] = - {{r}_{5}} + 1$, $[112] = [121] = {{r}_{5}}$, $[122] = - {{r}_{4}} - {{r}_{5}} + 14$, $[123] = [132] = {{r}_{4}}$, $[133] = - {{r}_{4}} + 9$;

$[211] = {{r}_{5}} - {{r}_{6}} - {{r}_{7}} + 148$, $[212] = [221] = - {{r}_{5}} + {{r}_{6}} + {{r}_{7}} - 135$, $[222] = {{r}_{4}} + {{r}_{5}} - {{r}_{7}} + 237$, $[223] = [232] = - {{r}_{4}} - {{r}_{6}} + 162$, $[233] = {{r}_{4}} + {{r}_{6}} - 9$;

$[311] = {{r}_{6}} + {{r}_{7}} - 144$, $[312] = [321] = - {{r}_{6}} - {{r}_{7}} + 153$, $[322] = {{r}_{7}}$, $[323] = [332] = {{r}_{6}}$, $[333] = - {{r}_{6}} + 81$,

где ${{r}_{4}} \in \{ 0,1,...,9\} $, ${{r}_{5}} \in \{ 0,1\} $, ${{r}_{6}} \in \{ 0,1,...,81\} $ и ${{r}_{7}} \in \{ 63,64,...,149\} $.

Доказательство. Упрощения формул (+).

Имеем $p_{{23}}^{2} = 153$, поэтому [223] = –r₄ – r₆ + + $162 \leqslant 153$ и $9 \leqslant {{r}_{4}} + {{r}_{6}}$. По лемме 2 имеем $88 \leqslant [222] = {{r}_{4}} + {{r}_{5}} - {{r}_{7}} + 237 \leqslant 184$. Так как $\{ v,w\} \cup \Lambda (v) \cup \Lambda (w)$ содержит $530 - [222]$ вершин, то $98 \leqslant [222] \leqslant 184$.

Лемма 3. Пусть $d(u,v)\, = \,d(u,w)\, = \,2$, $d(v,w)$ = 3. Тогда либо ${{r}_{{25}}} = 0$ и выполняются равенства:

1) $[112] = [121] = 0$, $[113] = [131] = 1$, [122] = = $ - {{r}_{{22}}} + 14$, $[123] = [132] = {{r}_{{22}}}$, $[133] = - {{r}_{{22}}} + 8$;

2) $[212] = {{r}_{{26}}} + 7$, $[213] = - {{r}_{{26}}} + 7$, $[221] = - {{r}_{{27}}}$ + 14, $[222] = - {{r}_{{24}}} - {{r}_{{26}}} + 257$, $[223] = {{r}_{{24}}} + {{r}_{{26}}} + {{r}_{{27}}} - 7$, $[231] = {{r}_{{27}}}$, $[232] = {{r}_{{24}}}$, $[233] = - {{r}_{{24}}} - {{r}_{{27}}} + 152$;

3) $[312] = - {{r}_{{26}}} + 9$, $[313]\, = \,{{r}_{{26}}}$, $[321] = {{r}_{{27}}} + 2$, [322] = = ${{r}_{{22}}} + {{r}_{{24}}} + {{r}_{{26}}}$, $[323] = - {{r}_{{22}}} - {{r}_{{24}}} - {{r}_{{26}}} - {{r}_{{27}}}$ + 151, $[331] = - {{r}_{{27}}}$ + 7, $[332] = - {{r}_{{22}}} - {{r}_{{24}}}$ + 144, $[333] = {{r}_{{22}}} + {{r}_{{24}}} + {{r}_{{27}}}$ – 70,

${{r}_{{22}}}\, \in \,\{ 0,1,...,8\} $, ${{r}_{{24}}}\, \in \,\{ 55,56,...,151\} $, ${{r}_{{27}}} \in \{ 0,1$, ..., 7}, ${{r}_{{26}}} \in \{ 0,1,...,7\} $,

либо ${{r}_{{25}}} = 1$ и выполняются равенства:

4) $[112] = [121] = 1$, $[113] = [131] = 0$, [122] = = $ - {{r}_{{22}}} + 13$, $[123] = [132] = {{r}_{{22}}}$, $[133] = - {{r}_{{22}}} + 9$;

5) $[212] = {{r}_{{26}}} + 6$, $[213] = - {{r}_{{26}}} + 8$, $[221] = - {{r}_{{27}}}$ + 14, $[222] = - {{r}_{{24}}} - {{r}_{{26}}} + {\text{258}}$, $[223] = {{r}_{{24}}} + {{r}_{{26}}} + {{r}_{{27}}} - 8$, $[231] = {{r}_{{27}}}$, $[232] = {{r}_{{24}}}$, $[233] = - {{r}_{{24}}} - {{r}_{{27}}} + 152$;

6) $[312] = - {{r}_{{26}}} + 9$, $[313] = {{r}_{{26}}}$, $[321] = {{r}_{{27}}} + 1$, $[322] = {{r}_{{22}}} + {{r}_{{24}}} + {{r}_{{26}}}$, $[323] = - {{r}_{{22}}} - {{r}_{{24}}} - {{r}_{{26}}} - {{r}_{{27}}}$ + + 152, $[331] = - {{r}_{{27}}} + 8$, $[332] = - {{r}_{{22}}} - {{r}_{{24}}} + 144$, $[333] = {{r}_{{22}}} + {{r}_{{24}}} + {{r}_{{27}}} - 71$,

${{r}_{{22}}}\, \in \,\{ 0,1,...,9\} $, ${{r}_{{24}}}\, \in \,\{ 54,55,...,151\} $, ${{r}_{{27}}} \in \{ 0,1$, ..., 8}, ${{r}_{{26}}} \in \{ 0,1,...,8\} $.

Доказательство. Упрощения формул (+) дают равенства

$[112] = {{r}_{{25}}}$, $[113] = - {{r}_{{25}}} + 1$, $[121] = {{r}_{{23}}}$, [122] = = $ - {{r}_{{22}}} - {{r}_{{23}}}$ + 14, $[123] = {{r}_{{22}}}$, $[131] = - {{r}_{{23}}} + 1$, $[132] = {{r}_{{22}}} + {{r}_{{23}}} - {{r}_{{25}}}$, $[133] = - {{r}_{{22}}} + {{r}_{{25}}} + 8$;

$[212] = - {{r}_{{25}}} + {{r}_{{26}}} + 7$, $[213] = {{r}_{{25}}} - {{r}_{{26}}} + 7$, [221] = = $ - {{r}_{{27}}}$ + 14, $[222] = - {{r}_{{24}}} + {{r}_{{25}}} - {{r}_{{26}}}$, [223] = r₂₄ – r₂₅ + + ${{r}_{{26}}} + {{r}_{{27}}}$ – 7, $[231] = {{r}_{{27}}}$, $[232] = {{r}_{{24}}}$, [233] = $ - {{r}_{{24}}} - {{r}_{{27}}}$ + + 152;

$[312] = - {{r}_{{26}}} + 9$, $[313] = {{r}_{{26}}}$, $[321] = - {{r}_{{23}}} + {{r}_{{27}}} + 2$, $[322] = {{r}_{{22}}} + {{r}_{{23}}} + {{r}_{{24}}} - {{r}_{{25}}} + {{r}_{{26}}}$, [323] = –r₂₂ – r₂₄ + + ${{r}_{{25}}} - {{r}_{{26}}} - {{r}_{{27}}}$ + 151, $[331] = {{r}_{{23}}} - {{r}_{{27}}}$ + 7, [332] = = $ - {{r}_{{22}}}\, - \,{{r}_{{23}}}\, - \,{{r}_{{24}}}\, + \,{{r}_{{25}}}$ + 144, $[333]\, = \,{{r}_{{22}}}\, + \,{{r}_{{24}}}\, - \,{{r}_{{25}}}\, + \,{{r}_{{27}}}$ – ‒ 70,

где r₂₂, ${{r}_{{27}}}\, \in \,\{ 0,1,...,14\} $, ${{r}_{{23}}}\, \in \,\{ 0,1,...,7\} $, ${{r}_{{24}}}\, \in \,\{ 0,1$, ..., 152}, ${{r}_{{25}}} \in \{ 0,1\} $, ${{r}_{{26}}} \in \{ 0,1,...,9\} $.

Симметризация. Верны равенства [112] = r₂₅ = = $[121]{\kern 1pt} ' = r{{{\text{'}}}_{{23}}}$, $[122] = - {{r}_{{22}}} - {{r}_{{23}}} + 14$, поэтому ${{r}_{{22}}}\, + \,{{r}_{{23}}}$ = $r{{{\text{'}}}_{{22}}} = r{{{\text{'}}}_{{23}}}$,

Далее, $[212] = - {{r}_{{25}}} + {{r}_{{26}}} + 7 = [221]{\kern 1pt} ' = - r{{{\text{'}}}_{{27}}} + 14$, поэтому $ - {{r}_{{25}}} + {{r}_{{26}}} + r{{{\text{'}}}_{{27}}} = 7$, $[233] = - {{r}_{{24}}} - {{r}_{{27}}} + 152$ и ${{r}_{{24}}} + {{r}_{{27}}} = r{{{\text{'}}}_{{24}}} + {{r}_{{27}}}{\text{'}}$.

Пусть ${{r}_{{25}}} = 0$. Тогда $r{{{\text{'}}}_{{23}}} = 0$, ${{r}_{{22}}} + {{r}_{{23}}} = r{{{\text{'}}}_{{22}}} = {{r}_{{22}}}$ и ${{r}_{{26}}} + r{{{\text{'}}}_{{27}}} = 7$. Отсюда ${{r}_{{23}}} = 0$ и выполняются равенства (1–3).

Пусть ${{r}_{{25}}} = 1$. Тогда $r{{{\text{'}}}_{{23}}} = 1$, ${{r}_{{22}}} + {{r}_{{23}}} = r{{{\text{'}}}_{{22}}} + 1$ = = r₂₂ + 1 и ${{r}_{{26}}} + r{{{\text{'}}}_{{27}}} = 8$. Отсюда ${{r}_{{23}}} = 1$ и выполняются равенства (4–6). Лемма доказана.

По лемме 3 имеем $99 \leqslant [222]$ = –r₂₄ + r₂₅ – ‒ ${{r}_{{26}}} + 257 \leqslant 204$.

Лемма 4. Пусть $d(u,v) = d(u,w) = d(v,w) = 2$. Тогда либо ${{r}_{{16}}} = 1$ и выполняются равенства:

1) $[111] = 0$, $[112] = [121] = 1$, $[113] = [131] = 0$, $[122] = 13 - {{r}_{{14}}}$, $[123] = [132] = {{r}_{{14}}}$, $[133] = 9 - {{r}_{{14}}}$;

2) $[211] = 1$, $[212] = [221] = 13 - {{r}_{{14}}}$, $[213] = [231]$ = = r₁₄, $[222] = {{r}_{{14}}} - {{r}_{{15}}} + 250$, $[223] = [232] = {{r}_{{15}}}$, [233] = = $ - {{r}_{{14}}} - {{r}_{{15}}} + 153$;

3) $[311] = 0$, $[312] = [321] = {{r}_{{14}}}$, [313] = [331] = = $ - {{r}_{{14}}} + 9$, $[322] = {{r}_{{15}}}$, $[323] = [332] = - {{r}_{{14}}} - {{r}_{{15}}} + 153$, $[333] = 2{{r}_{{14}}} + {{r}_{{15}}} - 81$,

либо ${{r}_{{20}}} = 1$ и выполняются равенства:

4) $[111] = [112] = [121] = 0$, $[113] = [131] = 1$, $[122] = 14 - {{r}_{{14}}}$, $[123] = [132] = {{r}_{{14}}}$, $[133] = 8 - {{r}_{{14}}}$;

5) $[211]\, = \,0$, $[212] = [221] = 14 - {{r}_{{14}}}$, $[213] = [231]$ = = r₁₄, $[222] = {{r}_{{14}}} - {{r}_{{15}}} + 249$, $[223] = [232] = {{r}_{{15}}}$, $[233] = - {{r}_{{14}}} - {{r}_{{15}}} + 153$;

6) $[311] = 1$, $[312] = [321] = {{r}_{{14}}}$, [313] = [331] = = $ - {{r}_{{14}}} + 8$, $[322] = {{r}_{{15}}}$, $[323] = [332] = - {{r}_{{14}}} - {{r}_{{15}}} + 153$, $[333] = 2{{r}_{{14}}} + {{r}_{{15}}} - 80$,

либо ${{r}_{{16}}} = {{r}_{{20}}} = 0$ и выполняются равенства:

7) $[111] = 1$, $[112] = [121] = [113] = [131] = 0$, $[122] = 14 - {{r}_{{14}}}$, $[123] = [132] = {{r}_{{14}}}$, $[133] = 9 - {{r}_{{14}}}$;

8) $[211] = 0$, $[212] = [221] = 14 - {{r}_{{14}}}$, [213] = [231] = = r₁₄, $[222] = {{r}_{{14}}} - {{r}_{{15}}} + 249$, $[223] = [232] = {{r}_{{15}}}$, [233] = = $ - {{r}_{{14}}} - {{r}_{{15}}} = 153$;

9) $[311]\, = \,0$, $[312]\, = \,[321]\, = \,{{r}_{{14}}}$, $[313] = [331]$ = –r₁₄ + 9, $[322] = {{r}_{{15}}}$, $[323] = [332] = - {{r}_{{14}}} - {{r}_{{15}}} + 153$, [333] = = $2{{r}_{{14}}} + {{r}_{{15}}} - 81$,

где ${{r}_{{14}}} \in \{ 0,1,...,9\} $, ${{r}_{{15}}} \in \{ 63,64,...,153\} $.

Доказательство. Упрощения формул (+) дают равенства

$[111] = - {{r}_{{14}}} - {{r}_{{15}}}\, - \,{{r}_{{16}}}\, + \,{{r}_{{18}}}\, - \,{{r}_{{20}}}\, + \,{{r}_{{21}}}\, + \,1$, [112] = r₁₆, $[113] = {{r}_{{14}}} + {{r}_{{15}}} - {{r}_{{18}}} + {{r}_{{20}}} - {{r}_{{21}}}$, $[121] = {{r}_{{19}}}$, $[122] = {{r}_{{17}}}$, $[123] = - {{r}_{{17}}} - {{r}_{{19}}} + 14$, $[131] = {{r}_{{14}}} + {{r}_{{15}}} + {{r}_{{16}}} - {{r}_{{18}}} - {{r}_{{19}}} + {{r}_{{20}}} - {{r}_{{21}}}$, [132] = = $ - {{r}_{{16}}} - {{r}_{{17}}}$ + 14, [133] = $ - {{r}_{{14}}} - {{r}_{{15}}}$ + r₁₇ + r₁₈ + r₁₉ – ‒ ${{r}_{{20}}} + {{r}_{{21}}} - 5$;

$[211]\, = \,{{r}_{{14}}}\, + \,{{r}_{{15}}}\, + \,{{r}_{{16}}}\, - \,{{r}_{{18}}}\, - \,{{r}_{{21}}}$, $[212] = - {{r}_{{14}}} - {{r}_{{16}}}$ + 14, $[213] = - {{r}_{{15}}} + {{r}_{{18}}} + {{r}_{{21}}}$, $[221] = - {{r}_{{14}}} - {{r}_{{15}}} - {{r}_{{16}}} + {{r}_{{21}}}$ + 14, $[222] = {{r}_{{14}}} + {{r}_{{16}}} - {{r}_{{21}}} + 249$, $[223] = {{r}_{{15}}}$, $[231] = {{r}_{{18}}}$, $[232] = {{r}_{{21}}}$, $[233] = - {{r}_{{18}}} - {{r}_{{21}}} + 153$;

$[311] = {{r}_{{20}}}$, $[312] = {{r}_{{14}}}$, $[313] = - {{r}_{{14}}} - {{r}_{{20}}} + 9$, [321] = = ${{r}_{{14}}}\, + \,{{r}_{{15}}}\, + \,{{r}_{{16}}}\, - \,{{r}_{{19}}}\, - \,{{r}_{{21}}}$, $[322] = - {{r}_{{14}}}\, - \,{{r}_{{16}}}\, - \,{{r}_{{17}}}\, + \,{{r}_{{21}}}$ + 14, $[323] = - {{r}_{{15}}} + {{r}_{{17}}} + {{r}_{{19}}}$ + 139, [331] = –r₁₄ – r₁₅ – r₁₆ + + ${{r}_{{19}}} - {{r}_{{20}}} + {{r}_{{21}}}$ + 9, $[332] = {{r}_{{16}}} + {{r}_{{17}}} - {{r}_{{21}}}$ + 139, $[333] = {{r}_{{14}}} + {{r}_{{15}}} - {{r}_{{17}}} - {{r}_{{19}}} + {{r}_{{20}}}$ – 67,

где ${{r}_{{14}}},{{r}_{{20}}} \in \{ 0,1,...,9\} $, ${{r}_{{15}}} \in \{ 0,1,...,167\} $, r₁₆, r₁₇, ${{r}_{{19}}} \in \{ 0,1,...,14\} $, ${{r}_{{18}}},{{r}_{{21}}}$ $ \in \{ 0,1,...,153\} $.

Симметризация. Верны равенства [112] = r₁₆ = $r_{{16}}^{*}$, $[121] = {{r}_{{19}}} = r_{{19}}^{ \sim }$, ${{r}_{{16}}} = r_{{19}}^{'}$, $[122] = {{r}_{{17}}} = r_{{17}}^{'}$, [223] = r₁₅ = = $r_{{15}}^{*}$, $[232] = {{r}_{{21}}} = r_{{21}}^{ \sim }$, $[311] = {{r}_{{20}}} = r_{{20}}^{'}$, $[231] = {{r}_{{18}}}$, $[312] = {{r}_{{14}}}$ и $r_{{18}}^{*} = r_{{14}}^{'}$.

Так как $[112] = {{r}_{{16}}} = r_{{16}}^{ * }$, то $r_{{16}}^{'} = r_{{16}}^{ \sim }$, поэтому $[121]* = {{r}_{{19}}}* = [211] = {{r}_{{14}}} + {{r}_{{15}}} + {{r}_{{16}}} - {{r}_{{18}}} - {{r}_{{21}}}$ и r₁₄ + r₁₅ + + r₁₆ = ${{r}_{{18}}} + {{r}_{{19}}} + {{r}_{{21}}}$. Аналогично, $[121] = {{r}_{{19}}} = r_{{19}}^{ \sim }$ влечет $r_{{19}}^{'} = r_{{19}}^{*}$, поэтому [112] = r₁₆ = [211] = = ${{r}_{{14}}} + {{r}_{{15}}} + {{r}_{{16}}} - {{r}_{{18}}} - {{r}_{{21}}}$ и ${{r}_{{16}}} = {{r}_{{19}}}$. Отсюда ${{r}_{{16}}} = r_{{16}}^{'} = r_{{16}}^{*} = r_{{16}}^{ \sim }$ и ${{r}_{{19}}} = r_{{19}}^{'} = r_{{19}}^{*} = r_{{19}}^{ \sim }$.

Далее, $[122] = {{r}_{{17}}} = r_{{17}}^{'}$ влечет $r_{{17}}^{*} = r_{{17}}^{ \sim }$, поэтому $[212] = - {{r}_{{14}}} - {{r}_{{16}}} + 14$ = [221]' = $ - r{{{\text{'}}}_{{14}}} - r{{{\text{'}}}_{{15}}} - r{{{\text{'}}}_{{16}}} + r{{{\text{'}}}_{{21}}}$ + + 14 и ${{r}_{{15}}} = {{r}_{{21}}}$. Теперь из равенства ${{r}_{{14}}} + {{r}_{{15}}} + {{r}_{{16}}} = {{r}_{{18}}} + {{r}_{{19}}} + {{r}_{{21}}}$ следует, что ${{r}_{{14}}} = {{r}_{{18}}}$. Аналогично, $[223] = {{r}_{{15}}} = r_{{15}}^{*}$ влечет $r_{{15}}^{'} = r_{{15}}^{ \sim }$, следовательно, [232] = ${{r}_{{21}}} = [322] = - {{r}_{{14}}} - {{r}_{{16}}} - {{r}_{{17}}} + {{r}_{{21}}}$ + + 14 и ${{r}_{{14}}} + {{r}_{{16}}} + {{r}_{{17}}}$ = 14.

Отсюда следуют равенства

$[111] = - {{r}_{{16}}} - {{r}_{{20}}} + 1$, $[112] = [121] = {{r}_{{16}}}$, [113] = = $[131]$ = r₂₀, $[122] = {{r}_{{17}}}$, $[123] = [132] = {{r}_{{14}}}$, $[133] = 9 - {{r}_{{14}}} - {{r}_{{20}}}$;

$[211] = {{r}_{{16}}}$, $[212] = [221] = {{r}_{{17}}}$, $[213] = [231] = {{r}_{{14}}}$, $[222] = - {{r}_{{17}}} - {{r}_{{15}}}$ + 263, [223] = $[232] = {{r}_{{15}}}$, $[233] = - {{r}_{{14}}} - {{r}_{{15}}}$ + 153;

$[311] = {{r}_{{20}}}$, $[312] = [321] = {{r}_{{14}}}$, [313] = [331] = = $ - {{r}_{{14}}} - {{r}_{{20}}} + 9$, $[322] = {{r}_{{15}}}$, [323] = [332] = $ - {{r}_{{14}}} - {{r}_{{15}}}$ + + 153, $[333] = 2{{r}_{{14}}} + {{r}_{{15}}} + {{r}_{{20}}} - 81$,

где ${{r}_{{16}}} + {{r}_{{20}}} \leqslant 1$, ${{r}_{{14}}} + {{r}_{{20}}} \leqslant 9$, ${{r}_{{14}}} + {{r}_{{15}}} \leqslant 153$, ${{r}_{{15}}} + {{r}_{{17}}} \leqslant 167$.

Допустим, что ${{r}_{{16}}} = 1$. Тогда ${{r}_{{20}}} = 0$, ${{r}_{{14}}} + {{r}_{{17}}} = 13$ и выполняются равенства из пунктов (1)–(3) заключения леммы 4.

Допустим, что ${{r}_{{20}}} = 1$. Тогда ${{r}_{{16}}} = 0$, ${{r}_{{14}}} + {{r}_{{17}}} = 14$ и выполняются равенства из пунктов (4)–(6) заключения леммы 4.

Допустим, что ${{r}_{{20}}} = {{r}_{{16}}} = 0$. Тогда ${{r}_{{14}}} + {{r}_{{17}}} = 14$ и выполняются равенства из пунктов (7)–(9) заключения леммы 4. Лемма 4 доказана.

По лемме 4 имеем $96 \leqslant [222] = \leqslant 190$.

Пусть $d(u,v) = 2$. Подсчитаем число $g$ пар вершин y, z на расстоянии 2 в графе $\Gamma $, где $y \in \left\{ {\begin{array}{*{20}{c}} {uv} \\ {21} \end{array}} \right\}$ и $z \in \left\{ {\begin{array}{*{20}{c}} {uv} \\ {22} \end{array}} \right\}$. С одной стороны, $p_{{21}}^{2} = 14$, по лемме 2 имеем [212] = $ - {{r}_{5}} + {{r}_{6}} + {{r}_{7}} - 135 \leqslant 95$ (${{r}_{5}} \in \{ 0,1\} $, ${{r}_{6}} \in \{ 0,1,...,81\} $, ${{r}_{7}} \in \{ 63,64,...,149\} $) и $g \leqslant 1330$. С другой стороны, $p_{{22}}^{2} = 264$, по лемме 4 имеем [212] = $14 - {{r}_{{14}}}$ и $g = 3696 - \sum\limits_i {r_{{14}}^{i}} \leqslant 1330$. Поэтому $2366 \leqslant \sum\limits_i {r_{{14}}^{i}} $ и $10.1 \leqslant \sum\limits_i {r_{{14}}^{i}{\text{/}}264} $. Противоречие с тем, что ${{r}_{{14}}} \leqslant 9$.

Полученное противоречие завершает доказательство следствия 1.

Пусть $\Gamma $ – дистанционно-регулярный граф с массивом пересечений $\{ {{b}^{2}}(b\, - \,1){\text{/}}2,(b\, - \,1)({{b}^{2}}\, - \,b\, + \,2){\text{/}}2,$ $b(b - 1){\text{/}}4;1,b(b - 1){\text{/}}4,b{{(b - 1)}^{2}}{\text{/}}2\} $. Тогда число вершин      равно $({{b}^{2}} - b + 1)({{b}^{2}} + 1)$, $\Gamma $ имеет спектр                 $({{b}^{3}} - {{b}^{2}}){\text{/}}{{2}^{1}}$, $({{b}^{2}} - b){\text{/}}{{2}^{{({{b}^{2}} - b + 1)b}}}$, $( - b \pm \sqrt {{{b}^{3}} - {{b}^{2}} + b} ){\text{/}}{{2}^{{({{b}^{2}} - b + 2)(b - 1)b/2}}}$, и дуальную матрицу Q собственных значений

Лемма 5. Для чисел пересечений графа $\Gamma $ верны равенства

Доказательство. Прямые вычисления.

Зафиксируем вершины $u,{v},w$ графа $\Gamma $ и положим $\{ ijh\} = \left\{ {\begin{array}{*{20}{c}} {uvw} \\ {ijh} \end{array}} \right\}$, $[ijh] = \left[ {\begin{array}{*{20}{c}} {uvw} \\ {ijh} \end{array}} \right]$.

Лемма 6. Пусть $d(u,v)\, = \,d(u,w)\, = \,2$, $d(v,w)$ = 1. Тогда тройные числа пересечений равны:

$[111] = {{b}^{4}} - 7{{b}^{3}}{\text{/}}2 + 13{{b}^{2}}{\text{/}}2 - 6b - {{r}_{2}} - {{r}_{3}} - {{r}_{4}}$, [121] = = [211] = $ - {{b}^{4}} + 7{{b}^{3}}{\text{/}}2 - 25{{b}^{2}}{\text{/}}4 + 23b{\text{/}}4 + {{r}_{2}} + {{r}_{3}} + {{r}_{4}}$, $[122] = {{b}^{4}} - 7{{b}^{3}}{\text{/}}2 + 13{{b}^{2}}{\text{/}}2 - 7b - {{r}_{1}} - {{r}_{2}} - {{r}_{3}} + 1$, $[123]\, = \,[132]\, = \,{{b}^{3}}{\text{/}}2 - 5{{b}^{2}}{\text{/}}4 + 7b{\text{/}}4 + {{r}_{1}} - {{r}_{4}} - 1$, [133] = = $ - {{b}^{3}}{\text{/}}2 + 3{{b}^{2}}{\text{/}}2 - 2b - {{r}_{1}} + {{r}_{4}} + 1$;

$[211] = - {{b}^{4}} + 7{{b}^{3}}{\text{/}}2 - 6{{b}^{2}} + 9b{\text{/}}2 + {{r}_{3}} + {{r}_{4}}$, [212] = = [221] = ${{b}^{4}} - 3{{b}^{3}} + 5{{b}^{2}} - 4b - {{r}_{3}} - {{r}_{4}} - 1$, $[222] = {{r}_{3}}$, $[223] = [232] = {{r}_{4}}$, $[233] = {{b}^{3}}{\text{/}}2 - {{b}^{2}} + 3b{\text{/}}2 - {{r}_{4}}$;

$[311] = {{r}_{2}}$, $[312] = [321] = {{b}^{2}}{\text{/}}4 - b{\text{/}}4 - {{r}_{2}}$, [322] = = ${{b}^{3}}{\text{/}}2 - 3{{b}^{2}}{\text{/}}2 + 2b + {{r}_{1}} + {{r}_{2}}$, [323] = [332] = b²/4 – ‒ $b{\text{/}}4 - {{r}_{1}}$, $[333] = {{r}_{1}}$.

Доказательство. Упрощения формул (+).

По лемме 6 имеем [233] = b³/2 – b² + + $3b{\text{/}}2 - {{r}_{4}} \geqslant 0$, поэтому [222] = ${{r}_{4}}\, \leqslant \,{{b}^{3}}{\text{/}}2\, - \,{{b}^{2}}\, + \,3b{\text{/}}2$.

Положим $\Delta = {{\Gamma }_{2}}(u)$, $\Lambda = {{\Delta }_{2}}$. Тогда $\Lambda $ – регулярный граф степени $p_{{22}}^{2} = {{b}^{4}} - 3{{b}^{3}} + 5{{b}^{2}} - 4b - 1$ на ${{k}_{2}} = ({{b}^{2}} - b + 2)({{b}^{2}} - b) = {{b}^{4}} - 2{{b}^{3}} + 3{{b}^{2}} - 2b$ вершинах. Пусть $d(u,v) = d(u,w) = 2$, $d(v,w) = 1$. Тогда $\Lambda (v) \cap \Lambda (w)$ содержит не менее b⁴ – $4{{b}^{3}}\, + \,7{{b}^{2}}\, - \,6b$ – 1 вершин. Поэтому b⁴ – 4b³ + 7b² – 6b – ‒ $1 \leqslant {{b}^{3}}{\text{/}}2 - {{b}^{2}} + 3b{\text{/}}2$ и b⁴ + $8{{b}^{2}} \leqslant 9{{b}^{3}}{\text{/}}2 + 15b{\text{/}}2$ + 1. Отсюда $b \leqslant 4$.

Но в случае b = 3 имеем ${{b}^{4}} + 8{{b}^{2}} = 153$, $9{{b}^{3}}{\text{/}}2 + 15b{\text{/}}2 + 1 = 121.5 + 22.5 + 1 = 145$, противоречие. Аналогично, в случае $b = 4$ имеем ${{b}^{4}} + 8{{b}^{2}} = 256 + 128$ = 384, $9{{b}^{3}}{\text{/}}2 + 15b{\text{/}}2 + 1$ = = $288 + 30 + 1 = 319$, противоречие.

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

Пусть $\Gamma $ является графом Шилла с массивом пересечений $\{ (s + 1)({{s}^{3}} - 1),{{s}^{4}},{{s}^{3}};1,{{s}^{2}},s({{s}^{3}} - 1)\} $. Многочлен Тервелигера (см. [7]) графа $\Gamma $ равен –s(s³ – – ${{s}^{2}}\, - \,s\, - \,x$ – 1)(s³ – sx – s – $x - 1)(s + x + 1)$(x + 1), поэтому собственные значения локального подграфа принадлежат [–s – 1, $ - 1] \cup [({{s}^{3}} - s - 1){\text{/}}(s + 1)$, s³ – s² – s – 1]. С другой стороны, по предложению 4.4.3 из [1] собственные значения локального подграфа принадлежат отрезку [–s⁴/(s³ – 1) – 1, ${{s}^{4}}{\text{/}}({{s}^{2}} + s + 1)$ – 1].

Положим $A = ({{s}^{3}} - s - 1){\text{/}}(s + 1)$, B = ${{s}^{4}}{\text{/}}({{s}^{2}}$ + s + + 1) – 1. Тогда B – A = $({{s}^{4}}(s + 1) - ({{s}^{3}} - s - 1)$(s² + s + + 1) – $(s + 1)({{s}^{2}} + s + 1)){\text{/}}((s + 1)({{s}^{2}} + s + 1))$ = = $ - {{s}^{3}}{\text{/}}((s + 1)({{s}^{2}} + s + 1))$ < 0, поэтому $B < A$ и все неглавные собственные значения локального подграфа отрицательны. Отсюда локальный подграф является объединением изолированных $({{a}_{1}} + 1)$-клик. Противоречие с тем, что a₁ + 1 = ${{s}^{3}} - s - 1$ не делит $k = (s + 1)({{s}^{3}} - 1)$.

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