Дистанционно-транзитивный граф
редактировать
Граф Биггса-Смита, самый большой 3-регулярный дистанционно-транзитивный граф.
В математическом поле теории графов, дистанционно-транзитивный граф - это граф такой, что для любых двух вершин v и w на любом расстоянии i и любых других двух вершин x и y на том же расстоянии существует автоморфизм графа, несущего v к x и w к y. Дистанционно-транзитивные графы были впервые определены в 1971 году Норманом Л. Биггсом и Д. Х. Смитом.
Дистанционно-транзитивный граф интересен отчасти потому, что он имеет большую группу автоморфизмов. Некоторые интересные конечные группы представляют собой группы автоморфизмов дистанционно-транзитивных графов, особенно тех, чей диаметр равен 2.
Содержание
- 1 Примеры
- 2 Классификация кубических дистанционно-транзитивных графов
- 3 Связь с дистанционно-регулярными графами
- 4 Ссылки
- 5 Внешние ссылки
Примеры
Некоторые первые примеры семейств дистанционно-транзитивных графов включают:
Классификация кубических дистанционно-транзитивных графов
После их введения в 1971 г. Биггс и Смит показали, что существует только 12 конечных трехвалентных дистанционно-транзитивные графы. Это:
| Имя графика | Количество вершин | Диаметр | Обхват | Массив пересечений |
|---|
| полный граф K4 | 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-вершинный Tutte 12-cage. Наименьшим дистанционно-регулярным графом, который не является дистанционно-транзитивным, является граф Шриханде. Известны полные списки дистанционно-транзитивных графов для некоторых степеней больше трех, но классификация дистанционно-транзитивных графов со сколь угодно большой степенью вершин остается открытой.
Список литературы
- Ранние произведения
- Адельсон-Вельский, Г.М. ; Veĭsfeĭler, B.J. ; Leman, A. A.; Фараджев И.А. (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, MR 0327584.
- Surveys
- Biggs, NL (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 ; Коэн, А. М.; Neumaier, A. (1989), "Distance-Transitive Graphs", 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. Appl. (Советская серия), 84, Dordrecht: Kluwer, pp. 283–378, MR 1321634.
Внешние ссылки
Граф Биггса-Смита, самый большой 3-регулярный дистанционно-транзитивный граф. 