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

Дистанційно-транзитивний граф (англ. distance-transitive graph) — це такий граф, що для будь-якої пари його вершин ${\displaystyle v}$ і ${\displaystyle w}$, відстань між якими ${\displaystyle i}$, і будь-якої іншої пари вершин ${\displaystyle x}$ і ${\displaystyle y}$, відстань між якими також ${\displaystyle i}$, знайдеться автоморфізм, що переводить ${\displaystyle v}$ в ${\displaystyle x}$, а ${\displaystyle w}$ в ${\displaystyle y}$.

Граф Бігса — Сміта, найбільший 3-регулярний дистанційно-транзитивний граф.

Термін дистанційно-транзитивний граф увели Бігс і Сміт 1971 року^[1].

Визначення

Повний граф ${\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] (Адельсон-Вельський Г. М., Вейсфейлер Б. Ю.^[ru], Леман А. А., Фараджев І. А.). Найменший дистанційно-регулярний граф, який не є дистанційно-транзитивним — це граф Шрікханде. Єдиний тривалентний граф цього типу — це 12-клітка Татта, граф зі 126 вершинами.

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

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

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

Приклади

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

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

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

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

Класифікація кубічних дистанційно-транзитивних графів

1971 року Бігс^[en] і Сміт у роботі^[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}

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

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