Дистанционно-регулярный граф

Граф Шрикханде - дистанционно-регулярный граф, не являющийся дистанционно-транзитивным

Дистанционно-регулярный граф (англ. distance-regular graph) - это такой регулярный граф, у которого для двух любых вершин $v$ и $w$, расположенных на одинаковом расстоянии $j$ друг от друга справедливо, что количество вершин инцидентных к $v$, и при этом находящихся на расстоянии $j-1$ от вершины $w$, зависит только от расстояния $j$ между вершинами $v$ и $w$ ; более того количество инцидентных к $v$ вершин, и находящихся на расстоянии $j+1$ от вершины $w$, также зависит только от расстояния $j$.

Определение

Определение дистанционно-регулярного графа  :

Дистанционно-регулярный граф - это неориентрированный, связанный, ограниченный, регулярный граф $\Gamma =(V,E)$ диаметра $D$, для которого справедливо, что существуют числа

$b_{0}=k\quad b_{1},\,\dots \,,\,b_{D-1}\ ,\quad c_{1}=1,\quad c_{2},\,\dots ,\,c_{D}$

такие, что для каждой пары вершин $(u,v)$, отстоящих друг от друга на расстоянии $d(u,v)=j$ справедливо:

(1) число вершин, инцидентных $u$, и находящихся на расстоянии $j-1$ от $v$ есть $c_{j}$ ($1\leq j\leq D$)

(2) число вершин, инцидентных $u$, и находящихся на расстоянии $j+1$ от $v$ есть $b_{j}$ ($0\leq j\leq D-1$).

Массив $\left\{k,\,b_{1},\,\dots ,\,b_{D-1}\,;1,\,c_{2},\,\dots ,\,c_{D}\right\}$ есть массив пересечений дистанционно-регулярного графа.

Дистанционно-регулярный и дистанционно-транзитивный графы

На первый взгляд дистанционно-транзитивный граф и дистанционно-регулярный граф являются очень близкими понятиями. Действительно, каждый дистанционно-транзитивный граф является дистанционно-регулярным. Однако их природа разная. Если дистанционно-транзитивный граф определяется исходя из симметрии графа через условие автоморфизма, то дистанционно-регулярный граф определяется из условия его комбинаторной регулярности .

Автоморфизм дистанционно-транзитивного графа вызывает его регулярность, и соответственно, наличие чисел пересечений $a_{j},\,b_{j},\,c_{j}$. Возникает обратный вопрос, если существует комбинаторная регулярность, и определены числа пересечений для графа, и он дистанционно-регулярный, то следует ли из этого автоморфизм? Ответ - нет.

Если из дистанционно-транзитивности графа следует его дистанционно-регулярность, то обратное не верно.

Это было доказано в 1969 г, еще до введения в обиход термина дистанционно-транзитивный граф, группой советских математиков (Адельсон-Вельский Г.М. , Вейсфелер Б.Ю., Леман А.А., Фараджев И.А. ). Наименьший дистанционно-регулярный граф, не являющийся дистанционно-транзитивным — это граф Шрикханда. Единственный тривалентный граф этого типа — это 12-клетка Татта, граф с 126 вершинами.

Массив пересечений дистанционно-регулярного графа

Пусть $\Gamma =(V,E)$ - транзитивно - регулярный граф диаметра $D$ и степени $k$ , а $u$ и $v$ есть пара вершин, отстоящих друг от друга на расстояние $d=(u,v)$. Тогда множество вершин, инцидентных к $u$ можно разбить на три множества $A$, $B$ и $C$ в зависимости от их расстояния $d(v,w)$ до вершины $v$, где вершина $w$ инцидентна к $u$  :

$\left\{w\in A\,:d(v,w)=j\right\},\quad \left\{w\in B\,:d(v,w)=j+1\right\},\quad \left\{w\in C\,:d(v,w)=j-1\right\}$.

Кардинальные числа $|A|,\,|B|,\,|C|$ этих множеств $a_{j}=|A|,\,b_{j}=|B|,\,c_{j}=|C|$ есть числа пересечений, а массив пересечений есть

$\iota (\Gamma )={\begin{Bmatrix}\ast &c_{1}&c_{2}&\dots &c_{d-1}&c_{d}\\a_{0}&a_{1}&a_{2}&\dots &a_{d-1}&a_{d}\\b_{0}&b_{1}&b_{2}&\dots &b_{d-1}&\ast \\\end{Bmatrix}}$

Так как степень графа $k$, то $b_{0}=k$ , $c_{0}=0$ а $c_{1}=1$. Более того, $a_{i}+b_{i}+c_{i}=k$. Поэтому массив пересечений записывается как:

$\iota (\Gamma )={\begin{Bmatrix}k,\,b_{1},\,\dots ,\,b_{d-1}\,;\,1,\,c_{2},\,\dots ,\,c_{d}\end{Bmatrix}}$

Свойства массива пересечений

• Каждая вершина имеет постоянное число вершин $k_{j}$, отстоящих от нее на расстояние $j$, причем $k_{0}=1$ и $k_{j+1}={\frac {b_{j}k_{j}}{c_{j+1}}}$ для всех $j=0,\,1,\,\dots ,\,D-1$

Свойства

• Дистанционно-регулярный граф с диаметром 2 является сильно регулярным и обратное тоже верно (при условии, что граф является связным).

Матрицы дистанционной связности

Предположим, что G — связный дистанционно-регулярный граф. Для любого расстояния i = 1, …, d, мы можем образовать граф G_i, в котором вершины смежны, если расстояние между ними в графе G равно i. Пусть A_i — матрица смежности графа G_i. Например, A₁ — это матрица смежности A графа G. Пусть также, A₀ = I — единичная матрица. Это даёт нам d + 1 матриц A₀, A₁, …, A_d, называемых матрицами расстояний графа G. Их сумма — это матрица J, в которой каждое значение равно 1. Имеется важная формула:

$AA_{i}=b_{i-1}A_{i-1}+a_{i}A_{i}+c_{i+1}A_{i+1}.$

Из формулы следует, что каждая A_i является полиномиальной функцией от A степени i, и что A является корнем многочлена степени d + 1.

Более того, A имеет в точности d + 1 различных собственных значений, а именно собственных значений матрицы пересечений B, из которых максимальным является k степень.

Множество матриц расстояний является векторным подпространством векторного пространства всех n × n вещественных матриц. Замечателен факт, что произведение A_i A_j любых двух матриц расстояний является линейной комбинацией матриц расстояний:

$A_{i}A_{j}=\sum _{k=0}^{d}p_{ij}^{k}A_{k}.$

Это означает, что матрицы расстояний порождают схему отношений. Теория схем отношений является центральным моментом для изучения дистанционно-регулярных графов. Например, свойство, что A_i является многочленом от A, есть свойство схем отношений.

Примеры

• Полные графы являются дистанционно-регулярными графами с диаметром 1 и степенью v−1.
• Циклы C_2d+1 нечётной длины являются дистанционно-регулярными графами с k = 2 и диаметром d. Числами пересечений a_i = 0, b_i = 1, и c_i = 1, за исключением специальных случаев (смотрите выше) и c_d = 2.
• Все Графы Мура, в частности граф Петерсена и граф Хоффмана — Синглтона, являются дистанционно-регулярными.
• Сильно регулярные графы являются дистанционно-регулярными.
• Нечётные графы являются дистанционно-регулярными.

Литература

• Адельсон-Вельский Г.М., Вейсфелер Б.Ю., Леман А.А., Фараджев И.А. Об одном примере графа, не имеющнго транзитивной группы автоморфизмов // Доклады Академии наук. — 1969. — Т. 185, № 5. — С. 975—976.
• Biggs N.L. Algebraic Graph Theory (англ.). — 2nd. — Cambridge University Press, 1993. — 205 p.

• Brouwer A., Cohen A.M., Neumaier A. Distance Regular Graphs (англ.). — Berlin, New York: Springer-Verlag, 1989. — ISBN 3-540-50619-5, 0-387-50619-5.
• van Dam E.R., Koolen J.H., Tanaka H. Distance-regular graphs (англ.) // The Electronic Journal of Combinatorics : Dynamic surveys. — 2006:DS22. — Apr 15.
• Godsil C. D. Algebraic combinatorics (англ.). — N. Y.: Chapman and Hall, 1993. — P. xvi+362. — (Chapman and Hall Mathematics Series). — ISBN 0-412-04131-6.

• Lauri J., Scapelatto R. Topics in Graph Automorphisms and Reconstruction (англ.). — 2nd. — Combridge: Combridge University Press, 2016. — 188 p.