Доклады Российской академии наук. Математика, информатика, процессы управления, 2020, T. 492, № 1, стр. 54-57

Мы рассматриваем неориентированные графы без петель и кратных ребер. Для вершины a графа Γ через ${{\Gamma }_{i}}(a)$ обозначим i-окрестность вершины a, т.е. подграф, индуцированный Γ на множестве всех вершин, находящихся на расстоянии i от a. Положим $[a] = {{\Gamma }_{1}}(a)$, ${{a}^{ \bot }} = \{ a\} \cup [a]$.

Степенью вершины называется число вершин в ее окрестности. Граф Γ называется регулярным степени k, если степень любой вершины из Γ равна k. Граф $\Gamma $ назовем реберно регулярным с параметрами (${v}$, $k$, $\lambda $), если он содержит ${v}$ вершин, регулярен степени k и каждое его ребро лежит в $\lambda $ треугольниках. Граф Γ – вполне регулярный граф с параметрами (${v}$, $k$, $\lambda $, $\mu $), если он реберно регулярен c соответствующими параметрами, и $[a] \cap [b]$ содержит $\mu $ вершин для любых двух вершин a, b, находящихся на расстоянии 2 в $\Gamma $. Вполне регулярный граф диаметра 2 называется сильно регулярным графом. Максимальные клики графа называются прямыми. Разбиение реберно регулярного графа с параметрами (${v}$, $k$, $\lambda $) кликами порядка $\lambda + 2$ называется спредом.

Система инцидентности с множеством точек $P$ и множеством прямых L называется $\alpha $-частичной геометрией порядка $(s,\;t)$, если каждая прямая содержит ровно $s + 1$ точку, каждая точка лежит ровно на $t + 1$ прямой, любые две точки лежат не более чем на одной прямой, и для любого антифлага $(a,\;l) \in (P,\;L)$ найдется точно α прямых, проходящих через $a$ и пересекаюших l (обозначение $p{{G}_{\alpha }}(s,\;t)$). В случае α = 1 геометрия называется обобщенным четырехугольником и обозначается $GQ(s,\;t)$. Точечный граф геометрии определяется на множестве точек P и две точки смежны, если они лежат на прямой. Точечный граф геометрии $p{{G}_{\alpha }}(s,\;t)$ сильно регулярен с ${v} = (s + 1)$(1 + + st/α), $k = s(t + 1)$, $\lambda = s - 1 + t(\alpha - 1)$, $\mu $ = α(t + 1). Сильно регулярный граф с такими параметрами для некоторых натуральных чисел α, $s$, $t$ называется псевдогеометрическим графом для $p{{G}_{\alpha }}(s,\;t)$.

Если вершины u, w находятся на расстоянии $i$ в Γ, то через ${{b}_{i}}(u,\;w)$ (через ${{c}_{i}}(u,\;w)$) обозначим число вершин в пересечении ${{\Gamma }_{{i + 1}}}(u)$ (${{\Gamma }_{{i - 1}}}(u)$) с $[w]$. Граф $\Gamma $ диаметра d называется дистанционно регулярным с массивом пересечений $\{ {{b}_{0}},{{b}_{1}}, \ldots ,{{b}_{{d - 1}}}$; c₁, ..., c_d}, если значения ${{b}_{i}}(u,\;w)$ и ${{c}_{i}}(u,\;w)$ не зависят от выбора вершин u, w на расстоянии i в Γ для любого $i = 0$, …, d. Положим ${{a}_{i}} = k - {{b}_{i}} - {{c}_{i}}$. Далее, через $p_{{ij}}^{l}(x,y)$ обозначим число вершин в подграфе ${{\Gamma }_{i}}(x) \cap {{\Gamma }_{j}}(y)$ для вершин x, y, находящихся на расстоянии l в графе Γ. В дистанционно регулярном графе числа $p_{{ij}}^{l}(x,\;y)$ не зависят от выбора вершин x, y, обозначаются $p_{{ij}}^{l}$ и называются числами пересечений графа $\Gamma $.

Если Γ – граф диаметра d, $i \in \{ 1,\;2,\; \ldots ,\;d\} $, то граф Γ_i имеет то же самое множество вершин, что и Γ, и вершины $u$, $w$ смежны в Γ_i, если ${{d}_{\Gamma }}(u,w) = i$.

Пусть Γ – антиподальный недвудольный дистанционно регулярный граф диаметра 3. Тогда Γ имеет массив пересечений $\{ k,\;(r - 1){{c}_{2}},\;1;\;1,\;{{c}_{2}},\;k\} $ (${{c}_{2}} < k - 1$) и спектр k¹, n^f, –1^k, $ - {{m}^{g}}$, где n, –m – корни квадратного уравнения ${{x}^{2}} - ({{a}_{1}} - {{c}_{2}})x - k$ = 0, f = $m(r - 1)(k + 1){\text{/}}(m + n)$, g = n(r – 1) $(k + 1)$/(m + n). Если r = 2, то Γ называется графом Тейлора. Если ${{a}_{1}} \ne {{c}_{2}}$, то числа m, $n$ целые и параметры Γ можно выразить через r, $m$, $n$: $k = mn$, c₂ = (m – 1)$(n + 1){\text{/}}r$, ${{a}_{1}} = {{c}_{2}} + n - m$. Условие целочисленности кратностей f, $g$ дает делимость $(r - 1)m({{m}^{2}} - 1)$ на m + n. Наконец, граница Крейна $q_{{33}}^{3} \geqslant 0$ влечет $m \leqslant {{n}^{2}}$, если $r \ne 2$ (см. [1, с. 431]). В случае $m = {{n}^{2}}$, следуя Годсилу, назовем Γ антиподальным графом Крейна. Годсил [2] доказал

Предложение 1. Пусть Γ – антиподальный дистанционно регулярный граф диаметра 3 с собственными значениями k, $n$, –1, –m. Если $m = {{n}^{2}}$, то выполняются следующие утверждения:

1) r делит $n + 1$, $n - 1$ делит a₁и ${{n}^{2}} - 1$ делит c₂;

2) для любой вершины $u \in \Gamma $ граф $\Delta = [u]$ сильно регулярен с собственными значениями a₁ = k(Δ) = = $(n\, - \,1)\left( {\frac{{{{{(n\, + \,1)}}^{2}}}}{{r\, - \,1}}} \right)$, ${{\eta }_{1}} = n - \frac{{(n + 1)}}{r}$ и η₂ = n – $\frac{{{{{(n + 1)}}^{2}}}}{r}$.

Напомним предложение 12.5.2 из [1].

Предложение 2. Пусть Γ – точечный граф обобщенного четырехугольника $GQ(s,t)$, имеющего спред S. Удаляя из Γ ребра, лежащие на прямых из S, получим антиподальный граф с массивом пересечений

Из предложений 1, 2 следует, что точечному графу обобщенного четырехугольника $GQ(q,\;{{q}^{2}})$, имеющего спред, отвечает антиподальный граф Крейна с $r = q + 1$.

Если точечный граф $\Sigma $ для $GQ(q,\;{{q}^{2}})$ имеет автоморфизм $\sigma $ порядка f, фиксирующий каждую компоненту спреда, то граф $\bar {\Sigma } = \Sigma {\text{/}}\langle \sigma \rangle $, вершинами которого являются $\sigma $-орбиты на множестве точек, и две орбиты смежны, если некоторая вершина одной из них смежна с вершиной другой, является дистанционно регулярным с массивом пересечений {q³, $((q + 1){\text{/}}f - 1)({{q}^{2}} - 1)f$, 1; 1, (q² – 1)f, q³}. Теперь из предложения 1 и леммы 6.1 [2] следует

Теорема 1. Пусть q – степень простого числа и f – нетривиальный делитель q + 1. Тогда существует дистанционно регулярный граф с массивом пересечений {q³, $((q + 1){\text{/}}f - 1)({{q}^{2}} - 1)f$, 1; 1, (q² – 1)f, q³}, в котором окрестность Δ любой вершины является псевдогеометрическим графом для $p{{G}_{{f - 1}}}(q - 1$, (q + 1)(f – 1)). При f = 2 получим псевдогеометрический граф для $GQ(q - 1,\;q + 1)$, а при f = 3 получим псевдогеометрический граф для $p{{G}_{2}}(q - 1$, 2q + 2).

В случае f = 4 получим псевдогеометрический граф для $p{{G}_{3}}(q - 1,\;3q + 3)$, 4 делит q + 1. Если $q - 4 \leqslant 5$, то q = 7 и существует граф Тейлора с массивом пересечений {7³, 192, 1; 1, 192, 7³}, в котором окрестности вершин являются псевдогеометрическими графами для $p{{G}_{3}}(6,24)$ (см. следствие 2 из [3]).

В лемме 5.3 из [2] параметр $\lambda (\Delta )$ вычислен неверно. Ввиду теоремы 1 имеем λ(Δ) = q – 2 + + $(f - 2)(f - 1)$(q + 1). Интересно, что в случае $r = (q + 1){\text{/}}2$ (равносильно f = 2) параметр $\lambda (\Delta )$ из леммы 5.3 [2] совпадает с q – 2 + $(f - 2)(f - 1)$(q + 1) и $\Delta $ является псевдогеометрическим графом для $GQ(q - 1,q + 1)$.

Следствие 1. Пусть $q$ – степень нечетного простого числа. Тогда существует антиподальный дистанционно регулярный граф с массивом пересечений {q³, $(q - 1)({{q}^{2}} - 1),\;1;\;1,\;2({{q}^{2}} - 1),\;{{q}^{3}}\} $, в котором окрестности вершин являются псевдогеометрическими графами для $GQ(q - 1,\;q + 1)$.

Дистанционно регулярные графы, в которых окрестности вершин являются псевдогеометрическими графами для $GQ(q - 1,\;q + 1)$, классифицированы в [4] для q = 3, в [5] для q = 4, в [6] для q = 5 и в [7] для q = 7. Однако существование графов с массивами пересечений {125, 96, 1; 1; 48, 125} в [6] и {343, 288, 1; 1, 96, 343} в [7] (обнаруженное в следствии 1) оставалось неизвестным.

Пусть Γ – граф диаметра d и e – натуральное число. Подмножество C вершин графа $\Gamma $ называется e-кодом, если минимальное расстояние между двумя вершинами из C не меньше $2e + 1$. Для e‑кода в дистанционно регулярном графе диаметра $d = 2e + 1$ выполняется граница ${\text{|}}C{\text{|}} \leqslant p_{{dd}}^{d} + 2$. В случае равенства код называется максимальным. Для максимального e-кода в дистанционно регулярном графе диаметра $d = 2e + 1$ выполняется граница ${{c}_{d}} \geqslant {{a}_{d}}p_{{dd}}^{d}$. В случае равенства код называется локально регулярным. Наконец, для e-кода в дистанционно регулярном графе диаметра $d = 2e + 1$ выполняется граница $\left| C \right|\, \leqslant \,{{{{k}_{d}}} \mathord{\left/ {\vphantom {{{{k}_{d}}} {\sum\limits_{i = 0}^e {p_{{id}}^{d}} }}} \right. \kern-0em} {\sum\limits_{i = 0}^e {p_{{id}}^{d}} }}$ + 1. В случае равенства код называется совершенным относительно последней окрестности.

Если дистанционно регулярный граф Γ диаметра 3 содержит максимальный 1-код, являющийся локально регулярным и совершенным относительно последней окрестности, то по предложению 5 из [8] Γ имеет массив пересечений $\{ a(p + 1),\;cp,\;a + 1;\;1,\;c,\;ap\} $ или $\{ a(p + 1),(a + 1)p,c$; 1, c, ap}, где a = a₃, $c = {{c}_{2}}$, $p = p_{{33}}^{3}$.

В случае, когда Γ имеет массив пересечений $\{ a(p + 1),\;cp,\;a + 1;\;1,\;c,\;ap\} $, граф ${{\Gamma }_{3}}$ является псевдогеометрическим для $GQ(p + 1,\;a)$, а максимальному 1-коду отвечает овоид графа Γ. Если a = c + 1, то граф Γ₂ является псевдогеометрическим для $p{{G}_{2}}(p + 1,\;2a)$, а Γ имеет массив пересечений {(c + + 1)(p + 1), $cp,c + 2;1,c,(c + 1)p\} $. Существование дистанционно регулярных графов Γ диаметра 3, для которых графы Γ₂ и Γ₃ сильно регулярны, не известно.

Граф $\Gamma $ является $Q$-полиномиальным, если p² = = 2(a + 1) и Γ₃ – псевдогеометрический граф для $GQ(p + 1,\;{{p}^{2}}{\text{/}}2 - 1)$. В случае p = 4 граф Γ₃ – псевдогеометрический для $GQ(5,\;7)$ и Γ имеет массив пересечений {35, 24, 8; 1, 6, 28}. В случае p = 6 граф Γ₃ – псевдогеометрический для $GQ(7,\;17)$ и $\Gamma $ имеет массив пересечений {119, 96, 18; 1, 16, 102}. В указанной серии $Q$-полиномиальных графов по теореме 3 из [8] графов нет.

Юришич и Видали в [8] рассмотрели дистанционно регулярный граф Γ с массивом пересечений $\{ {{q}^{2}} - 1,\;q(q - 2),\;q + 2;\;1,\;q,\;(q - 2)(q + 1)\} $ (c = q, $p = q - 2$). Этот граф имеет спектр (q² – 1)¹, ${{(2q - 1)}^{{q({{q}^{2}} - 1)/6}}}$, $ - {{1}^{{(q + 1)({{q}^{2}} + q - 2)/2}}}$, $ - {{(q + 1)}^{{q(q - 1)(q - 2)/3}}}$, граф Γ₃ является псевдогеометрическим для $GQ(q - 1$, q + 1) и ${{\bar {\Gamma }}_{2}}$ – псевдогеометрический граф для $p{{G}_{2}}(q - 1,2q + 2)$.

Можно ли так модифицировать окрестности вершин в локальном графе из заключения следствия  1, что получится дистанционно регулярный граф Γ с массивом пересечений $\{ {{q}^{2}} - 1,\;q(q - 2),\;q + 2;\;1,\;q,\;(q - 2)(q + 1)\} $?

Гипотеза. Пусть q – степень нечетного простого числа, $q > 5$. Тогда существует дистанционно регулярный граф с массивом пересечений {q² – 1, $q(q - 2),\;q + 2;\;1,\;q,\;(q - 2)(q + 1)\} $.

Наименьший возможный граф имеет массив пересечений $\{ 48,\;35,\;9;\;1,\;7,\;40\} $.