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

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

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

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

Определение

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

$b_0=k{b}_1,\dots ,b_{D-1},c_1=1,c_2,\dots ,c_D$

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

(1) число вершин, инцидентных $u$ и находящихся на расстоянии $j-1$ от $v$, есть $c_j$ ($1⩽j⩽D$)

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

Тогда

$\iota (\mathrm{\Gamma })=\left\{\begin{array}{c}k,b_1,\dots ,b_{D-1};1,c_2,\dots ,c_D\end{array}\right\}$

есть массив пересечений графа $\mathrm{\Gamma }$ (см. Шаблон:Ссылка на раздел), а $a_j,b_j,c_j$ — числа пересечений, где $a_j=k-b_j-c_j$Шаблон:SfnШаблон:Sfn.

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

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

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

$\{w\in A:d(v,w)=j\},\{w\in B:d(v,w)=j+1\},\{w\in C:d(v,w)=j-1\}$

Если граф $\mathrm{\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$ есть числа пересечений.

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

$\iota (\mathrm{\Gamma })=\left\{\begin{array}{cccccc}\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{array}\right\}$

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

$\iota (\mathrm{\Gamma })=\left\{\begin{array}{c}k,b_1,\dots ,b_{D-1};1,c_2,\dots ,c_D\end{array}\right\}$

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

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

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

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

Свойства

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

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

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

• Каждая вершина имеет постоянное число вершин $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⩽c_1⩽c_2⩽\dots ⩽c_D$;
• Для чисел пересечений $b_j$ справедливо $k=b_0⩾b_1⩾b_2\dots ⩾b_{D-1}$;
• Если $i+j⩽D$, то $c_i⩽b_j$;
• Есть такое $i$, что $k_0⩽k_1⩽\dots ⩽k_i$ и $k_{i+1}⩾k_{i+2}⩾\dots ⩾k_D$.

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

Пусть граф $\mathrm{\Gamma }(V,E)$ — транзитивно-регулярный диаметра $D$, $n=|V|$ есть число его вершин, а $k$ — валентность графа. Определим множество матриц расстояний (Шаблон:Lang-en) размера $n\times n$ $\{{𝐀}_0,{𝐀}_1,\dots ,{𝐀}_D\}$ какШаблон:Sfn :

${\left({𝐀}_h\right)}_{r,s}=\{\begin{array}{cc}1& :d(v_r,v_s)=h,\\ 0& :d(v_r,v_s)\ne h\end{array}$

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

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

• ${𝐀}_0={𝐈}_n$, где ${𝐈}_n$ есть единичная матрица ;
• ${𝐀}_1=𝐀$ есть обычная матрица смежности графа $\mathrm{\Gamma }(V,E)$;
• ${𝐀}_0+{𝐀}_1+{𝐀}_2+\dots +{𝐀}_D={𝐉}_n$, где ${𝐉}_n$ есть матрица единиц
• $𝐀{𝐀}_i=b_{i-1}{𝐀}_{i-1}+a_i{𝐀}_i+c_{i+1}{𝐀}_{i+1}$, где $\left\{\begin{array}{c}k,b_1,\dots ,b_{d-1};1,c_2,\dots ,c_d\end{array}\right\}$ — массив пересечений дистанционно-регулярного графа и $a_i=k-b_i-c_i$
• существуют такие действительные числа $p_{i,j}^h,(i,j,h=0,1,\dots ,D)$, что ${𝐀}_i{𝐀}_j=\sum _{h=0}^D{p}_{i,j}^h{𝐀}_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$.

Литература

• Шаблон:Статья
• Шаблон:Статья
• Шаблон:Книга
• Шаблон:Книга
• Шаблон:Книга
• Шаблон:Статья
• Шаблон:Книга