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

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

f:V(G)\to V(G)\

такой, что

f(v_{1})=v_{2}.\

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

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

Конечные примеры [ править ]

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

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

Свойства [ править ]

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

Бесконечные примеры [ править ]

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

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

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

См. также [ править ]

Ссылки [ править ]

^ Перейти обратно: ^а ^б Годсил, Крис ; Ройл, Гордон (2013) [2001], Алгебраическая теория графов , Тексты для выпускников по математике , том. 207, Спрингер, ISBN 978-1-4613-0163-9 .
^ Поточник П., Спига П. и Веррет Г. (2013), «Кубические вершинно-транзитивные графы с числом вершин до 1280», Журнал символических вычислений , 50 : 465–477, arXiv : 1201.5317 , doi : 10.1016/j.jsc .2012.09.002 , S2CID 26705221 .
^ Лаури, Йозеф; Скапеллато, Раффаэле (2003), Темы автоморфизмов и реконструкции графов , Студенческие тексты Лондонского математического общества, том. 54, Издательство Кембриджского университета, стр. 54. 44, ISBN 0-521-82151-7 , МР 1971819 . Лаури и Скапеллето приписывают это строительство Марку Уоткинсу.
^ Бабай, Л. (1996), Технический отчет TR-94-10 , Чикагский университет, заархивировано из оригинала 11 июня 2010 г.
^ Дистель, Рейнхард; Лидер, Имре (2001), «Гипотеза о пределе графов, отличных от Кэли» (PDF) , Journal of Algebraic Combinatorics , 14 (1): 17–25, doi : 10.1023/A:1011257718029 , S2CID 10927964 .
^ Эскин, Алекс; Фишер, Дэвид; Уайт, Кевин (2005). «Квазиизометрии и жесткость разрешимых групп». arXiv : math.GR/0511647 . .

Внешние ссылки [ править ]

Вайсштейн, Эрик В. «Вершинно-транзитивный граф» . Математический мир .
Перепись малых связных кубических вершинно-транзитивных графов . Примож Поточник, Пабло Спига, Габриэль Веррет, 2012.
Вершинно-транзитивные графы с числом вершин менее 48 . Гордон Ройл и Дерек Холт, 2020 год.

[Godsil01-1] Перейти обратно: ^а ^б Годсил, Крис ; Ройл, Гордон (2013) [2001], Алгебраическая теория графов , Тексты для выпускников по математике , том. 207, Спрингер, ISBN 978-1-4613-0163-9 .

[2] Поточник П., Спига П. и Веррет Г. (2013), «Кубические вершинно-транзитивные графы с числом вершин до 1280», Журнал символических вычислений , 50 : 465–477, arXiv : 1201.5317 , doi : 10.1016/j.jsc .2012.09.002 , S2CID 26705221 .

[3] Лаури, Йозеф; Скапеллато, Раффаэле (2003), Темы автоморфизмов и реконструкции графов , Студенческие тексты Лондонского математического общества, том. 54, Издательство Кембриджского университета, стр. 54. 44, ISBN 0-521-82151-7 , МР 1971819 . Лаури и Скапеллето приписывают это строительство Марку Уоткинсу.

[4] Бабай, Л. (1996), Технический отчет TR-94-10 , Чикагский университет, заархивировано из оригинала 11 июня 2010 г.

[5] Дистель, Рейнхард; Лидер, Имре (2001), «Гипотеза о пределе графов, отличных от Кэли» (PDF) , Journal of Algebraic Combinatorics , 14 (1): 17–25, doi : 10.1023/A:1011257718029 , S2CID 10927964 .

[6] Эскин, Алекс; Фишер, Дэвид; Уайт, Кевин (2005). «Квазиизометрии и жесткость разрешимых групп». arXiv : math.GR/0511647 . .

[1]

[2]

[3]

[4]

[5]

[6]

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