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

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

В математической области теории графов , А вершина-симметрический граф является граф G , в которой, учитывая любые две вершины v ₁ и v ₂ из G , есть некоторый автоморфизм

{\ Displaystyle е \ двоеточие G \ в G \}

такой, что

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Реберно-транзитивный граф
Гипотеза Ловаса
Полусимметричный граф
Нулевой симметричный граф

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

^ Годсил, Крис ; Ройл, Гордон (2001), алгебраическая теория графов , Graduate Texts in Mathematics , 207 , New York: Springer-Verlag.
^ Поточник П., Спига П. и Веррет Г. (2013), «Кубические вершинно-транзитивные графы с числом вершин до 1280», Журнал символьных вычислений , 50 : 465–477, arXiv : 1201.5317 , doi : 10.1016 / j. jsc.2012.09.002.
^ Лаури, Йозеф; Скапеллато, Раффаэле (2003), Темы автоморфизмов и реконструкции графов , Студенческие тексты Лондонского математического общества, 54 , Кембридж: Издательство Кембриджского университета, стр. 44, ISBN 0-521-82151-7, MR 1971819. Лаури и Скапеллето приписывают эту постройку Марку Уоткинсу.
^ Godsil, С. & Royle, Г. (2001), Алгебраическая Теория графов , Springer Verlag
^ Бабай, Л. (1996), Технический отчет TR-94-10 , Чикагский университет[1] Архивировано 11 июня 2010 г. в Wayback Machine.
^ Дистель, Рейнхард; Лидер Имре (2001), "Гипотеза относительно предела графов без октав" (PDF) , журнал Алгебраической комбинаторики , 14 (1): 17-25, DOI : 10,1023 / A: 1011257718029 .
^ Эскин, Алекс; Фишер, Дэвид; Уайт, Кевин (2005). «Квазиизометрии и жесткость разрешимых групп». arXiv : math.GR/0511647 ..

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

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

[1] Годсил, Крис ; Ройл, Гордон (2001), алгебраическая теория графов , Graduate Texts in Mathematics , 207 , New York: Springer-Verlag.

[2] Поточник П., Спига П. и Веррет Г. (2013), «Кубические вершинно-транзитивные графы с числом вершин до 1280», Журнал символьных вычислений , 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] Godsil, С. & Royle, Г. (2001), Алгебраическая Теория графов , Springer Verlag

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

[6] Дистель, Рейнхард; Лидер Имре (2001), "Гипотеза относительно предела графов без октав" (PDF) , журнал Алгебраической комбинаторики , 14 (1): 17-25, DOI : 10,1023 / A: 1011257718029 .

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

[1]