Дистанційно-транзитивний граф

Повний граф ${\displaystyle K_{7}}$

Граф Петерсена

Граф Хівуда

Граф Паппа

Граф Коксетера

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

Нехай неорієнтований, зв'язний, обмежений граф ${\displaystyle \Gamma =(V,E)}$ має групу автоморфізмів ${\displaystyle Aut(\Gamma )}$. Кількість ребер у найкоротшому шляху, що з'єднує ${\displaystyle u,v\in V(\Gamma )}$ називають відстанню між ${\displaystyle u}$ і ${\displaystyle v}$ і позначають як ${\displaystyle d(u,v)}$. Нехай ${\displaystyle G}$ — підгрупа ${\displaystyle Aut(\Gamma )}$. Граф ${\displaystyle \Gamma }$ називають ${\displaystyle G}$-дистанційно-транзитивним (англ. ${\displaystyle G}$-distance-transitive якщо для кожної четвірки вершин ${\displaystyle u,v,x,y}$, таких що ${\displaystyle d(u,v)=d(x,y)}$, існує автоморфізм ${\displaystyle g\in G}$, який відображає ${\displaystyle u\rightarrow x}$ і ${\displaystyle v\rightarrow y}$.[2]

Іншими словами[2] ${\displaystyle \Gamma }$ є ${\displaystyle G}$-дистанційно-транзитивним графом, якщо підгрупа ${\displaystyle G}$ діє транзитивно на множину ${\displaystyle \left\{(x,y)\,|\,x,e\in V(\Gamma ),\,d(x,y)=i\right\}}$.

Нехай ${\displaystyle \Gamma =(V,E)}$ — неорієнтований, зв'язний, обмежений граф, а дві його вершини ${\displaystyle u,v\in V(\Gamma )}$ розташовані на відстані ${\displaystyle j=d(u,v)}$ одна від одної. Всі вершини ${\displaystyle w}$, інцідентні вершині ${\displaystyle u}$ можна розбити на три множини ${\displaystyle A}$, ${\displaystyle B}$ і ${\displaystyle C}$, залежно від їх відстані ${\displaystyle d(v,w)}$ до вершини ${\displaystyle v}$:

${\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 \Gamma }$ дистанційно-транзитивний, то кардинальні числа множин ${\displaystyle |A|,\,|B|,\,|C|}$ не залежать від вершин ${\displaystyle u}$ і ${\displaystyle v}$, а залежать тільки від відстані ${\displaystyle j=d(u,v)}$. Нехай ${\displaystyle a_{j}=|A|,\,b_{j}=|B|,\,c_{j}=|C|}$, де ${\displaystyle a_{j},\,b_{j},\,c_{j}}$ — числа перетинів.

Визначимо масив перетинів дистанційно-транзитивного графу ${\displaystyle \Gamma }$ як[3][4]:

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

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

Дистанційно-транзитивний граф є вершинно-транзитивним і симетричним.

Дистанційно-транзитивні графи мають велике число груп автоморфізмів.

Гігман[6][7] розвинув теорію груп рангу 3. Ці групи є групами автоморфізмів сильно регулярних графів, причому вони діють транзитивно як на множині вершин і ребер, так і на множині пар різних несуміжних вершин. Такі графи є дистанційно транзитивними графами діаметру 2.

Найпростіші приклади дистанційно-транзитивних графів:

• повні графи ${\displaystyle K_{n}}$
• повні двочасткові графи (бікліки) з рівними частками ${\displaystyle K_{n,n}}$
• графи гіперкуба ${\displaystyle Q_{n}}$

Складніші приклади дистанційно-транзитивних графів:

• граф Джонсона
• граф Грассмана
• граф Геммінга
• граф Лівінгстона

1971 року Бігс і Сміт у роботі[1] довели теорему, що серед тривалентних графів існує всього лише 12 дистанційно-транзитивних графів:

Назва графу	Число вершин	Діаметр	Обхват	Масив перетинів
Повний граф K 4	4	1	3	{3; 1}
Повний двочастковий граф K 3,3	6	2	4	{3,2; 1,3}
Граф Петерсена	10	2	5	{3,2; 1,1}
Граф гіперкуба ${\displaystyle Q_{3}}$	8	3	4	{3,2,1; 1,2,3}
Граф Хівуда	14	3	6	{3,2,2; 1,1,3}
Граф Паппа	18	4	6	{3,2,2,1; 1,1,2,3}
Граф Коксетера	28	4	7	{3,2,2,1; 1,1,1,2}
Граф Татта — Коксетера	30	4	8	{3,2,2,2; 1,1,1,3}
Граф додекаедра	20	5	5	{3,2,1,1,1; 1,1,1,2,3}
Граф Дезарга	20	5	6	{3,2,2,1,1; 1,1,2,2,3}
Граф Бігса — Сміта	102	7	9	{3,2,2,2,1,1,1; 1,1,1,1,1,1,3}
Граф Фостера	90	8	10	{3,2,2,2,2,1,1,1; 1,1,1,1,2,2,2,3}

Повний список дистанційно-транзитивних графів відомий для деяких степенів, більших від трьох, але класифікація дистанційно-транзитивних графів з довільно великим степенем залишається відкритою.

Найпростіше асимптотичне сімейство дистанційно-транзитивних графів — це графи гіперкубів. Інші сімейства — це складені кубічні графи і квадратні турові графи. Всі три сімейства мають довільно великий степінь.

• Адельсон-Вельский Г.М., Вейсфелер Б.Ю., Леман А.А., Фараджев И.А. Об одном примере графа, не имеющнго транзитивной группы автоморфизмов // Доклады Академии наук. — 1969. — Т. 185, № 5 (3 листопада). — С. 975—976.
• Biggs N.L., Smith D.H. On trivalent graphs // Bulletin of the London Mathematical Society. — 1971. — Vol. 3, iss. 2 (3 November). — P. 155—158. — DOI:10.1112/blms/3.2.155.
• Biggs N.L. Algebraic Graph Theory. — 2nd. — Cambridge University Press, 1993. — 205 с.
• Higman D.G. Finite permutation groups of rank 3 // Math. Zeitschr.. — 1964. — 3 листопада. — С. 142—156.
• Higman D.G. Primitive rank 3 groups with a prime subdegree // Math. Zeitschr.. — 1966. — Т. 91 (3 листопада). — С. 70-89.
• Ivanov A. A. Distance-Transitive Graphs and Their Classification / (eds.) // Investigations in Algebraic Theory of Combinatorial Objects. Mathematics and Its Applications (Soviet Series). — Dordrecht : Springer, 1994. — Vol. 84 (3 November). — P. 283-378.
• Lauri J., Scapelatto R. Topics in Graph Automorphisms and Reconstruction. — 2nd. — Combridge : Combridge University Press, 2016. — 188 с.

• Weisstein, Eric W. Дистанційно-транзитивний граф(англ.) на сайті Wolfram MathWorld.