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

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

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

Визначення

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

Дистанційно-регулярний граф — це неорієнтований, зв'язний, обмежений, регулярний граф ${\displaystyle \Gamma =(V,E)}$ діаметром ${\displaystyle D}$, для якого справедливо, що існують числа

${\displaystyle b_{0}=k\quad b_{1},\,\dots \,,\,b_{D-1}\,\quad c_{1}=1,\quad c_{2},\,\dots ,\,c_{D}}$

такі, що для кожної пари вершин ${\displaystyle (u,v)}$, відстань між якими ${\displaystyle d(u,v)=j}$ справедливо:

(1) число вершин, інцидентних ${\displaystyle u}$, розташованих на відстані ${\displaystyle j-1}$ від ${\displaystyle v}$ є ${\displaystyle c_{j}}$ (${\displaystyle 1\leqslant j\leqslant D}$): (2) число вершин, інцидентних ${\displaystyle u}$, розташованих на відстані ${\displaystyle j+1}$ від ${\displaystyle v}$ є ${\displaystyle b_{j}}$ (${\displaystyle 0\leqslant j\leqslant D-1}$).

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

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

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

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

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

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

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

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

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

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

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

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

якщо ${\displaystyle k}$ — валентність графа, то ${\displaystyle b_{0}=k}$, ${\displaystyle c_{0}=0}$ а ${\displaystyle c_{1}=1}$. Більш того, ${\displaystyle a_{i}+b_{i}+c_{i}=k}$ . Тому масив перетинів записується як:

${\displaystyle \iota (\Gamma )={\begin{Bmatrix}k,\,b_{1},\,\dots ,\,b_{D-1}\,;\,1,\,c_{2},\,\dots ,\,c_{D}\end{Bmatrix}}}$

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

Згідно з оглядом^[4][4]:

• Кожна вершина має стале число вершин ${\displaystyle k_{j}}$, віддалених від неї на відстань ${\displaystyle j}$, причому ${\displaystyle k_{0}=1}$ і ${\displaystyle k_{j+1}={\frac {b_{j}k_{j}}{c_{j+1}}}}$ для всіх ${\displaystyle j=0,\,1,\,\dots ,\,D-1}$;
• порядок графа ${\displaystyle n}$ дорівнює ${\displaystyle n=k_{0}+k_{1}+\,\dots \,+k_{D}}$;
• число вершин, віддалених від кожної вершини на відстан ${\displaystyle j+1}$ виражається через числа перетинів як ${\displaystyle k_{j+1}={\frac {b_{0}b_{1}\dots b_{j}}{c_{1}c_{2}\dots c_{j+1}}}}$ для всіх ${\displaystyle j=0,\,1,\,\dots ,\,D-1}$;
• добуток ${\displaystyle k_{j}\cdot n}$ числа вершин, віддалених від довільної вершини на відстань ${\displaystyle j}$, на порядок графа є парним числом для всіх ${\displaystyle j=1,\,2,\,\dots ,\,D}$;
• добуток ${\displaystyle k_{j}\cdot a_{j}}$ числа вершин, віддалених від довільної вершини на відстані ${\displaystyle j}$, на кількість перетинів ${\displaystyle a_{j}}$ є парним числом для всіх ${\displaystyle j=1,\,2,\,\dots ,\,D}$;
• добуток ${\displaystyle a_{1}\cdot n\cdot k}$ числа перетинів ${\displaystyle a_{1}}$ на порядок графа і на його валентність ділитися на 6;
• для чисел перетинів ${\displaystyle c_{j}}$ виконується ${\displaystyle 1\leqslant c_{1}\leqslant c_{2}\leqslant \dots \leqslant c_{D}}$;
• для чисел перетинів ${\displaystyle b_{j}}$ виконується ${\displaystyle k=b_{0}\geqslant b_{1}\geqslant b_{2}\dots \geqslant b_{D-1}}$;
• якщо ${\displaystyle i+j\leqslant D}$, то ${\displaystyle c_{i}\leqslant b_{j}}$;
• є таке ${\displaystyle i}$, що ${\displaystyle k_{0}\leqslant k_{1}\leqslant \dots \leqslant k_{i}}$ і ${\displaystyle k_{i+1}\geqslant k_{i+2}\geqslant \dots \geqslant k_{D}}$.

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

Нехай граф ${\displaystyle \Gamma (V,E)}$ — транзитивно-регулярний діаметра ${\displaystyle D}$, ${\displaystyle n=|V|}$ — кардинальне число його множини вершин ${\displaystyle V}$, а ${\displaystyle k}$ — валентність графа. Визначимо^[1] множину матриць відстаней (англ. distance matrices) розміру ${\displaystyle n\times n}$${\displaystyle \left\{\mathbf {A} _{0},\,\mathbf {A} _{1},\,\dots ,\,\mathbf {A} _{D}\right\}}$ як:

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

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

• ${\displaystyle \mathbf {A} _{0}=\mathbf {I} _{n}}$ де ${\displaystyle \mathbf {I} _{n}}$ — одинична матриця;
• ${\displaystyle \mathbf {A} _{1}=\mathbf {A} }$ є звичайною матрицею суміжності графа ${\displaystyle \Gamma (V,E)}$;
• ${\displaystyle \mathbf {A} _{0}+\mathbf {A} _{1}+\mathbf {A} _{2}+\dots +\mathbf {A} _{D}=\mathbf {J} _{n}}$, де ${\displaystyle \mathbf {J} _{n}}$ є матрицею одиниць
• ${\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}}$, де ${\displaystyle {\begin{Bmatrix}k,\,b_{1},\,\dots ,\,b_{d-1}\,;\,1,\,c_{2},\,\dots ,\,c_{d}\end{Bmatrix}}}$ — масив перетинів дистанційно-регулярного графа і ${\displaystyle a_{i}=k-b_{i}-c_{i}}$
• Існують дійсні числа ${\displaystyle p_{i,j}^{h},\ (i,\,j,\,h=0,\,1,\,\dots ,\,D)}$, такі що ${\displaystyle \mathbf {A} _{i}\mathbf {A} _{j}=\sum _{h=0}^{D}{p_{i,j}^{h}\mathbf {A} _{h}}}$ для всіх ${\displaystyle (i,\,j=0,\,1,\,\dots ,\,D)}$, причому ${\displaystyle p_{i,j}^{h}}$ — кількість перетинів, тобто кількість вершин, розташованих на відстані ${\displaystyle j}$ від вершини ${\displaystyle v}$ і на відстані ${\displaystyle i}$ від вершини ${\displaystyle w}$ за умови відстані ${\displaystyle h}$ між вершинами ${\displaystyle v}$ і ${\displaystyle w}$. Відмітимо, що ${\displaystyle p_{1,i-1}^{i}=c_{i}}$, ${\displaystyle p_{1,i}^{i}=a_{i}}$, ${\displaystyle p_{1,i+1}^{i}=b_{i}}$

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

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

Приклади

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

Примітки

1. Biggs, 1993.
2. Lauri, 2016.
3. Адельсон-Вельский, 1969.
4. van Dam, 2006.

Література

• Адельсон-Вельский Г.М., Вейсфелер Б.Ю., Леман А.А., Фараджев И.А. Об одном примере графа, не имеющего транзитивной группы автоморфизмов // Доклады Академии наук. — 1969. — Т. 185, № 5 (25 березня). — С. 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 (25 March). Архівовано з джерела 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 с.