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

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

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

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

Определение

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

Дистанционно-регулярный граф — это неориентрированный, связанный, ограниченный, регулярный граф $\Gamma =(V,E)$ валентности $k$ и диаметром $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\leqslant j\leqslant D$)

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

Тогда

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

есть массив пересечений графа $\Gamma$ (см. § Массив пересечений), а $a_{j},\,b_{j},\,c_{j}$ — числа пересечений, где $a_{j}=k-b_{j}-c_{j}$.

Массив пересечений

Изначально термины «массив пересечений» и «числа пересечений» были введены для описания дистанционно-транзитивных графов.

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

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

Если граф $\Gamma$ дистанционно-транзитивный, то мощности (кардинальные числа) множеств $|A|,\,|B|,\,|C|$ не зависят от вершин $u,v$, а зависят только от расстояния $j=d(u,v)$. Пусть $a_{j}=|A|,\,b_{j}=|B|,\,c_{j}=|C|$, где $a_{j},\,b_{j},\,c_{j}$ есть числа пересечений.

Определим массив пересечений дистанционно-транзитивного графа $\Gamma$ как:

$\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}}$

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

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

Следствием автоморфизма дистанционно-транзитивного графа является его регулярность. Соответственно, для регулярного графа можно определить числа пересечений. С другой стороны для дистанционно-регулярного графа существует комбинаторная регулярность, и для него также определены числа пересечений (см. § Массив пересечений), однако автоморфизм из этого не следует.

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

Свойства

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

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

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

• Каждая вершина имеет постоянное число вершин $k_{j}$, отстоящих от нее на расстояние $j$, причем $k_{0}=1$ и $k_{j+1}={\frac {b_{j}k_{j}}{c_{j+1}}}$ для всех $j=0,\,1,\,\dots ,\,D-1$;
• Порядок графа $n$ равен $n=k_{0}+k_{1}+\,\dots \,+k_{D}$;
• Число вершин, отстоящих от каждой вершины на расстоянии $j+1$, выражается через числа пересечений как $k_{j+1}={\frac {b_{0}b_{1}\dots b_{j}}{c_{1}c_{2}\dots c_{j+1}}}$ для всех $j=0,\,1,\,\dots ,\,D-1$;
• Произведение $k_{j}\cdot n$ числа вершин, отстоящих от произвольной вершины на расстоянии $j$, на порядок графа есть четная величина для всех $j=1,\,2,\,\dots ,\,D$;
• Произведение $k_{j}\cdot a_{j}$ числа вершин, отстоящих от произвольной вершины на расстоянии $j$, на число пересечений $a_{j}$ на есть четная величина для всех $j=1,\,2,\,\dots ,\,D$;
• Произведение $a_{1}\cdot n\cdot k$ числа пересечений $a_{1}$ на порядок графа и на его валентность делится на 6;
• Для чисел пересечений $c_{j}$ справедливо $1\leqslant c_{1}\leqslant c_{2}\leqslant \dots \leqslant c_{D}$;
• Для чисел пересечений $b_{j}$ справедливо $k=b_{0}\geqslant b_{1}\geqslant b_{2}\dots \geqslant b_{D-1}$;
• Если $i+j\leqslant D$, то $c_{i}\leqslant b_{j}$;
• Есть такое $i$, что $k_{0}\leqslant k_{1}\leqslant \dots \leqslant k_{i}$ и $k_{i+1}\geqslant k_{i+2}\geqslant \dots \geqslant k_{D}$.

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

Пусть граф $\Gamma (V,E)$ — транзитивно-регулярный диаметра $D$, $n=|V|$ есть число его вершин, а $k$ — валентность графа. Определим множество матриц расстояний (англ. distance matrices) размера $n\times n$ $\left\{\mathbf {A} _{0},\,\mathbf {A} _{1},\,\dots ,\,\mathbf {A} _{D}\right\}$ как :

$\left(\mathbf {A} _{h}\right)_{r,s}={\begin{cases}1&:\,d(v_{r},v_{s})=h,\\0&:\,d(v_{r},v_{s})\neq h\end{cases}}$

Свойства матриц расстояний

Матрицы расстояния обладают следующими свойствами:

• $\mathbf {A} _{0}=\mathbf {I} _{n}$, где $\mathbf {I} _{n}$ есть единичная матрица ;
• $\mathbf {A} _{1}=\mathbf {A}$ есть обычная матрица смежности графа $\Gamma (V,E)$;
• $\mathbf {A} _{0}+\mathbf {A} _{1}+\mathbf {A} _{2}+\dots +\mathbf {A} _{D}=\mathbf {J} _{n}$, где $\mathbf {J} _{n}$ есть матрица единиц
• $\mathbf {A} \mathbf {A} _{i}=b_{i-1}\mathbf {A} _{i-1}+a_{i}\mathbf {A} _{i}+c_{i+1}\mathbf {A} _{i+1}$, где ${\begin{Bmatrix}k,\,b_{1},\,\dots ,\,b_{d-1}\,;\,1,\,c_{2},\,\dots ,\,c_{d}\end{Bmatrix}}$ — массив пересечений дистанционно-регулярного графа и $a_{i}=k-b_{i}-c_{i}$
• существуют такие действительные числа $p_{i,j}^{h},\ (i,\,j,\,h=0,\,1,\,\dots ,\,D)$, что $\mathbf {A} _{i}\mathbf {A} _{j}=\sum _{h=0}^{D}{p_{i,j}^{h}\mathbf {A} _{h}}$ для всех $(i,\,j=0,\,1,\,\dots ,\,D)$, причем $p_{i,j}^{h}$ есть число пересечений, то есть количество вершин, находящихся на расстоянии $j$ от вершины $v$ и на расстоянии $i$ от вершины $w$ при условии расстояния $h$ между вершинами $v$ и $w$. Отметим, что $p_{1,i-1}^{i}=c_{i}$, $p_{1,i}^{i}=a_{i}$, $p_{1,i+1}^{i}=b_{i}$.

Литература

• Адельсон-Вельский Г. М., Вейсфелер Б. Ю., Леман А. А., Фараджев И. А. Об одном примере графа, не имеющего транзитивной группы автоморфизмов // Доклады Академии наук. — 1969. — Т. 185, № 5. — С. 975—976.
• Biggs N. L. Intersection Matrices for Linear Graphs (англ.) // Combinatorial mathematics and its applications : proceedings of a conference held at the Mathematical Institute, Oxford, from 7-10 July, 1969 / edited by D.J.A. Welsh. — London: Academic press, 1971. — P. 15-23.
• Biggs N. L. Algebraic Graph Theory (англ.). — 2nd edition. — 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.
• Cohen A. M. Distance-transitive graphs // Topics in Algebraic Graph Theory (англ.) / edited by L. W. Beineke, R. J. Wilson. — Cambridge University Press, 2004. — Vol. 102. — P. 222—249. — (Encyclopedia of Mathematics and its Applications).
• van Dam E. R., Koolen J. H., Tanaka H. Distance-regular graphs (англ.) // The Electronic Journal of Combinatorics : Dynamic surveys. — 2006. — No. DS22.
• Lauri J., Scapelatto R. Topics in Graph Automorphisms and Reconstruction (англ.). — 2nd edition. — Combridge: Combridge University Press, 2016. — 188 p.