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

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

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

Определение

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

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

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

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

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

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

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

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

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

Свойства

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

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

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

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

\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]:

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

Примечания

↑ Biggs, 1971.
↑ Brouwer, Cohen and Neumaier, 1989, p. 128.
↑ ¹ ² ³ ⁴ ⁵ ⁶ Biggs, 1993, p. 159.
↑ ¹ ² Brouwer, Cohen and Neumaier, 1989, p. 126.
↑ Biggs, 1971, p. 18.
↑ Lauri and Scapelatto, 2016, p. 33.
↑ Biggs, 1993, p. 157.
↑ ¹ ² ³ ⁴ Brouwer, Cohen and Neumaier, 1989, p. 136.
↑ Cohen, 2004, p. 232.
↑ Адельсон-Вельский, Вейсфелер, Леман и Фараджев, 1969.
↑ van Dam, Koolen and Tanaka, 2006, p. 8.
↑ van Dam, Koolen and Tanaka, 2006, p. 11.

Литература

Адельсон-Вельский Г. М., Вейсфелер Б. Ю., Леман А. А., Фараджев И. А. Об одном примере графа, не имеющего транзитивной группы автоморфизмов // Доклады Академии наук. — 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.

[_1f5ff51384a2a411-1] Biggs, 1971.

[_122330a94db8a6ef-2] Brouwer, Cohen and Neumaier, 1989, p. 128.

[_21b58c7c7edb5078-3] ¹ ² ³ ⁴ ⁵ ⁶ Biggs, 1993, p. 159.

[_122330a94db8a6e1-4] ¹ ² Brouwer, Cohen and Neumaier, 1989, p. 126.

[_c0674d01bda93cee-5] Biggs, 1971, p. 18.

[_0619c880e60f4978-6] Lauri and Scapelatto, 2016, p. 33.

[_21b58c7c7edb5076-7] Biggs, 1993, p. 157.

[_12232fa94db8a512-8] ¹ ² ³ ⁴ Brouwer, Cohen and Neumaier, 1989, p. 136.

[_8b6f039ff850ace9-9] Cohen, 2004, p. 232.

[_0cdd44bb08854b7d-10] Адельсон-Вельский, Вейсфелер, Леман и Фараджев, 1969.

[_a619fcbee8556801-11] van Dam, Koolen and Tanaka, 2006, p. 8.

[_93908064c91fc5a9-12] van Dam, Koolen and Tanaka, 2006, p. 11.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]