Дистанционно-транзитивный граф — такой граф, что для любых двух заданных вершин v и w, находящихся на расстоянии i, и любых двух вершин x и y, находящихся на том же расстоянии, существует автоморфизм графа, который переводит v в x и w в y.
Дистанционно-транзитивный граф является вершинно-транзитивным и симметричным, так же как и дистанционно-регулярным.
Дистанционно-транзитивный граф интересен, в частности, из-за большой группы автоморфизмов. Некоторые интересные конечные группы являются группами автоморфизмов дистанционно-транзитивных графов, особенно тех, чей диаметр равен 2.
Впервые определены в 1971 году Норманном Бигсом[en] и Д. Х. Смитом (D. H. Smith), которые показали, что существует только 12 конечных тривалентных дистанционно-транзитивных графов:
| Название графа | Число вершин | Диаметр | Обхват | Массив пересечений |
|---|---|---|---|---|
| Полный граф K4 | 4 | 1 | 3 | {3;1} |
| Полный двудольный граф K3,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 году группа советских математиков под руководством Адельсона-Вельского показала, что существуют графы, являющиеся дистанционно-регулярными, но не дистанционно-транзитивными. Единственный граф этого типа степени три — это 12-клетка Татта[en], граф с 126 вершинами. Наименьший дистанционно-регулярный граф, не являющийся дистанционно-транзитивным — это граф Шрикханда[en]. Полный список дистанционно-транзитивных графов известен для некоторых степеней больших трёх, но классификация дистанционно-транзитивных графов с произвольно большой степенью остаётся открытой.
Простейшее асимптотическое[en] семейство дистанционно-транзитивных графов — это графы гиперкубов. Другие семейства — это складные кубические графы и квадратные ладейные графы. Все три семейства имеют произвольно большую степень.
Литература
- Ранние работы
- G. M. Adel'son-Vel'skii, B. Ju. Veĭsfeĭler, A. A. Leman, I. A. Faradžev. An example of a graph which has no transitive group of automorphisms // Доклады Академии наук. — 1969. — Т. 185. — С. 975—976.
- Norman Biggs. Combinatorial Mathematics and its Applications (Proc. Conf., Oxford, 1969). — London: Academic Press, 1971. — С. 15—23.
- Norman Biggs. Finite Groups of Automorphisms. — London & New York: Cambridge University Press, 1971. — Т. 6. — (London Mathematical Society Lecture Note Series).
- N. L. Biggs, D. H. Smith. On trivalent graphs // Bulletin of the London Mathematical Society. — 1971. — Т. 3, вып. 2. — С. 155—158. — DOI:10.1112/blms/3.2.155.
- D. H. Smith. Primitive and imprimitive graphs // The Quarterly Journal of Mathematics. Oxford. Second Series. — 1971. — Т. 22, вып. 4. — С. 551—557. — DOI:10.1093/qmath/22.4.551.
- Обзоры
- N. L. Biggs. Глава 20 Distance-Transitive Graphs // Algebraic Graph Theory. — 2nd. — Cambridge University Press, 1993. — С. 155–163.
- John Van Bon. Finite primitive distance-transitive graphs // European Journal of Combinatorics. — 2007. — Т. 28, вып. 2. — С. 517—532. — DOI:10.1016/j.ejc.2005.04.014..
- A. E. Brouwer, A. M. Cohen, A. Neumaier. Глава 7 Distance-Transitive Graphs // Distance-Regular Graphs. — New York: Springer-Verlag, 1989. — С. 214—234.
- A. M. Cohen Cohen. Topics in Algebraic Graph Theory / L. W. Beineke, R. J. Wilson. — Cambridge University Press, 2004. — Т. 102. — С. 222—249. — (Encyclopedia of Mathematics and its Applications).
- C. Godsil, G. Royle. Глава Distance-Transitive Graphs, секция 4.5. // Algebraic Graph Theory. — New York: Springer-Verlag, 2001. — С. 66—69.
- A. A. Ivanov. The Algebraic Theory of Combinatorial Objects / I. A. Faradžev, A. A. Ivanov, M. Klin, A. J. Woldar. — Dordrecht: Kluwer, 1992. — Т. 84. — С. 283—378. — (Math. Appl. (Soviet Series))..
Ссылки
- Weisstein, Eric W. Distance-Transitive Graph (англ.) на сайте Wolfram MathWorld.
 | Для улучшения этой статьи желательно: |
Данная страница на сайте WikiSort.ru содержит текст со страницы сайта "Википедия".
Если Вы хотите её отредактировать, то можете сделать это на странице редактирования в Википедии.
Если сделанные Вами правки не будут кем-нибудь удалены, то через несколько дней они появятся на сайте WikiSort.ru .