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

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

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

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

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

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

Полный граф $K_7$

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

Граф Хивуда

Граф Паппа

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

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

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

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

Шаблон:Начало скрытого блока Неориентированный, связный, ограниченный граф $\mathrm{\Gamma }=(V,E)$ называется дистанционно-транзитивным, если для двух любых упорядоченных пар его вершин $(u,v)$ и $(x,y)$, таких что $d(u,v)=d(x,y)$ существует автоморфизм $g$ графа $\mathrm{\Gamma }$, такой что $g:(u,v)\to (x,y)$ Шаблон:Конец скрытого блока Шаблон:Начало скрытого блока Пусть неориентрированный, связный, ограниченный граф $\mathrm{\Gamma }=(V,E)$ обладает группой автоморфизмов $\mathrm{A}\mathrm{u}\mathrm{t}(\mathrm{\Gamma })$. Граф $\mathrm{\Gamma }$ называется дистанционно-транзитивным, если для всех вершин $u,v,x,y$, таких что $d(u,v)=d(x,y)$, существует автоморфизм $g\in G$, который отображает $u\to x$ и $v\to y$ Шаблон:Конец скрытого блока Шаблон:Начало скрытого блока Неориентированный связный конечный граф $\mathrm{\Gamma }=(V,E)$ без петель и кратных ребер называется дистанционно-транзитивным, если его груп­па автоморфизмов $\mathrm{A}\mathrm{u}\mathrm{t}(\mathrm{\Gamma })$ действует транзитивно на упорядоченных па­рах равноудаленных вершин Шаблон:Конец скрытого блока Шаблон:Начало скрытого блока Пусть $\mathrm{\Gamma }=(V,E)$ — связный граф диаметра $D$ и $\mathrm{A}\mathrm{u}\mathrm{t}(\mathrm{\Gamma })$ — его группа автоморфизмов. $\mathrm{A}\mathrm{u}\mathrm{t}(\mathrm{\Gamma })$ дистанционно-транзитивна на $\mathrm{\Gamma }$, если она транзитивна на каждом множестве ${\mathrm{\Gamma }}_i=\{(x,y)\in \mathrm{\Gamma }\times \mathrm{\Gamma }:d(x,y)=i\}$, где $i=0,1,\dots ,D$. Граф $\mathrm{\Gamma }$ является дистанционно-транзитивным, если его группа автоморфизмов $\mathrm{A}\mathrm{u}\mathrm{t}(\mathrm{\Gamma })$ является дистанционно-транзитивной на нем. Шаблон:Конец скрытого блока Шаблон:Начало скрытого блока Пусть неориентированный, связанный, ограниченный граф $\mathrm{\Gamma }=(V,E)$ обладает группой автоморфизмов $\mathrm{A}\mathrm{u}\mathrm{t}(\mathrm{\Gamma })$. Пусть $G$ есть подгруппа $\mathrm{A}\mathrm{u}\mathrm{t}(\mathrm{\Gamma })$. Граф $\mathrm{\Gamma }$ называется $G$-дистанционно-транзитивным (Шаблон:Lang-en), если для каждой четвёрки вершин $u,v,x,y$, таких что $d(u,v)=d(x,y)$, существует автоморфизм $g\in G$, который отображает $u\to x$ и $v\to y$. Дистанционно-транзитивным называется граф, который является $G$-дистанционно-транзитивным для некоторой подгруппы $G$ группы автоморфизмов графа.

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

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

Пусть $\mathrm{\Gamma }=(V,E)$ есть неориентированный, связанный, ограниченный граф, а две его вершины $u,v\in V(\mathrm{\Gamma })$ находятся на расстоянии $j=d(u,v)$ друг от друга. Все вершины $w$, инцидентные к вершине $u$, можно разбить на три множества $A$, $B$ и $C$ в зависимости от их расстояния $d(v,w)$ до вершины $v$ :

$\{w\in A:d(v,w)=j\}$,   $\{w\in B:d(v,w)=j+1\}$,   $\{w\in C:d(v,w)=j-1\}$.

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

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

$\iota (\mathrm{\Gamma })=\left\{\begin{array}{cccccc}\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{array}\right\}$

называется массивом пересечений дистанционно-транзитивного графаШаблон:SfnШаблон:Sfn.

Свойства

• Каждый дистанционно-транзитивный граф является дистанционно-регулярным, однако обратное не справедливоШаблон:SfnШаблон:SfnШаблон:SfnШаблон:Sfn.
• Дистанционно-транзитивный граф является вершинно-транзитивным и симметричнымШаблон:Sfn.
• Массив пересечений дистанционно-регулярного графа степени $k$. Так как дистанционно-транзитивный граф является регулярным, то числа пересечений $b_0=k$ и $c_1=1$. Более того, $a_i+b_i+c_i=k$. Поэтому массив пересечений дистанционно-регулярного графа можно записать какШаблон:SfnШаблон:SfnШаблон:Sfn:

$\iota (\mathrm{\Gamma })=\left\{\begin{array}{c}k,b_1,\dots ,b_{d-1};1,c_2,\dots ,c_d\end{array}\right\}$

Примеры

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

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

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

• граф ДжонсонаШаблон:Sfn
• граф ГрассманаШаблон:Sfn
• граф ХеммингаШаблон:SfnШаблон:Sfn
• граф Ливингстона

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

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

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

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

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

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

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

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

Название графа	Число вершин	Диаметр	Обхват	Массив пересечений
Полный граф K4	4	1	3	{3;1}
Полный двудольный граф K3,3	6	2	4	{3,2;1,3}
Граф гиперкуба $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}

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

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

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

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

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

Литература

Книги

• Шаблон:Книга

• Шаблон:Книга

• Шаблон:Книга
• Шаблон:Книга

• Шаблон:Книга
• Шаблон:Книга

• Шаблон:Статья
• Шаблон:Книга

Статьи

• Шаблон:Статья
• Шаблон:Статья
• Шаблон:Статья
• Шаблон:Статья
• Шаблон:Статья
• Шаблон:Статья

Ссылки

• Шаблон:Mathworld