Interested Article - Дистанционно-транзитивный граф
![](/images/009/186/9186990/1.jpg?rand=74336)
![](https://cdn.wafarin.com/avatars/99df19055813a76fdd16095bb267aa93.gif)
- 2020-02-05
- 1
![](/images/009/186/9186990/1.jpg?rand=61654)
Дистанционно-транзитивный граф ( англ. distance-transitive graph ) — граф , в котором любая упорядоченная пара вершин переводится в любую другую упорядоченную пару вершин с тем же расстоянием между вершинами одним из автоморфизмов графа.
Близким понятием является дистанционно-регулярный граф , однако природа их разная. Если дистанционно-транзитивный граф определяется исходя из симметрии графа через условие автоморфизма, то дистанционно-регулярный граф определяется из условия его комбинаторной регулярности. Каждый дистанционно-транзитивный граф является дистанционно-регулярным, однако обратное не справедливо. Это было доказано в 1969 году, еще до введения в обиход термина «дистанционно-транзитивный граф».
Полностью классифицированы дистанционно-регулярные графы степеней меньших 13.
Определения дистанционно-транзитивного графа
![](/images/009/186/9186990/2.jpg?rand=223519)
![](/images/009/186/9186990/4.jpg?rand=889839)
![](/images/009/186/9186990/5.jpg?rand=453681)
![](/images/009/186/9186990/6.jpg?rand=566499)
![](/images/009/186/9186990/7.jpg?rand=238011)
![](/images/009/186/9186990/8.jpg?rand=231398)
Существует несколько различных по форме, но одинаковых по смыслу определений дистанционно-транзитивного графа. Предполагается, что граф — неориентированный, связанный и ограниченный. В определении используются понятия расстояние между вершинами графа и автоморфизм графа :
- Расстояние между двумя вершинами графа есть количество рёбер по наикратчайшему пути, соединяющему и
- Автоморфизм графа — взаимно однозначное отображение множества вершин графа на себя, сохраняющее смежность вершин.
- Группа автоморфизмов графа — множество автоморфизмов графа.
- Пусть неориентрированный, связный, ограниченный граф обладает группой автоморфизмов . Граф называется дистанционно-транзитивным, если для всех вершин , таких что , существует автоморфизм , который отображает и
- Неориентированный связный конечный граф без петель и кратных ребер называется дистанционно-транзитивным, если его группа автоморфизмов действует транзитивно на упорядоченных парах равноудаленных вершин
- Пусть — связный граф диаметра и — его группа автоморфизмов. дистанционно-транзитивна на , если она транзитивна на каждом множестве , где . Граф является дистанционно-транзитивным, если его группа автоморфизмов является дистанционно-транзитивной на нем.
- Пусть неориентированный, связанный, ограниченный граф обладает группой автоморфизмов . Пусть есть подгруппа . Граф называется -дистанционно-транзитивным ( англ. -distance-transitive ), если для каждой четвёрки вершин , таких что , существует автоморфизм , который отображает и . Дистанционно-транзитивным называется граф, который является -дистанционно-транзитивным для некоторой подгруппы группы автоморфизмов графа.
- Другими словами, есть -дистанционно-транзитивный граф, если подгруппа действует транзитивно на множестве при каждом .
Массив пересечений
Пусть есть неориентированный, связанный, ограниченный граф, а две его вершины находятся на расстоянии друг от друга. Все вершины , инцидентные к вершине , можно разбить на три множества , и в зависимости от их расстояния до вершины :
- , , .
Если граф дистанционно-транзитивный, то мощности (кардинальные числа) множеств не зависят от вершин , а зависят только от расстояния и называются числами пересечений .
Набор чисел пересечений
называется массивом пересечений дистанционно-транзитивного графа .
Свойства
- Каждый дистанционно-транзитивный граф является дистанционно-регулярным , однако обратное не справедливо .
- Дистанционно-транзитивный граф является вершинно-транзитивным и симметричным .
- Массив пересечений дистанционно-регулярного графа степени . Так как дистанционно-транзитивный граф является регулярным, то числа пересечений и . Более того, . Поэтому массив пересечений дистанционно-регулярного графа можно записать как :
Примеры
Простейшие примеры дистанционно-транзитивных графов :
- полные графы
- полные двудольные графы (биклики) с равными долями
- графы гиперкуба
Более сложные примеры дистанционно-транзитивных графов:
- граф Джонсона
- граф Грассмана
- граф Хемминга
- граф Ливингстона
Дистанционно-регулярный и дистанционно-транзитивный графы
На первый взгляд дистанционно-транзитивный граф и дистанционно-регулярный граф являются очень близкими понятиями. Действительно, каждый дистанционно-транзитивный граф является дистанционно-регулярным. Однако их природа разная. Если дистанционно-транзитивный граф определяется исходя из симметрии графа через условие автоморфизма, то дистанционно-регулярный граф определяется из условия его комбинаторной регулярности .
Дистанционно-транзитивный граф является вершинно-транзитивным, и для него определены . Для дистанционно-регулярный графа через комбинаторную регулярность также определены числа пересечений. Из дистанционно-транзитивности графа следует его дистанционно-регулярность, но обратное неверно . Это было доказано в 1969 г., еще до введения в обиход термина «дистанционно-транзитивный граф», группой советских математиков ( Г. М. Адельсон-Вельский , Б. Ю. Вейсфелер , А. А. Леман, И. А. Фараджев) . Наименьший дистанционно-регулярный граф, не являющийся дистанционно-транзитивным, — это граф Шрикханде . Единственный тривалентный граф этого типа — это 12-клетка Татта , граф с 126 вершинами .
Классификация дистанционно-транзитивных графов
Первый общий результат в классификации дистанционно-транзитивных графов был получен в Биггзом и Смитом в 1971 году, где были классифицированы графы степени три. В течение последующих десяти-пятнадцати лет центральной проблемой в изучении дистанционно-транзитивных графов была классификация дистанционно-транзитивных графов малых степеней . Дистанционно-транзитивные графы степени четыре были полностью классифицированы Смитом .
В 1983 году Камерон, Прегер, Саксл и Зайц и независимо в 1985 году Вайс доказали, что для любой степени большей двух существует ограниченное число дистанционно-транзитивных графов .
Классификация кубических дистанционно-транзитивных графов
В 1971 году Н. Биггз и Д. Смит доказали теорему, что среди кубических (тривалентных) графов существует ровно 12 дистанционно-транзитивных графов :
Название графа | Число вершин | Диаметр | Обхват | |
---|---|---|---|---|
Полный граф K 4 | 4 | 1 | 3 | {3;1} |
Полный двудольный граф K 3,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} |
Дистанционно-транзитивные графы степени больше трёх
Все дистанционно-транзитивные графы степени известны . Все дистанционно-транзитивных графы степени (валентности) четыре ( ) были получены Д. Смитом в 1973-74 годах , а пятой, шестой и седьмой степеней в 1984 году А. А. Ивановым, А. В. Ивановым и И. А. Фараджевым .
В 1986 году А. А. Ивановым и А. В. Ивановым были получены все дистанционно-транзитивные графы степеней от до .
Походы к классификации
Списки дистанционно-транзитивных графов малых степеней были получены в рамках подхода, основанном на рассмотрении стабилизатора отдельной вершины и теоремах, ограничивающих диаметр графа. А. А. Иванов назвал этот подход «локальным». «Глобальный» же подход основывается на рассмотрении действия группы автоморфизмов на множестве вершин. Этот подход позволяет классифицировать дистанционно-транзитивные графы, действие группы на которых примитивно. Из них затем конструируют все остальные .
Примечания
- , p. 66.
- , p. 87.
- ↑ , p. 118.
- ↑ , с. 1704.
- ↑ , p. 223.
- , p. 285.
- ↑ , p. 33.
- ↑ , p. 157.
- , p. 34.
- ↑ , p. 136.
- , p. 232.
- , p. 66—67.
- , p. 158.
- , p. 255.
- , p. 269.
- , p. 519.
- , p. 261.
- Weisstein, Eric W. (англ.) на сайте Wolfram MathWorld .
- , p. 159.
- .
- ↑ .
- ↑ , pp. 288—292.
- ↑ .
- ↑ .
- Cameron P. J., Praeger C. E., Saxl J., and Seitz G. M. On the Sims conjecture and distance-transitive graphs // Bull. London Math. Soc. — 1983. — Vol. 15. — P. 499—506.
- Weiss R. On distance-transitive graphs // Bull. London Math. Soc. — 1985. — Vol. 17. — P. 253—256.
- , p. 214.
- , p. 221—225.
- .
- .
Литература
- Книги
- 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 : .
- 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 : .
- Ivanov A. A. (англ.) // Faradžev I. A., Ivanov A. A., Klin M. H., Woldar A. J. (eds.) Investigations in Algebraic Theory of Combinatorial Objects. Mathematics and Its Applications (Soviet Series). — Dordrecht: Springer , 1994. — Vol. 84 . — P. 283—378 . — doi : .
- 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 : .
- Статьи
- Адельсон-Вельский Г. М., Вейсфелер Б. Ю., Леман А. А., Фараджев И. А. // Доклады Академии наук . — 1969. — Т. 185 , № 5 . — С. 975—976 .
- Иванов А. А., Иванов А. В., Фараджев И. А. // Ж. вычисл. матем. и матем. физ . — 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 : .
- 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 : .
Ссылки
- Weisstein, Eric W. (англ.) на сайте Wolfram MathWorld .
![](https://cdn.wafarin.com/avatars/99df19055813a76fdd16095bb267aa93.gif)
- 2020-02-05
- 1