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

Существует несколько различных по форме, но одинаковых по смыслу определений дистанционно-транзитивного графа. Предполагается, что граф ${\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}}}$

называется массивом пересечений дистанционно-транзитивного графа^[7][8].

• Каждый дистанционно-транзитивный граф является дистанционно-регулярным, однако обратное не справедливо^{[4][9][10][11]}.
• Дистанционно-транзитивный граф является вершинно-транзитивным и симметричным^[3].
• Массив пересечений дистанционно-регулярного графа степени ${\displaystyle k}$. Так как дистанционно-транзитивный граф является регулярным, то числа пересечений ${\displaystyle b_{0}=k}$ и ${\displaystyle c_{1}=1}$. Более того, ${\displaystyle a_{i}+b_{i}+c_{i}=k}$. Поэтому массив пересечений дистанционно-регулярного графа можно записать как^[4][7][8]:

${\displaystyle \iota (\Gamma )={\begin{Bmatrix}k,\,b_{1},\,\dots ,\,b_{d-1}\,;\,1,\,c_{2},\,\dots ,\,c_{d}\end{Bmatrix}}}$

Простейшие примеры дистанционно-транзитивных графов^[5][12][13]:

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

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

• граф Джонсона^[14]
• граф Грассмана^[15]
• граф Хемминга^[16][17]
• граф Ливингстона^[18]

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

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

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

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

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

Название графа	Число вершин	Диаметр	Обхват	Массив пересечений
Полный граф K4	4	1	3	{3;1}
Полный двудольный граф K3,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}$ известны^[28]. Все дистанционно-транзитивных графы степени (валентности) четыре (${\displaystyle k=4}$) были получены Д. Смитом в 1973-74 годах^[23][24], а пятой, шестой и седьмой степеней в 1984 году А. А. Ивановым, А. В. Ивановым и И. А. Фараджевым^[29].

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

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