Вершинно-транзитивный граф

Семейства графов, определяемые их автоморфизмами
дистанционно-транзитивными	→	дистанционно-регулярными	←	сильно регулярными
↓
симметричными (дугово-транзитивными)	←	t-транзитивными, t ≥ 2		кососимметричный
↓
(если подключен). вершинно-транзитивный и реберный	→	реберный транзитивный и правильный	→	реберный транзитивный
↓		↓		↓
вершинно-транзитивный	→	правильный	→	(если двудольный). бирегулярный
↑
граф Кэли	←	нулевой симметричный		асимметричный

В математическом поле теории графов, вершинно-транзитивный граф - это граф G, в котором для любых двух вершин v 1 и v 2 графа G существует некоторый автоморфизм

$f:\; G\; \to \; G\; \{\backslash \; displaystyle\; f\; \backslash \; двоеточие\; G\; \backslash \; to\; G\; \backslash \}$

, такое, что

$f\; (v\; 1)\; =\; v\; 2.\; \{\backslash \; displaystyle\; f\; (v\_\; \{1\})\; =\; v\_\; \{2\}.\; \backslash \}$

Другими словами, граф является вершинно-транзитивным, если его группа автоморфизмов действует транзитивно на его вершины. Граф является вершинно-транзитивным тогда и только тогда, когда имеет его дополнение к графу, поскольку действия группы идентичны.

Каждый симметричный граф без изолированных вершин является вершинно-транзитивным, а каждый вершинно-транзитивный граф регулярным. Однако не все вершинно-транзитивные графы являются симметричными (например, ребра усеченного тетраэдра ), и не все регулярные графы являются вершинно-транзитивными (например, граф Фрухта и график Титце ).

• 1 Конечные примеры
• 2 Свойства
• 3 Бесконечные примеры
• 4 См. Также
• 5 Ссылки
• 6 Внешние ссылки

Края усеченный тетраэдр формирует вершинно-транзитивный граф (также граф Кэли ), который не является симметричным.

Конечные вершинно-транзитивные графы включают в себя симметричные графы (например, граф Петерсена, граф Хивуда, а также вершины и ребра Платоновых тел ). Конечные графы Кэли (такие как кубически связанные циклы ) также являются вершинно-транзитивными, как и вершины и ребра архимедовых тел (хотя только два из них симметричны). Поточник, Спига и Веррет построили перепись всех связных кубических вершинно-транзитивных графов не более чем на 1280 вершинах.

Хотя каждый граф Кэли является вершинно-транзитивным, существуют другие вершинно-транзитивные графы, которые не являются графами Кэли.. Самый известный пример - граф Петерсена, но могут быть построены и другие, включая линейные графы из реберно-транзитивных не двудольных графов с нечетными степенями вершин.

связность ребер вершинно-транзитивного графа равна степени d, в то время как связность вершин будет не менее 2 (d + 1) / 3. Если степень равна 4 или меньше, или граф также является реберно-транзитивным, или граф является минимальным графом Кэли, то связность вершин также будет равна d.

Бесконечные вершинно-транзитивные графы включают:

• бесконечные пути (бесконечные в обоих направлениях)
• бесконечные обычные деревья, например граф Кэли из свободной группы
• графы однородных мозаик (см. полный список плоских мозаик ), включая все мозаики правильными многоугольниками
• бесконечными графами Кэли
• графом Радо

Два счетных вершинно-транзитивных графа называются квази- isometric, если отношение их функций расстояния ограничено снизу и сверху. Хорошо известная гипотеза гласит, что любой бесконечный вершинно-транзитивный граф квазиизометричен графу Кэли. Контрпример был предложен Дистелом и Лидером в 2001 году. В 2005 году Эскин, Фишер и Уайт подтвердили контрпример.

• Edge-transitive граф
• гипотеза Ловаса
• Полусимметричный граф
• Нулевой симметричный граф

1. ^Годсил, Крис ; Ройл, Гордон (2001), Алгебраическая теория графов, Тексты для выпускников по математике, 207, Нью-Йорк: Springer-Verlag.
2. ^Поточник П., Спига П. и Веррет Г. (2013), «Кубические вершинно-транзитивные графы с числом вершин до 1280», Journal of Symbolic Computing, 50 : 465–477, arXiv : 1201.5317, doi : 10.1016 / j.jsc.2012.09.002.
3. ^Лаури, Йозеф; Скапеллато, Раффаэле (2003), Темы автоморфизмов и реконструкции графов, Тексты студентов Лондонского математического общества, 54, Кембридж: Издательство Кембриджского университета, стр. 44, ISBN 0-521-82151-7, MR 1971819. Лаури и Скапеллето приписывают эту постройку Марку Уоткинсу.
4. ^Годсил, К. и Ройл, Г. (2001), теория алгебраических графов, Springer Verlag
5. ^Бабай, Л. (1996), технический отчет TR-94-10, Чикагский университет [1] Архивировано 11.06.2010 на Wayback Machine
6. ^Diestel, Reinhard; Лидер, Имре (2001), «Гипотеза о пределе графов, отличных от Кэли» (PDF), Журнал алгебраической комбинаторики, 14 (1) : 17–25, doi : 10.1023 / A: 1011257718029.
7. ^Эскин, Алекс; Фишер, Дэвид; Уайт, Кевин (2005). «Квазиизометрии и жесткость разрешимых групп». arXiv : math.GR/0511647..

• Вайсштейн, Эрик У. «Вершинно-транзитивный граф». MathWorld.
• Перепись небольших связных кубических вершинно-транзитивных графов. Примож Поточник, Пабло Спига, Габриэль Верре, 2012.