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

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

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

Визначення

Визначення дистанційно-регулярного графа:

Дистанційно-регулярний граф — це неорієнтований, зв'язний, обмежений, регулярний граф $\Gamma =(V,E)$ діаметром $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$).

Масив $\left\{k,\,b_{1},\,\dots ,\,b_{D-1}\,;1,\,c_{2},\,\dots ,\,c_{D}\right\}$ є масив перетинів дистанційно-регулярного графа, де $k$ — валентність графа.

Дистанційно-регулярний граф з діаметром 2 є сильно регулярним і обернене твердження теж істинне (за умови, що граф є зв'язним).

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

На перший погляд дистанційно-транзитивний граф і дистанційно-регулярний граф є дуже близькими поняттями. Дійсно, кожен дистанційно-транзитивний граф є дистанційно-регулярним. Однак їх природа різна. Якщо дистанційно-транзитивний граф визначається виходячи з симетрії графа через умову автоморфізму, то дистанційно-регулярний граф визначається з умови його комбінаторної регулярності.

Автоморфізм дистанційно-транзитивного графа викликає його регулярність, і відповідно, наявність чисел перетинів $a_{j},\,b_{j},\,c_{j}$. Однак, якщо існує комбінаторна регулярність, і визначені числа перетинів для графа, і він дистанційно-регулярний, то автоморфізм з цього не випливає.

Якщо з дистанційно-транзитивності графа випливає його дистанційно-регулярність, то зворотне не істинне.

Це доведено 1969 року, ще до введення в ужиток терміна дистанційно-транзитивний граф, групою радянських математиків (Адельсон-Вельський Г. М., Вейсфейлер Б. Ю., Леман А. А., Фараджев І. А.). Найменший дистанційно-регулярний граф, який не є дистанційно-транзитивним — це граф Шрікханде. Єдиний тривалентний граф цього типу — це 12-клітка Татта, граф зі 126 вершинами.

Масив перетинів дистанційно-регулярного графа

нехай $\Gamma =(V,E)$ — транзитивно-регулярний граф діаметра $D$ і порядку $n$, а $u$ і $v$ — пара вершин, віддалених одна від одної на відстань $d=(u,v)$. Тоді множину вершин, інцидентних до $u$ можна розбити на три множини $A$, $B$ і $C$, залежно від їх відстані $d(v,w)$ до вершини $v$, де вершина $w$ інцидентна до $u$:

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

кардинальні числа $|A|,\,|B|,\,|C|$ цих множин $a_{j}=|A|,\,b_{j}=|B|,\,c_{j}=|C|$ є числами перетинів, а масив перетинів є

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

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

Згідно з оглядом:

• Кожна вершина має стале число вершин $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|$ — кардинальне число його множини вершин $V$, а $k$ — валентність графа. Визначимо множину матриць відстаней (англ. distance matrices) розміру $n\times n$$\left\{\mathbf {A} _{0},\,\mathbf {A} _{1},\,\dots ,\,\mathbf {A} _{D}\right\}$ як:

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

Властивості матриць відстаней

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

Алгебра суміжності

Нехай на транзитивно-регулярному графі $\Gamma$ діаметру $D$ задано алгебру суміжності $\mathbb {A} (\Gamma )$, тобто матричну підалгебру $M_{n\times n}(\mathbb {R} )$ поліномів матриці суміжності $\mathbf {A}$. Її розмірністю буде $dim(\mathbb {A} )=D+1$, а базисом — множина матриць відстаней $\left\{\mathbf {A} _{0},\,\mathbf {A} _{1},\,\dots ,\,\mathbf {A} _{D}\right\}$.

Приклади

• Повні графи
• Циклічні графи
• Графи Мура, зокрема граф Петерсена і граф Гофмана — Синглтона
• Графи Геммінга
• Сильно регулярні графи
• Непарні графи

Література

• Адельсон-Вельский Г.М., Вейсфелер Б.Ю., Леман А.А., Фараджев И.А. Об одном примере графа, не имеющнго транзитивной группы автоморфизмов // Доклады Академии наук. — 1969. — Т. 185, № 5 (21 квітня). — С. 975—976.
• Biggs N.L. Algebraic Graph Theory. — 2nd. — Cambridge University Press, 1993. — 205 с.
• 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.
• van Dam E.R., Koolen J.H., Tanaka H. Distance-regular graphs // The Electronic Journal of Combinatorics : dynamic surveys. — 2006. — No. DS22 (21 April). Архівовано з джерела 10 січня 2021. Процитовано 4 липня 2021.
• Godsil C. D. Algebraic combinatorics. — N. Y. : Chapman and Hall, 1993. — С. xvi+362. — (Chapman and Hall Mathematics Series) — ISBN 0-412-04131-6.
• Lauri J., Scapelatto R. Topics in Graph Automorphisms and Reconstruction. — 2nd. — Combridge : Combridge University Press, 2016. — 188 с.