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

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

Определение

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

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

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

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

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

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

Тогда

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

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

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

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

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

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

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

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

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

Если ${\displaystyle k}$ — валентность графа, то ${\displaystyle b_{0}=k}$ , ${\displaystyle c_{0}=0}$ а ${\displaystyle c_{1}=1}$ . Более того, ${\displaystyle a_{i}+b_{i}+c_{i}=k}$ , тогда компактная форма записи массива пересечений есть:

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

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

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

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

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

Свойства

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

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

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

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

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

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

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

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

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

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