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

${\displaystyle f:V(G)\rightarrow V(G)\ }$

такой, что

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

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

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

Примеры конечных графов

Множество конечных вершинно-транзитивных графов включает симметричные графы (такие как граф Петерсена , граф Хивуда и вершины и рёбра правильных многогранников ). Конечные графы Кэли (такие как ) являются вершинно-транзитивными, как и вершины и рёбра архимедова тела (хотя только 2 из них симметричны). Поточник, Спига и Веррет (Potočnik, Spiga, Verret) создали перепись всех связных кубических (то есть с вершинами степени 3) вершинно-транзитивных графов с числом вершин, не превышающим 1280 .

Свойства

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

Примеры бесконечных графов

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

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

Два счётных вершинно-транзитивных графа называются , если отношение их функций расстояния ограничено снизу и сверху. Хорошо известная гипотеза утверждяет, что любой бесконечный вершинно-транзитивный граф квазиизоморфен графу Кэли . Контрпример был представлен Рейнхардом Дистелем (Reinhard Diestel) и Имре Лидером (Imre Leader) в 2001-м году . В 2005-м году Эскин, Фишер и Вайт (Eskin, Fisher, Whyte) подтвердили верность контрпримера .

См. также

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

Примечания

Ссылки

• . Primož Potočnik, Pablo Spiga, Gabriel Verret, 2012.