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

Дистанционно-регулярный граф (англ. 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 году на конференции в Оксфорде^[1], хотя сам термин появился гораздо позже^[2].

Определение

Определение дистанционно-регулярного графа^[3][4]:

Дистанционно-регулярный граф — это неориентрированный, связанный, ограниченный, регулярный граф ${\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}}$^[3][4].

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

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

Пусть ${\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}}}$

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

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

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

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

Свойства

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

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

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

• Каждая вершина имеет постоянное число вершин ${\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\}}$ как^[3] :

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

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

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

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