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

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

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

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

Определение

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

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

[math]\displaystyle{ b_0 = k \quad b_1, \, \dots \, , \, b_{D-1}\ , \quad c_1=1, \quad c_2, \, \dots , \, c_D }[/math]

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

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

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

Тогда

[math]\displaystyle{ \iota(\Gamma) = \begin{Bmatrix} k, \, b_1, \, \dots , \, b_{D-1} \, ; \, 1, \, c_2, \, \dots, \, c_D \end{Bmatrix} }[/math]

есть массив пересечений графа [math]\displaystyle{ \Gamma }[/math] (см. § Массив пересечений), а [math]\displaystyle{ a_j, \, b_j, \, c_j }[/math] — числа пересечений, где [math]\displaystyle{ a_j = k -b_j - c_j }[/math].

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

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

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

[math]\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 \} }[/math]

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

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

[math]\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} }[/math]

Если [math]\displaystyle{ k }[/math] — валентность графа, то [math]\displaystyle{ b_0 = k }[/math] , [math]\displaystyle{ c_0=0 }[/math] а [math]\displaystyle{ c_1=1 }[/math]. Более того, [math]\displaystyle{ a_i + b_i +c_i = k }[/math], тогда компактная форма записи массива пересечений есть:

[math]\displaystyle{ \iota(\Gamma) = \begin{Bmatrix} k, \, b_1, \, \dots , \, b_{D-1} \, ; \, 1, \, c_2, \, \dots, \, c_D \end{Bmatrix} }[/math]

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

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

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

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

Свойства

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

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

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

• Каждая вершина имеет постоянное число вершин [math]\displaystyle{ k_j }[/math], отстоящих от нее на расстояние [math]\displaystyle{ j }[/math], причем [math]\displaystyle{ k_0=1 }[/math] и [math]\displaystyle{ k_{j+1}=\frac{b_j k_j}{c_{j+1}} }[/math] для всех [math]\displaystyle{ j=0, \, 1, \, \dots , \, D-1 }[/math];
• Порядок графа [math]\displaystyle{ n }[/math] равен [math]\displaystyle{ n = k_0 + k_1 + \, \dots \, + k_D }[/math];
• Число вершин, отстоящих от каждой вершины на расстоянии [math]\displaystyle{ j+1 }[/math], выражается через числа пересечений как [math]\displaystyle{ k_{j+1} = \frac{b_0 b_1 \dots b_j}{c_1 c_2 \dots c_{j+1}} }[/math] для всех [math]\displaystyle{ j=0, \, 1, \, \dots , \, D-1 }[/math];
• Произведение [math]\displaystyle{ k_j \cdot n }[/math] числа вершин, отстоящих от произвольной вершины на расстоянии [math]\displaystyle{ j }[/math], на порядок графа есть четная величина для всех [math]\displaystyle{ j=1, \, 2, \, \dots , \, D }[/math];
• Произведение [math]\displaystyle{ k_j \cdot a_j }[/math] числа вершин, отстоящих от произвольной вершины на расстоянии [math]\displaystyle{ j }[/math], на число пересечений [math]\displaystyle{ a_j }[/math] на есть четная величина для всех [math]\displaystyle{ j=1, \, 2, \, \dots , \, D }[/math];
• Произведение [math]\displaystyle{ a_1 \cdot n \cdot k }[/math] числа пересечений [math]\displaystyle{ a_1 }[/math] на порядок графа и на его валентность делится на 6;
• Для чисел пересечений [math]\displaystyle{ c_j }[/math] справедливо [math]\displaystyle{ 1 \leqslant c_1 \leqslant c_2 \leqslant \dots \leqslant c_D }[/math];
• Для чисел пересечений [math]\displaystyle{ b_j }[/math] справедливо [math]\displaystyle{ k=b_0 \geqslant b_1 \geqslant b_2 \dots \geqslant b_{D-1} }[/math];
• Если [math]\displaystyle{ i+j \leqslant D }[/math], то [math]\displaystyle{ c_i \leqslant b_j }[/math];
• Есть такое [math]\displaystyle{ i }[/math], что [math]\displaystyle{ k_0 \leqslant k_1 \leqslant \dots \leqslant k_i }[/math] и [math]\displaystyle{ k_{i+1} \geqslant k_{i+2} \geqslant \dots \geqslant k_D }[/math].

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

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

[math]\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} }[/math]

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

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

• [math]\displaystyle{ \mathbf A_0 = \mathbf I_n }[/math], где [math]\displaystyle{ \mathbf I_n }[/math] есть единичная матрица ;
• [math]\displaystyle{ \mathbf A_1 = \mathbf A }[/math] есть обычная матрица смежности графа [math]\displaystyle{ \Gamma(V,E) }[/math];
• [math]\displaystyle{ \mathbf A_0 + \mathbf A_1 +\mathbf A_2 + \dots + \mathbf A_D = \mathbf J_n }[/math], где [math]\displaystyle{ \mathbf J_n }[/math] есть матрица единиц
• [math]\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} }[/math], где [math]\displaystyle{ \begin{Bmatrix} k, \, b_1, \, \dots , \, b_{d-1} \, ; \, 1, \, c_2, \, \dots, \, c_d \end{Bmatrix} }[/math] — массив пересечений дистанционно-регулярного графа и [math]\displaystyle{ a_i =k-b_i -c_i }[/math]
• существуют такие действительные числа [math]\displaystyle{ p_{i,j}^h,\ ( i, \, j, \, h = 0, \, 1, \, \dots, \, D) }[/math], что [math]\displaystyle{ \mathbf A_i \mathbf A_j = \sum^{D}_{h=0} {p_{i,j}^h \mathbf A_h} }[/math] для всех [math]\displaystyle{ ( i, \, j = 0, \, 1, \, \dots, \, D) }[/math], причем [math]\displaystyle{ p_{i,j}^h }[/math] есть число пересечений, то есть количество вершин, находящихся на расстоянии [math]\displaystyle{ j }[/math] от вершины [math]\displaystyle{ v }[/math] и на расстоянии [math]\displaystyle{ i }[/math] от вершины [math]\displaystyle{ w }[/math] при условии расстояния [math]\displaystyle{ h }[/math] между вершинами [math]\displaystyle{ v }[/math] и [math]\displaystyle{ w }[/math]. Отметим, что [math]\displaystyle{ p_{1,i-1}^i = c_i }[/math], [math]\displaystyle{ p_{1,i}^i = a_i }[/math], [math]\displaystyle{ p_{1,i+1}^i = b_i }[/math].

Литература

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