Симметричный граф

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

f : V(G) → V(G)

Граф Петерсена является (кубическим) симметричным графом. Любую пару смежных вершин можно перевести в другую пару автоморфизмом, поскольку любое кольцо из пяти вершин можно перевести в любое такое же.

такой, что:

f(u₁) = u₂ and f(v₁) = v₂.^[1]

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

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

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

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

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

Примеры

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

Вершины	Диаметр	Обхват	Граф	Примечания
4	1	3	полный граф K4	дистанционно транзитивен, 2-транзитивен
6	2	4	полный двудольный граф K3,3	дистанционно транзитивен, 3-транзитивен
8	3	4	вершины и рёбра куба	дистанционно транзитивен, 2-транзитивен
10	2	5	граф Петерсена	дистанционно транзитивен, 3-транзитивен
14	3	6	граф Хивуда	дистанционно транзитивен, 4-транзитивен
16	4	6	граф Мёбиуса — Кантора	2-транзитивен
18	4	6	граф Паппа	дистанционно транзитивен, 3-транзитивен
20	5	5	вершины и рёбра додекаэдра	дистанционно транзитивен, 2-транзитивен
20	5	6	граф Дезарга	дистанционно транзитивен, 3-транзитивен
24	4	6	граф Науру (обобщённый граф Петерсена G(12,5))	2-транзитивен
26	5	6	граф F26A[11]	1-транзитивен
28	4	7	граф Коксетера	дистанционно транзитивен, 3-транзитивен
30	4	8	граф Татта — Коксетера	дистанционно транзитивен, 5-транзитивен

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

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

Свойства

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

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

См. также

• Алгебраическая теория графов
• Галерея именованных графов^[англ.]
• Правильная карта