stringtranslate.com

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

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

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

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

Конечные примеры

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

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

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

Характеристики

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

Бесконечные примеры

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

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

Смотрите также

Ссылки

  1. ^ abc Годсил, Крис ; Ройл, Гордон (2013) [2001], Алгебраическая теория графов, Graduate Texts in Mathematics , т. 207, Springer, ISBN 978-1-4613-0163-9.
  2. ^ Potočnik P., Spiga P. & Verret G. (2013), "Кубические вершинно-транзитивные графы с числом вершин до 1280", Journal of Symbolic Computation , 50 : 465–477, arXiv : 1201.5317 , doi : 10.1016/j.jsc.2012.09.002, S2CID  26705221.
  3. ^ Лаури, Йозеф; Скапеллато, Раффаэле (2003), Темы по автоморфизмам графов и реконструкции, Лондонское математическое общество, студенческие тексты, т. 54, Cambridge University Press, стр. 44, ISBN 0-521-82151-7, г-н  1971819. Лаури и Скапеллето приписывают эту конструкцию Марку Уоткинсу.
  4. ^ Бабай, Л. (1996), Технический отчет TR-94-10, Чикагский университет, архивировано из оригинала 2010-06-11
  5. ^ Дистель, Рейнхард; Лидер, Имре (2001), «Гипотеза о пределе не-Кэлиевских графов» (PDF) , Журнал алгебраической комбинаторики , 14 (1): 17–25, doi : 10.1023/A:1011257718029 , S2CID  10927964.
  6. ^ Эскин, Алекс; Фишер, Дэвид; Уайт, Кевин (2005). «Квазиизометрии и жесткость разрешимых групп». arXiv : math.GR/0511647 ..

Внешние ссылки