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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Классификация кубических дистанционно-транзитивных графов В 1971 году Н. Биггз и Д. Смит доказали теорему, что среди кубических (тривалентных) графов существует ровно 12 дистанционно-транзитивных графов: Название графа Число вершин Диаметр Обхват Массив пересечений Полный граф K4 4 1 3 {3;1} Полный двудольный граф K3,3 6 2 4 {3,2;1,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}

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

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

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

Примечания

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

Статьи

Ссылки

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