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

Дистанционно-регулярный граф (англ. 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.

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.

[_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.