Русская Википедия:Вершинно-транзитивный граф
В теории графов вершинно-транзитивным графом называется граф G такой, что для любых двух вершин v1 и v2 графа G существует автоморфизм
- <math>f:V(G) \rightarrow V(G)\ </math>
такой, что
- <math>f(v_1) = v_2.\ </math>
Другими словами, граф вершинно-транзитивен, если его группа автоморфизма действует транзитивно относительно вершин[1]. Граф вершинно-транзитивен тогда и только тогда, когда результаты автоморфизмов его дополнения идентичны.
Любой симметричный граф без изолированных вершин является вершинно-транзитивным, и любой вершинно-транзитивный граф является регулярным. Однако не все вершинно-транзитивные графы симметричны (например, рёбра усечённого тетраэдра), и не все регулярные графы вершинно-транзитивны (например, граф Фрухта и граф Титце).
Примеры конечных графов
Множество конечных вершинно-транзитивных графов включает симметричные графы (такие как граф Петерсена, граф Хивуда и вершины и рёбра правильных многогранников). Конечные графы Кэли (такие как соединённые в куб циклы) являются вершинно-транзитивными, как и вершины и рёбра архимедова тела (хотя только 2 из них симметричны). Поточник, Спига и Веррет (Potočnik, Spiga, Verret) создали перепись всех связных кубических (то есть с вершинами степени 3) вершинно-транзитивных графов с числом вершин, не превышающим 1280[2].
Свойства
Рёберная связность вершинно-транзитивного графа равна степени d, в то время как вершинная связность будет как минимум 2(d+1)/3[3]. Если степень равна 4 или меньше, или граф также рёберно транзитивен, или граф является минимальным графом Кэли, то вершинная связность будет равна d[4].
Примеры бесконечных графов
Бесконечные вершинно-транзитивные графы включают:
- бесконечные пути (бесконечные в обоих направлениях);
- бесконечные регулярные деревья, то есть графы Кэли свободной группы;
- графы однородных паркетов (см. Шаблон:Не переведено 5 паркетов на плоскости), включая все паркеты из правильных многоугольников;
- бесконечные графы Кэли;
- Граф Радо.
Два счётных вершинно-транзитивных графа называются Шаблон:Не переведено 5, если отношение их функций расстояния ограничено снизу и сверху. Хорошо известная гипотеза утверждяет, что любой бесконечный вершинно-транзитивный граф квазиизоморфен графу Кэли. Контрпример был представлен Рейнхардом Дистелем (Reinhard Diestel) и Имре Лидером (Imre Leader) в 2001-м году[5]. В 2005-м году Эскин, Фишер и Вайт (Eskin, Fisher, Whyte) подтвердили верность контрпримера[6].
См. также
Примечания
Ссылки
- A census of small connected cubic vertex-transitive graphs . Primož Potočnik, Pablo Spiga, Gabriel Verret, 2012.
