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

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

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

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

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

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

Полный граф ${\displaystyle K_{7}}$

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

Граф Хивуда

Граф Паппа

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

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

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

Определение по Годзилу—Ройлу ^[1]

Неориентированный, связный, ограниченный граф ${\displaystyle \Gamma =(V,E)}$ называется дистанционно-транзитивным, если для двух любых упорядоченных пар его вершин ${\displaystyle (u,v)}$ и ${\displaystyle (x,y)}$, таких что ${\displaystyle d(u,v)=d(x,y)}$ существует автоморфизм ${\displaystyle g}$ графа ${\displaystyle \Gamma }$, такой что ${\displaystyle g:(u,v)\rightarrow (x,y)}$

Определение по Биггзу ^[2][3]

Пусть неориентрированный, связный, ограниченный граф ${\displaystyle \Gamma =(V,E)}$ обладает группой автоморфизмов ${\displaystyle \mathrm {Aut} (\Gamma )}$. Граф ${\displaystyle \Gamma }$ называется дистанционно-транзитивным, если для всех вершин ${\displaystyle u,v,x,y}$, таких что ${\displaystyle d(u,v)=d(x,y)}$, существует автоморфизм ${\displaystyle g\in G}$, который отображает ${\displaystyle u\rightarrow x}$ и ${\displaystyle v\rightarrow y}$

Определение по Иванову—Иванову—Фараджеву ^[4]

Неориентированный связный конечный граф ${\displaystyle \Gamma =(V,E)}$ без петель и кратных ребер называется дистанционно-транзитивным, если его груп­па автоморфизмов ${\displaystyle \mathrm {Aut} (\Gamma )}$ действует транзитивно на упорядоченных па­рах равноудаленных вершин

Определение по Коуэну ^[5]

Пусть ${\displaystyle \Gamma =(V,E)}$ — связный граф диаметра ${\displaystyle D}$ и ${\displaystyle \mathrm {Aut} (\Gamma )}$ — его группа автоморфизмов. ${\displaystyle \mathrm {Aut} (\Gamma )}$ дистанционно-транзитивна на ${\displaystyle \Gamma }$, если она транзитивна на каждом множестве ${\displaystyle \Gamma _{i}=\left\{(x,y)\in \Gamma \times \Gamma :d(x,y)=i\right\}}$, где ${\displaystyle i=0,\,1,\,\ldots ,\,D}$. Граф ${\displaystyle \Gamma }$ является дистанционно-транзитивным, если его группа автоморфизмов ${\displaystyle \mathrm {Aut} (\Gamma )}$ является дистанционно-транзитивной на нем.

Определение по Иванову ^[6]

Пусть неориентированный, связанный, ограниченный граф ${\displaystyle \Gamma =(V,E)}$ обладает группой автоморфизмов ${\displaystyle \mathrm {Aut} (\Gamma )}$. Пусть ${\displaystyle G}$ есть подгруппа ${\displaystyle \mathrm {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}$. Дистанционно-транзитивным называется граф, который является ${\displaystyle G}$-дистанционно-транзитивным для некоторой подгруппы ${\displaystyle G}$ группы автоморфизмов графа.

Другими словами, ${\displaystyle \Gamma }$ есть ${\displaystyle G}$-дистанционно-транзитивный граф, если подгруппа ${\displaystyle G}$ действует транзитивно на множестве ${\displaystyle \left\{(x,y)\mid x,e\in V(\Gamma ),\,d(x,y)=i\right\}}$ при каждом ${\displaystyle i}$.

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

Пусть ${\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].