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

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

Дистанційно-транзитивний граф (Шаблон:Lang-en) — це такий граф, що для будь-якої пари його вершин $v$ і $w$, відстань між якими $i$, і будь-якої іншої пари вершин $x$ і $y$, відстань між якими також $i$, знайдеться автоморфізм, що переводить $v$ в $x$, а $w$ в $y$.

Термін дистанційно-транзитивний граф увели Бігс і Сміт 1971 рокуШаблон:Sfn.

Визначення

Повний граф $K_7$

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

Граф Хівуда

Граф Паппа

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

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

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

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

Масив перетинів

Нехай $\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 }$ якШаблон:SfnШаблон:Sfn:

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

Властивості

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

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

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

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

Приклади

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

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

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

• граф Джонсона
• Шаблон:Нп
• граф Геммінга
• Шаблон:Нп

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

1971 року Шаблон:Нп і Сміт у роботіШаблон:Sfn довели теорему, що серед тривалентних графів існує всього лише 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}
Граф гіперкуба $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}

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

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

Література

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

Ранні роботи

• Шаблон:Книга
• Шаблон:Книга

• Шаблон:Стаття

Огляди

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

Посилання

• Шаблон:Mathworld