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

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

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

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

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

Существует несколько различных по форме, но одинаковых по смыслу определений дистанционно-транзитивного графа. Предполагается, что граф  — неориентированный, связанный и ограниченный. В определении используются понятия расстояние между вершинами графа и автоморфизм графа:
 Расстояние  между двумя вершинами  графа  есть количество рёбер по наикратчайшему пути, соединяющему  и 
 Автоморфизм графа   — взаимно однозначное отображение множества вершин графа на себя, сохраняющее смежность вершин.
 Группа автоморфизмов графа  — множество автоморфизмов графа.

  Определение по Годзилу—Ройлу 
   Неориентированный, связный, ограниченный граф  называется дистанционно-транзитивным, если для двух любых упорядоченных пар его вершин  и , таких что  существует автоморфизм  графа , такой что 
  
  

  Определение по Биггзу 
   Пусть неориентрированный, связный, ограниченный граф  обладает группой автоморфизмов . Граф  называется дистанционно-транзитивным, если для всех вершин , таких что , существует автоморфизм , который отображает  и 
  
  

  Определение по Иванову—Иванову—Фараджеву 
   Неориентированный связный конечный граф  без петель и кратных ребер называется дистанционно-транзитивным, если его груп­па автоморфизмов  действует транзитивно на упорядоченных па­рах равноудаленных вершин
  
  

  Определение по Коуэну 
   Пусть  — связный граф диаметра  и  — его группа автоморфизмов.  дистанционно-транзитивна на , если она транзитивна на каждом множестве , где . Граф  является дистанционно-транзитивным, если его группа автоморфизмов  является дистанционно-транзитивной на нем.
  
  

  Определение по Иванову 
   Пусть неориентированный, связанный, ограниченный граф  обладает группой автоморфизмов . Пусть  есть подгруппа . Граф  называется -дистанционно-транзитивным (), если для каждой четвёрки вершин , таких что , существует автоморфизм , который отображает  и . Дистанционно-транзитивным называется граф, который является -дистанционно-транзитивным для некоторой подгруппы  группы автоморфизмов графа.

 Другими словами,  есть -дистанционно-транзитивный граф, если подгруппа  действует транзитивно на множестве  при каждом .

Массив пересечений 
Пусть  есть неориентированный, связанный, ограниченный граф, а две его вершины  находятся на расстоянии  друг от друга. Все вершины , инцидентные к вершине , можно разбить на три множества ,  и  в зависимости от их расстояния  до вершины  :
 ,   ,   .

Если граф  дистанционно-транзитивный, то мощности (кардинальные числа) множеств  не зависят от вершин , а зависят только от расстояния  и называются числами пересечений.

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

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

Свойства 
 Каждый дистанционно-транзитивный граф является дистанционно-регулярным, однако обратное не справедливо.
 Дистанционно-транзитивный граф является вершинно-транзитивным и симметричным.
 Массив пересечений дистанционно-регулярного графа степени . Так как дистанционно-транзитивный граф является регулярным, то числа пересечений  и . Более того, . Поэтому массив пересечений дистанционно-регулярного графа можно записать как:

Примеры 
Простейшие примеры дистанционно-транзитивных графов:
 полные графы 
 полные двудольные графы (биклики) с равными долями 
 графы гиперкуба 

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

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

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

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

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

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

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

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

В 1986 году А. А. Ивановым и А. В. Ивановым были получены все дистанционно-транзитивные графы степеней от  до  .

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

Примечания

Литература 
Книги

 

 

 

 

 
 

 
 

Статьи

Ссылки 
 

Алгебраическая теория графов
Регулярные графы