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

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

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

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

Визначення

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

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

Граф Хівуда

Граф Паппа

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

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

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

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

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

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

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

Якщо граф $\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}$ — числа перетинів.

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

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

Властивості

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

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

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

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

Приклади

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

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

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

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

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

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

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

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

Література

• Адельсон-Вельский Г.М., Вейсфелер Б.Ю., Леман А.А., Фараджев И.А. Об одном примере графа, не имеющнго транзитивной группы автоморфизмов // Доклады Академии наук. — 1969. — Т. 185, № 5 (21 квітня). — С. 975—976.
• Biggs N.L., Smith D.H. On trivalent graphs // Bulletin of the London Mathematical Society. — 1971. — Vol. 3, iss. 2 (21 April). — 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. — 21 квітня. — С. 142—156.
• Higman D.G. Primitive rank 3 groups with a prime subdegree // Math. Zeitschr.. — 1966. — Т. 91 (21 квітня). — С. 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 (21 April). — P. 283-378. Архівовано з джерела 9 липня 2021. Процитовано 4 липня 2021.
• Lauri J., Scapelatto R. Topics in Graph Automorphisms and Reconstruction. — 2nd. — Combridge : Combridge University Press, 2016. — 188 с.

Ранні роботи

• Biggs N. Combinatorial Mathematics and its Applications (Proc. Conf., Oxford, 1969). — London : Academic Press, 1971. — С. 15—23.
• Biggs N. Finite Groups of Automorphisms. — London & New York : Cambridge University Press, 1971. — Т. 6. — (London Mathematical Society Lecture Note Series)

• Smith D.H. Primitive and imprimitive graphs // The Quarterly Journal of Mathematics. Oxford. Second Series. — 1971. — Vol. 22, iss. 4 (21 April). — P. 551—557. — DOI:10.1093/qmath/22.4.551.

Огляди

• Biggs N.L. Distance-Transitive Graphs // Algebraic Graph Theory. — 2nd. — Cambridge University Press, 1993. — С. 155–163.
• Van Bon J. Finite primitive distance-transitive graphs // European Journal of Combinatorics. — 2007. — Vol. 28, iss. 2 (21 April). — P. 517—532. — DOI:10.1016/j.ejc.2005.04.014..
• Brouwer A.E, Cohen A.M., Neumaier A. Distance-Transitive Graphs // Distance-Regular Graphs. — New York : Springer-Verlag, 1989. — С. 214—234.
• Cohen A.M. Topics in Algebraic Graph Theory / L. W. Beineke, R. J. Wilson. — Cambridge University Press, 2004. — Т. 102. — С. 222—249. — (Encyclopedia of Mathematics and its Applications)
• Godsil C., Royle G. Distance-Transitive Graphs // Algebraic Graph Theory. — New York : Springer-Verlag, 2001. — С. 66—69.

Посилання

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