Граф, в котором любые два узла, находящиеся на одинаковом расстоянии, изоморфны
Граф Биггса -Смита , крупнейший 3-регулярный дистанционно-транзитивный граф.
В математической области теории графов дистанционно -транзитивный граф — это граф , такой что для любых двух вершин v и w на любом расстоянии i и любых двух других вершин x и y на том же расстоянии существует автоморфизм графа, который переводит v в x и w в y . Дистанционно-транзитивные графы были впервые определены в 1971 году Норманом Л. Биггсом и Д. Х. Смитом.
Дистанционно-транзитивный граф интересен отчасти потому, что он имеет большую группу автоморфизмов . Некоторые интересные конечные группы — это группы автоморфизмов дистанционно-транзитивных графов, особенно тех, диаметр которых равен 2.
Примеры
Вот некоторые первые примеры семейств дистанционно-транзитивных графов:
После их введения в 1971 году Биггс и Смит показали, что существует всего 12 конечных связных трехвалентных дистанционно-транзитивных графов. Это:
Отношение к дистанционно-регулярным графам
Каждый дистанционно-транзитивный граф является дистанционно-регулярным , но обратное не обязательно верно.
В 1969 году, до публикации определения Биггса–Смита, российская группа под руководством Георгия Адельсона-Вельского показала, что существуют графы, которые являются дистанционно-регулярными, но не дистанционно-транзитивными. Наименьшим дистанционно-регулярным графом, который не является дистанционно-транзитивным, является граф Шрикханде с 16 вершинами и степенью 6. Единственный граф этого типа со степенью три — это 126-вершинная клетка Тутта 12-cage . Полные списки дистанционно-транзитивных графов известны для некоторых степеней, больших трех, но классификация дистанционно-транзитивных графов с произвольно большой степенью вершин остается открытой.
Биггс, Норман (1971), «Матрицы пересечений для линейных графов», Комбинаторная математика и ее приложения (Proc. Conf., Оксфорд, 1969) , Лондон: Academic Press, стр. 15–23, MR 0285421.
Биггс, Норман (1971), Конечные группы автоморфизмов , Серия лекций Лондонского математического общества, т. 6, Лондон и Нью-Йорк: Cambridge University Press, MR 0327563.
Биггс, Н. Л.; Смит, Д. Х. (1971), «О трехвалентных графах», Бюллетень Лондонского математического общества , 3 (2): 155–158, doi :10.1112/blms/3.2.155, MR 0286693.
Смит, Д. Х. (1971), «Примитивные и импримитивные графы», The Quarterly Journal of Mathematics , Вторая серия, 22 (4): 551–557, doi :10.1093/qmath/22.4.551, MR 0327584.
Опросы
Биггс, Н. Л. (1993), «Расстояние-транзитивные графы», Алгебраическая теория графов (2-е изд.), Cambridge University Press, стр. 155–163, глава 20.
Ван Бон, Джон (2007), «Конечные примитивные дистанционно-транзитивные графы», Европейский журнал комбинаторики , 28 (2): 517–532, doi : 10.1016/j.ejc.2005.04.014 , MR 2287450.
Брауэр, А. Э.; Коэн, А. М.; Ноймайер, А. (1989), «Дистанционно-транзитивные графы», Distance-Regular Graphs , Нью-Йорк: Springer-Verlag, стр. 214–234, глава 7.
Коэн, А. М. Коэн (2004), «Расстояние-транзитивные графы», в Бейнеке, Л. В.; Уилсон, Р. Дж. (ред.), Темы алгебраической теории графов , Энциклопедия математики и ее приложений, т. 102, Cambridge University Press, стр. 222–249.
Годсил, К.; Ройл , Г. (2001), «Расстояние-транзитивные графы», Алгебраическая теория графов , Нью-Йорк: Springer-Verlag, стр. 66–69, раздел 4.5.
Иванов, А.А. (1992), «Расстояночно-транзитивные графы и их классификация», в Faradžev, IA; Ivanov, AA; Klin, M.; et al. (ред.), The Algebraic Theory of Combinatori Objects , Math. Appl. (Soviet Series), vol. 84, Dordrecht: Kluwer, pp. 283–378, MR 1321634.
