Симметричный граф (или транзитивный относительно дуг граф ) — граф G , для любых двух пар смежных вершин которого u ₁ — v ₁ и u ₂ — v ₂ имеется автоморфизм :

f : V ( G ) → V ( G )

такой, что:

f ( u ₁ ) = u ₂ and f ( v ₁ ) = v ₂ .

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

По определению симметричные графы без изолированных вершин должны быть также вершинно-транзитивными . Поскольку по определению выше рёбра можно перевести из одного в другое, симметричные графы должны быть также рёберно-транзитивными . Однако рёберно-транзитивный граф не обязательно симметричен, поскольку a — b может быть переведён в c — d , но не в d — c . Полусимметричные графы , например, являются рёберно-транзитивными и регулярными , но не вершинно-транзитивными.

Любой связный симметричный граф должен быть как вершинно-транзитивен, так и рёберно-транзитивен, и обратное верно для графов нечётной степени. Однако для чётных степеней существуют связные одновременно вершинно-транзитивные и рёберно-транзитивные графы, но не симметричные. Такие графы называются полутранзитивными . Наименьший связный полутранзитивный граф — это граф Холта , имеющий степень 4 и 27 вершин. Запутывает то, что некоторые авторы используют термин «симметричный граф» для графов, которые одновременно являются вершинно-транзитивными и рёберно-транзитивными. Такое определение включает полутранзитивные графы, которые исключены определением выше.

Дистанционно-транзитивный граф — это граф, в котором вместо единичного расстояния смежные вершины находятся на одном и том же фиксированном расстоянии. Такие графы по определению симметричны.

t -дуга определяется как последовательность t +1 вершин, таких, что любые две последовательные вершины смежны, и повторение вершин может произойти не раньше, чем через 2 шага. Граф называется t -транзитивным , если группа автоморфизмов действует транзитивно на t -дуги, но не на ( t +1)-дуги. Поскольку 1-дуги — это просто рёбра, любой симметричный граф степени 3 и более должен быть t -транзитивным для некоторого t , и значение t можно использовать для классификации графов. Куб является 2-транзитивным, например.

Примеры

Сочетание условий симметрии с условием, что граф кубический (то есть все вершины имеют степень 3), порождает достаточно сильное условие, чтобы все такие графы были достаточно редки и их можно было бы перечислить. Список Фостера и его расширения дают такие списки. Список Фостера был начат в 1930-х годах Рональдом Фостером во время его работы в Bell Labs , и в 1988 (когда Фостеру было 92 ) список Фостера (список всех симметричных кубических графов вплоть до 512 вершин, известных на тот момент) был опубликован в виде книги. Первые тринадцать элементов списка — кубические симметричные графы, имеющие до 30 вершин (десять из них — дистанционно-транзитивные ), приведены ниже в таблице

Другие хорошо известные симметричные кубические графы — это граф Дика , граф Фостера и граф Биггса — Смита . Десять дистанционно-транзитивных графов перечислены выше. Вместе с графом Фостера и графом Биггса — Смита это единственные дистанционно-транзитивные графы.

Некубические симметричные графы включают циклы (степени 2), полные графы (степени 4 и выше с 5 и более вершинами), графы гиперкубов (степени 4 и выше с 16 и более вершинами) и графы, образованные вершинами и рёбрами октаэдра , икосаэдра , кубооктаэдра и икосододекаэдра . Граф Радо даёт пример симметричного графа с бесконечным числом вершин и бесконечной степенью.

Свойства

Вершинная связность симметричного графа всегда равна степени d . Для контраста, для общих вершинно-транзитивных графов вершинная связность ограничена снизу числом 2( d +1)/3.

t -транзитивный граф степени 3 и выше имеет обхват по меньшей мере 2( t -1). Однако не существует конечных t -транзитивных графов степени 3 и выше для t ≥ 8. В случае степени, в точности равной трём (кубические симметричные графы), нет графов для t ≥ 6.

См. также

• Алгебраическая теория графов
• Правильная карта

Примечания

Ссылки

• . Data files for all cubic symmetric graphs up to 768 vertices, and some cubic graphs with up to 1000 vertices. Gordon Royle, updated February 2001, retrieved 2009-04-18.
• . , August 2006, retrieved 2009-08-20.