Дистанционно-транзитивный граф ( англ. distance-transitive graph ) — граф , в котором любая упорядоченная пара вершин переводится в любую другую упорядоченную пару вершин с тем же расстоянием между вершинами одним из автоморфизмов графа.

Близким понятием является дистанционно-регулярный граф , однако природа их разная. Если дистанционно-транзитивный граф определяется исходя из симметрии графа через условие автоморфизма, то дистанционно-регулярный граф определяется из условия его комбинаторной регулярности. Каждый дистанционно-транзитивный граф является дистанционно-регулярным, однако обратное не справедливо. Это было доказано в 1969 году, еще до введения в обиход термина «дистанционно-транзитивный граф».

Полностью классифицированы дистанционно-регулярные графы степеней меньших 13.

Определения дистанционно-транзитивного графа

Существует несколько различных по форме, но одинаковых по смыслу определений дистанционно-транзитивного графа. Предполагается, что граф ${\displaystyle \Gamma =(V,E)}$ — неориентированный, связанный и ограниченный. В определении используются понятия расстояние между вершинами графа и автоморфизм графа :

• Расстояние ${\displaystyle d(u,v)}$ между двумя вершинами ${\displaystyle u,v\in V(\Gamma )}$ графа ${\displaystyle \Gamma =(V,E)}$ есть количество рёбер по наикратчайшему пути, соединяющему ${\displaystyle u}$ и ${\displaystyle v}$
• Автоморфизм графа ${\displaystyle g:V\rightarrow V}$ — взаимно однозначное отображение множества вершин графа на себя, сохраняющее смежность вершин.
• Группа автоморфизмов графа ${\displaystyle \mathrm {Aut} (\Gamma )}$ — множество автоморфизмов графа.

Массив пересечений

Пусть ${\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\colon d(v,w)=j\right\}}$ , ${\displaystyle \left\{w\in B\colon d(v,w)=j+1\right\}}$ , ${\displaystyle \left\{w\in C\colon d(v,w)=j-1\right\}}$ .

Если граф ${\displaystyle \Gamma }$ дистанционно-транзитивный, то мощности (кардинальные числа) множеств ${\displaystyle a_{j}=|A|,\,b_{j}=|B|,\,c_{j}=|C|}$ не зависят от вершин ${\displaystyle u,v}$ , а зависят только от расстояния ${\displaystyle j=d(u,v)}$ и называются числами пересечений .

Набор чисел пересечений

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

Примеры

Простейшие примеры дистанционно-транзитивных графов :

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

Более сложные примеры дистанционно-транзитивных графов:

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

Дистанционно-регулярный и дистанционно-транзитивный графы

На первый взгляд дистанционно-транзитивный граф и дистанционно-регулярный граф являются очень близкими понятиями. Действительно, каждый дистанционно-транзитивный граф является дистанционно-регулярным. Однако их природа разная. Если дистанционно-транзитивный граф определяется исходя из симметрии графа через условие автоморфизма, то дистанционно-регулярный граф определяется из условия его комбинаторной регулярности .

Дистанционно-транзитивный граф является вершинно-транзитивным, и для него определены . Для дистанционно-регулярный графа через комбинаторную регулярность также определены числа пересечений. Из дистанционно-транзитивности графа следует его дистанционно-регулярность, но обратное неверно . Это было доказано в 1969 г., еще до введения в обиход термина «дистанционно-транзитивный граф», группой советских математиков ( Г. М. Адельсон-Вельский , Б. Ю. Вейсфелер , А. А. Леман, И. А. Фараджев) . Наименьший дистанционно-регулярный граф, не являющийся дистанционно-транзитивным, — это граф Шрикханде . Единственный тривалентный граф этого типа — это 12-клетка Татта , граф с 126 вершинами .

Классификация дистанционно-транзитивных графов

Первый общий результат в классификации дистанционно-транзитивных графов был получен в Биггзом и Смитом в 1971 году, где были классифицированы графы степени три. В течение последующих десяти-пятнадцати лет центральной проблемой в изучении дистанционно-транзитивных графов была классификация дистанционно-транзитивных графов малых степеней . Дистанционно-транзитивные графы степени четыре были полностью классифицированы Смитом .

В 1983 году Камерон, Прегер, Саксл и Зайц и независимо в 1985 году Вайс доказали, что для любой степени большей двух существует ограниченное число дистанционно-транзитивных графов .

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

В 1971 году Н. Биггз и Д. Смит доказали теорему, что среди кубических (тривалентных) графов существует ровно 12 дистанционно-транзитивных графов :

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

Дистанционно-транзитивные графы степени больше трёх

Все дистанционно-транзитивные графы степени ${\displaystyle k<13}$ известны . Все дистанционно-транзитивных графы степени (валентности) четыре ( ${\displaystyle k=4}$ ) были получены Д. Смитом в 1973-74 годах , а пятой, шестой и седьмой степеней в 1984 году А. А. Ивановым, А. В. Ивановым и И. А. Фараджевым .

В 1986 году А. А. Ивановым и А. В. Ивановым были получены все дистанционно-транзитивные графы степеней от ${\displaystyle k=8}$ до ${\displaystyle k=13}$ .

Походы к классификации

Списки дистанционно-транзитивных графов малых степеней были получены в рамках подхода, основанном на рассмотрении стабилизатора отдельной вершины и теоремах, ограничивающих диаметр графа. А. А. Иванов назвал этот подход «локальным». «Глобальный» же подход основывается на рассмотрении действия группы автоморфизмов на множестве вершин. Этот подход позволяет классифицировать дистанционно-транзитивные графы, действие группы на которых примитивно. Из них затем конструируют все остальные .

Примечания

Литература

Книги

• Biggs N. Distance-Transitive Graphs // Finite Groups of Automorphisms (англ.) . — London & New York: Cambridge University Press, 1971. — Vol. 6. — P. 86—96. — (London Mathematical Society Lecture Note Series).

• Biggs N. L. Distance-Transitive Graphs // Algebraic Graph Theory (англ.) . — 2nd edition. — Cambridge University Press, 1993. — P. 155–163. — 205 p.

• Brouwer A. E., Cohen A. M., Neumaier A. Distance-Transitive Graphs // Distance-Regular Graphs (англ.) . — New York: Springer-Verlag, 1989. — P. 214—234.

• Cohen A. M. Distance-transitive graphs // Topics in Algebraic Graph Theory (англ.) / edited by L. W. Beineke, R. J. Wilson. — Cambridge University Press, 2004. — Vol. 102. — P. 222—249. — (Encyclopedia of Mathematics and its Applications).

• Godsil C., Royle G. Distance-Transitive Graphs // Algebraic Graph Theory (англ.) . — New York: Springer-Verlag, 2001. — Vol. 207. — P. 66—69. — (Graduate Texts in Mathematics). — doi : .
• Ivanov A. A., Ivanov A. V. Distance-transitive graphs of valency k , 8 < k < 13 // Algebraic, Extremal and Metric Combinatorics 1986 (англ.) / Deza, M., Frankl, P., & Rosenberg, I. (Eds.). — Cambridge: Cambridge University Press, 1988. — P. 112—145. — (London Mathematical Society Lecture Note Series). — doi : .

• Ivanov A. A. (англ.) // Faradžev I. A., Ivanov A. A., Klin M. H., Woldar A. J. (eds.) Investigations in Algebraic Theory of Combinatorial Objects. Mathematics and Its Applications (Soviet Series). — Dordrecht: Springer , 1994. — Vol. 84 . — P. 283—378 . — doi : .
• Lauri J., Scapelatto R. Topics in Graph Automorphisms and Reconstruction (англ.) . — 2nd edition. — Cambridge: Cambridge University Press, 2016. — 188 p. — (London Mathematical Society Lecture Note Series). — doi : .

Статьи

• Адельсон-Вельский Г. М., Вейсфелер Б. Ю., Леман А. А., Фараджев И. А. // Доклады Академии наук . — 1969. — Т. 185 , № 5 . — С. 975—976 .
• Иванов А. А., Иванов А. В., Фараджев И. А. // Ж. вычисл. матем. и матем. физ . — 1984. — Т. 24 , № 11 . — С. 1704–1718 .
• Biggs N. L., Smith D. H. On trivalent graphs (англ.) // Bulletin of the London Mathematical Society. — 1971. — Vol. 3 , iss. 2 . — P. 155—158 . — doi : .
• Smith D. H. On tetravalent graphs (англ.) // J. Lodon Math. Soc. — 1973. — Vol. 6 . — P. 659—662 .
• Smith D. H. Distance-transitive graphs of valency four (англ.) // J. Lodon Math. Soc. — 1974. — Vol. 8 . — P. 377—384 .
• Van Bon J. Finite primitive distance-transitive graphs (англ.) // European Journal of Combinatorics. — 2007. — Vol. 28 , iss. 2 . — P. 517—532 . — doi : .

Ссылки

• Weisstein, Eric W. (англ.) на сайте Wolfram MathWorld .