В математической области теории графов , А расстояние-симметрический граф является графиком таким образом, чтобы, учитывая любые две вершины V и W в любом расстоянии я , и любые другие две вершины х и у на том же расстоянии, существует автоморфизм из граф, который переводит v в x и w в y . Дистанционно-транзитивные графы были впервые определены в 1971 году Норманом Л. Биггсом и Д.Х. Смитом.
Дистанционно-транзитивный граф интересен отчасти потому, что он имеет большую группу автоморфизмов . Некоторые интересные конечные группы - это группы автоморфизмов дистанционно транзитивных графов, особенно тех, диаметр которых равен 2.
Примеры [ править ]
Некоторые первые примеры семейств дистанционно-транзитивных графов включают:
- Джонсон графов .
- Грассман графики .
- В Хэмминге графы .
- В сложенной кубе графика .
- Графики квадратной ладьи .
- Гиперкуб графика .
- Ливингстон график .
Классификация кубических дистанционно-транзитивных графов [ править ]
Введя их в 1971 г., Биггс и Смит показали, что существует всего 12 конечных трехвалентных дистанционно-транзитивных графов. Это:
| Название графика | Количество вершин | Диаметр | Обхват | Массив пересечений |
|---|---|---|---|---|
| Тетраэдрический граф или полный граф K 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 году, до публикации определения Биггса – Смита, российская группа под руководством Георгия Адельсона-Вельского показала, что существуют дистанционно регулярные графы, но не дистанционно транзитивные. Единственный граф этого типа со степенью три - это 126-вершинный 12-клеточный Tutte . Наименьший дистанционно регулярный граф, который не является дистанционно транзитивным, - это граф Шриханде . Известны полные списки дистанционно-транзитивных графов для некоторых степеней больше трех, но классификация дистанционно-транзитивных графов со сколь угодно большой степенью вершин остается открытой.
Ссылки [ править ]
- Ранние работы
- Адельсон-Вельский, GM ; Veĭsfeĭler, B.J. ; Leman, AA; Фараджев И.А. (1969), «Пример графа, не имеющего транзитивной группы автоморфизмов», Докл. АН СССР , 185 : 975–976, MR 0244107..
- Биггс, Норман (1971), "Матрицы пересечений для линейных графов", Комбинаторная математика и ее приложения (Proc. Conf., Oxford, 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), «Примитивные и импримитивные графы», Ежеквартальный журнал математики. Оксфорд. Вторая серия , 22 (4): 551-557, DOI : 10,1093 / qmath / 22.4.551 , МР 0327584.
- Обзоры
- Биггс, Н.Л. (1993), "Дистанционно-транзитивные графы", алгебраическая теория графов (2-е изд.), Cambridge University Press, стр. 155–163, глава 20.
- Ван Бон, Джон (2007), "Конечные примитивные заочные-транзитивные графы", Европейский журнал комбинаторика , 28 (2): 517-532, DOI : 10.1016 / j.ejc.2005.04.014 , MR 2287450.
- Брауэр, AE ; Коэн, AM; Neumaier, A. (1989), "Дистанционно-транзитивные графы", Distance-Regular Graphs , New York: Springer-Verlag, pp. 214–234., глава 7.
- Коэн, AM Cohen (2004), «Дистанционно-транзитивные графы», в Beineke, LW; Уилсон, Р.Дж. (ред.), « Темы алгебраической теории графов» , «Энциклопедия математики и ее приложений», 102 , Cambridge University Press, стр. 222–249..
- Годсил, К .; Ройл, Г. (2001), "Дистанционно-транзитивные графы", Алгебраическая теория графов , Нью-Йорк: Springer-Verlag, стр. 66–69., раздел 4.5.
- Иванов, А.А. (1992), "Дистанционно-транзитивные графы и их классификация", Фараджев, И.А. Иванов, АА; Клин, М .; и другие. (ред.), Алгебраическая теория комбинаторных объектов , Math. Прил. (Советская серия), 84 , Dordrecht: Kluwer, стр. 283–378, MR 1321634.
Внешние ссылки [ править ]
- Вайсштейн, Эрик В. "Дистанционно-переходный граф" . MathWorld .
