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

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

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

Термін дистанційно-транзитивний граф увели Бігс і Сміт 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] і квадратні турові графи. Всі три сімейства мають довільно великий степінь.

Примітки

1. Biggs, 1971.
2. Ivanov, 1994.
3. Lauri, 2016.
4. Biggs, 1993.
5. Адельсон-Вельский, 1969.
6. Higman, 1964.
7. Higman, 1966.

Література

• Адельсон-Вельский Г.М., Вейсфелер Б.Ю., Леман А.А., Фараджев И.А. Об одном примере графа, не имеющего транзитивной группы автоморфизмов // Доклады Академии наук. — 1969. — Т. 185, № 5 (15 січня). — С. 975—976.
• Biggs N.L., Smith D.H. On trivalent graphs // Bulletin of the London Mathematical Society. — 1971. — Vol. 3, iss. 2 (15 January). — 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. — 15 січня. — С. 142—156.
• Higman D.G. Primitive rank 3 groups with a prime subdegree // Math. Zeitschr.. — 1966. — Т. 91 (15 січня). — С. 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 (15 January). — 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 (15 January). — 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 (15 January). — 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.