Дистанционно-транзитивный граф
 | Эта статья включает список литературы , связанную литературу или внешние ссылки , но ее источники остаются неясными, поскольку в ней отсутствуют встроенные цитаты . ( сентябрь 2021 г. ) |
В математической области теории графов дистанционно -транзитивный граф — это граф , в котором для любых двух вершин v и w, находящихся на любом расстоянии i , и любых других двух вершин x и y , существует автоморфизм на том же расстоянии граф, который переводит v в x и w в y . Дистанционно-транзитивные графы были впервые определены в 1971 году Норманом Л. Биггсом и Д. Х. Смитом.
Дистанционно-транзитивный граф интересен отчасти потому, что он имеет большую группу автоморфизмов . Некоторые интересные конечные группы — это группы автоморфизмов дистанционно-транзитивных графов, особенно тех, диаметр которых равен 2.
Примеры [ править ]
Некоторые первые примеры семейств дистанционно-транзитивных графов включают:
- Графики Джонсона .
- Грассмана Графы .
- Графы Хэмминга (включая графы Гиперкуба ).
- Графики свернутого куба .
- Графики квадратной ладьи .
- График Ливингстона .
кубических дистанционно- транзитивных Классификация графов
Введя их в 1971 году, Биггс и Смит показали, что существует только 12 конечно связных трехвалентных дистанционно-транзитивных графов. Это:
| Имя графика | Количество вершин | Диаметр | Обхват | Массив пересечений |
|---|---|---|---|---|
| Тетраэдрический граф или полный граф К 4 | 4 | 1 | 3 | {3;1} |
| полный двудольный граф K 3,3 | 6 | 2 | 4 | {3,2;1,3} |
| график Петерсена | 10 | 2 | 5 | {3,2;1,1} |
| Кубический граф | 8 | 3 | 4 | {3,2,1;1,2,3} |
| График Хивуда | 14 | 3 | 6 | {3,2,2;1,1,3} |
| Граф Паппуса | 18 | 4 | 6 | {3,2,2,1;1,1,2,3} |
| Граф Кокстера | 28 | 4 | 7 | {3,2,2,1;1,1,1,2} |
| График Олла – Кокстера | 30 | 4 | 8 | {3,2,2,2;1,1,1,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} |
| График Биггса-Смита | 102 | 7 | 9 | {3,2,2,2,1,1,1;1,1,1,1,1,1,3} |
| Граф Фостера | 90 | 8 | 10 | {3,2,2,2,2,1,1,1;1,1,1,1,2,2,2,3} |
Связь с дистанционно-регулярными графами [ править ]
Каждый дистанционно-транзитивный граф дистанционно регулярен , но обратное не обязательно верно.
В 1969 году, еще до публикации определения Биггса-Смита, российская группа под руководством Георгия Адельсона-Вельского показала, что существуют графы, которые являются дистанционно регулярными, но не дистанционно транзитивными. Наименьшим дистанционно регулярным графом, который не является дистанционно транзитивным, является граф Шрикханде с 16 вершинами и степенью 6. Единственный граф этого типа со степенью три — это 12- клетка Тутте с 126 вершинами . Известны полные списки дистанционно-транзитивных графов на несколько степеней больше трёх, но классификация дистанционно-транзитивных графов со сколь угодно большой степенью вершин остаётся открытой.
Ссылки [ править ]
- Ранние работы
- Адельсон-Вельский, ГМ ; Вейсфейлер, Б.Ю. ; Леман, А.А.; Фараджев И.А. (1969), "Пример графа, не имеющего транзитивной группы автоморфизмов", Доклады АН СССР , 185 : 975–976, МР 0244107 .
- Биггс, Норман (1971), «Матрицы пересечений для линейных графов», Комбинаторная математика и ее приложения (Proc. Conf., Oxford, 1969) , Лондон: Academic Press, стр. 15–23, MR 0285421 .
- Биггс, Норман (1971), Конечные группы автоморфизмов , Серия лекций Лондонского математического общества, том. 6, Лондон и Нью-Йорк: Издательство Кембриджского университета, MR 0327563 .
- Биггс, Нидерланды; Смит, Д.Х. (1971), «О трехвалентных графах», Бюллетень Лондонского математического общества , 3 (2): 155–158, doi : 10.1112/blms/3.2.155 , MR 0286693 .
- Смит, Д.Х. (1971), «Примитивные и импримитивные графы», Ежеквартальный журнал математики , вторая серия, 22 (4): 551–557, doi : 10.1093/qmath/22.4.551 , MR 0327584 .
- Опросы
- Биггс, Н.Л. (1993), «Дистанционно-транзитивные графы», Алгебраическая теория графов (2-е изд.), Cambridge University Press, стр. 155–163 , глава 20.
- Ван Бон, Джон (2007), «Конечные примитивные дистанционно-транзитивные графы», European Journal of Combinatorics , 28 (2): 517–532, doi : 10.1016/j.ejc.2005.04.014 , MR 2287450 .
- Брауэр, AE ; Коэн, AM; Ноймайер, А. (1989), «Дистанционно-транзитивные графы», Дистанционно-регулярные графы , Нью-Йорк: Springer-Verlag, стр. 214–234 , глава 7.
- Коэн, А.М. Коэн (2004), «Дистанционно-транзитивные графы», в Бейнеке, Л.В.; Уилсон, Р.Дж. (ред.), Темы алгебраической теории графов , Энциклопедия математики и ее приложений, том. 102, Издательство Кембриджского университета, стр. 222–249 .
- Годсил, К. ; Ройл, Г. (2001), «Дистанционно-транзитивные графы», Алгебраическая теория графов , Нью-Йорк: Springer-Verlag, стр. 66–69 , раздел 4.5.
- Иванов А.А. (1992), «Дистанционно-транзитивные графы и их классификация», Фараджев И.А.; Иванов А.А.; Клин, М.; и др. (ред.), Алгебраическая теория комбинаторных объектов , Матем. Прил. (Советский сериал), вып. 84, Дордрехт: Kluwer, стр. 283–378, MR 1321634 .