Дистанционно-транзитивный граф
Дистанционно-транзитивный граф (англ. distance-transitive graph) — это граф, в котором любая упорядоченная пара вершин переводится в любую другую упорядоченную пару вершин с тем же расстоянием между вершинами одним из автоморфизмов графа.
Определение
Определение дистанционно-транзитивного графа[1][2][3][4][5]:
Пусть неориентрированный, связанный, ограниченный граф обладает группой автоморфизмов . Количество ребер по наикратчайшему пути, соединяющему , называется расстоянием между и и обозначается как . Пусть есть подгруппа . Граф называется -дистанционно-транзитивным (англ. -distance-transitive), если для каждой четвёрки вершин , таких что , существует автоморфизм , который отображает и .
Другими словами, есть -дистанционно-транзитивный граф, если подгруппа действует транзитивно на множестве при каждом .
Массив пересечений
Пусть есть неориентированный, связанный, ограниченный граф, а две его вершины находятся на расстоянии друг от друга. Все вершины , инцидентные к вершине , можно разбить на три множества , и в зависимости от их расстояния до вершины :
- , , .
Если граф дистанционно-транзитивный, то мощности (кардинальные числа) множеств не зависят от вершин , а зависят только от расстояния и называются числами пересечений.
Набор чисел пересечений
называется массивом пересечений дистанционно-транзитивного графа[6][7].
Свойства
- Каждый дистанционно-транзитивный граф является дистанционно-регулярным, однако обратное не справедливо[2][8][9][10].
- Это было доказано в 1969 году, ещё до введения в обиход термина «дистанционно-транзитивный граф», группой советских математиков (Г. М. Адельсон-Вельский, Б. Ю. Вейсфелер, А. А. Леман, И. А. Фараджев)[9][10][11]. Наименьший дистанционно-регулярный граф, не являющийся дистанционно-транзитивным — это граф Шрикханде. Единственный тривалентный граф этого типа — это 12-клетка Татта, граф с 126 вершинами[9].
- Дистанционно-транзитивный граф является вершинно-транзитивным и симметричным[4].
- Массив пересечений дистанционно-регулярного графа степени . Так как дистанционно-транзитивный граф является регулярным, то числа пересечений и . Более того, . Поэтому массив пересечений дистанционно-регулярного графа можно записать как[2][6][7]:
Примеры
Простейшие примеры дистанционно-транзитивных графов[5][12][13]:
- полные графы
- полные двудольные графы (биклики) с равными долями
- графы гиперкуба
Более сложные примеры дистанционно-транзитивных графов:
Классификация кубических дистанционно-транзитивных графов
В 1971 году Н. Биггс и Д. Смит доказали теорему, что среди кубических (тривалентных) графов существует ровно 12 дистанционно-транзитивных графов[19]:
Название графа | Число вершин | Диаметр | Обхват | Массив пересечений |
---|---|---|---|---|
Полный граф 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} |
Дистанционно-транзитивные графы степени больше трёх
Все дистанционно-транзитивные графы степени известны[20].
Все дистанционно-транзитивных графы степени (валентности) четыре () были получены Д. Смитом в 1973-74 годах[21][22], а пятой, шестой и седьмой степеней в 1984 году А. А. Ивановым, А. В. Ивановым и И. А. Фараджевым[23].
В 1986 году А. А. Ивановым и А. В. Ивановым были получены все дистанционно-транзитивные графы степеней от до [24].
Примечания
- Ivanov, 1994, p. 285.
- Иванов, Иванов и Фараджев, 1984, с. 1704.
- Biggs, 1971, p. 87.
- Biggs, 1993, p. 118.
- Cohen, 2004, p. 223.
- Lauri and Scapelatto, 2016, p. 33.
- Biggs, 1993, p. 157.
- Lauri and Scapelatto, 2016, p. 34.
- Brower, Cohen and Neumaier, 1989, p. 136.
- Cohen, 2004, p. 232.
- Адельсон-Вельский, Вейсфелер, Леман и Фараджев, 1969.
- Godsil and Royle, 2001, p. 66-67.
- Biggs, 1993, p. 158.
- Brower, Cohen and Neumaier, 1989, p. 255.
- Brower, Cohen and Neumaier, 1989, p. 269.
- Van Bon, 2007, p. 519.
- Brower, Cohen and Neumaier, 1989, p. 261.
- Weisstein, Eric W. Livingstone Graph (англ.) на сайте Wolfram MathWorld.
- Biggs and Smith, 1971.
- Brower, Cohen and Neumaier, 1989, p. 221—225.
- Smith, 1973.
- Smith, 1974.
- Иванов, Иванов и Фараджев, 1984.
- Ivanov and Ivanov, 1988.
Литература
- Книги
- Biggs N. Distance-Transitive Graphs // Finite Groups of Automorphisms (англ.). — London & New York: Cambridge University Press, 1971. — Vol. 6. — P. 86—96. — (London Mathematical Society Lecture Note Series).
- Biggs N. L. Distance-Transitive Graphs // Algebraic Graph Theory (англ.). — 2nd edition. — Cambridge University Press, 1993. — P. 155–163. — 205 p.
- Brouwer A. E., Cohen A. M., Neumaier A. Distance-Transitive Graphs // Distance-Regular Graphs (англ.). — New York: Springer-Verlag, 1989. — P. 214—234.
- Cohen A. M. Distance-transitive graphs // Topics in Algebraic Graph Theory (англ.) / edited by L. W. Beineke, R. J. Wilson. — Cambridge University Press, 2004. — Vol. 102. — P. 222—249. — (Encyclopedia of Mathematics and its Applications).
- Godsil C., Royle G. Distance-Transitive Graphs // Algebraic Graph Theory (англ.). — New York: Springer-Verlag, 2001. — Vol. 207. — P. 66—69. — (Graduate Texts in Mathematics). — doi:10.1007/978-1-4613-0163-9.
- Ivanov A. A., Ivanov A. V. Distance-transitive graphs of valency k, 8 < k < 13 // Algebraic, Extremal and Metric Combinatorics 1986 (англ.) / Deza, M., Frankl, P., & Rosenberg, I. (Eds.). — Cambridge: Cambridge University Press, 1988. — P. 112—145. — (London Mathematical Society Lecture Note Series). — doi:10.1017/CBO9780511758881.
- Ivanov A. A. Distance-Transitive Graphs and Their Classification (англ.) // Faradžev I. A., Ivanov A. A., Klin M. H., Woldar A. J. Investigations in Algebraic Theory of Combinatorial Objects. Mathematics and Its Applications (Soviet Series) / (eds.). — Dordrecht: Springer, 1994. — Vol. 84. — P. 283—378. — doi:10.1007/978-94-017-1972-8.
- Lauri J., Scapelatto R. Topics in Graph Automorphisms and Reconstruction (англ.). — 2nd edition. — Cambridge: Cambridge University Press, 2016. — 188 p. — (London Mathematical Society Lecture Note Series). — doi:10.1017/CBO9781316669846.
- Статьи
- Адельсон-Вельский Г. М., Вейсфелер Б. Ю., Леман А. А., Фараджев И. А. Об одном примере графа, не имеющего транзитивной группы автоморфизмов // Доклады Академии наук. — 1969. — Т. 185, № 5. — С. 975—976.
- Иванов А. А., Иванов А. В., Фараджев И. А. Дистанционно-транзитивные графы степени 5, 6 и 7 // Ж. вычисл. матем. и матем. физ. — 1984. — Т. 24, № 11. — С. 1704–1718.
- Biggs N. L., Smith D. H. On trivalent graphs (англ.) // Bulletin of the London Mathematical Society. — 1971. — Vol. 3, iss. 2. — P. 155—158. — doi:10.1112/blms/3.2.155.
- Smith D. H. On tetravalent graphs (англ.) // J. Lodon Math. Soc. — 1973. — Vol. 6. — P. 659—662.
- Smith D. H. Distance-transitive graphs of valency four (англ.) // J. Lodon Math. Soc. — 1974. — Vol. 8. — P. 377—384.
- Van Bon J. Finite primitive distance-transitive graphs (англ.) // European Journal of Combinatorics. — 2007. — Vol. 28, iss. 2. — P. 517—532. — doi:10.1016/j.ejc.2005.04.014.