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

В теорії графів, граф G є симетричним (або дуго-транзитивним) якщо, для будь-яких пар суміжних вершин u₁—v₁ і u₂—v₂ графу G, існує автоморфізм

f : V(G) → V(G)

Граф Петерсена — (кубічний) симетричний граф. Будь-яка пара суміжних вершин може бути відображена на іншу через автоморфізм, бо будь-яке 5-вершинне кільце може бути відображене в будь-яке інше

такий, що

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

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

За визначенням (ігноруючи u₁ і u₂), симетричний граф без ізольованих вершин має також бути вершинно-транзитивним.[1] Завдяки визначенню через відображення одного ребра на інше, симетричний граф має також бути реберно-транзитивним. Однак, реберно-транзитивний граф не має бути симетричним, бо a—b можуть відбиватись в c—d, але не в d—c. Наприклад, напівсиметричний граф є реберно-транзитивним і регулярним, але не вершинно-транзитивним.

Види графів за їхніми автоморфізмами
відстанево-транзитивний	${\displaystyle \rightarrow }$	відстанево-регулярний	${\displaystyle \leftarrow }$	сильно регулярний
${\displaystyle \downarrow }$
симетричний (дуго-транзитивний)	${\displaystyle \leftarrow }$	t-транзитивний, t ≥ 2
${\displaystyle \downarrow }$(якщо зв'язний)
вершинно- та реберно-транзитивний	${\displaystyle \rightarrow }$	реберно-транзитивний і регулярний	${\displaystyle \rightarrow }$	реберно-транзитивний
${\displaystyle \downarrow }$		${\displaystyle \downarrow }$
вершинно-транзитивний	${\displaystyle \rightarrow }$	регулярний
${\displaystyle \uparrow }$
граф Келі		кососиметричний		асиметричний

Таким чином, кожний зв'язний симетричний граф має бути і вершинно-транзитивним, і реберно-транзитивним, зворотне твердження теж правильне для графів непарних степенів.[3] Однак, для парних степенів, існують зв'язні вершинно-транзитивні і реберно-транзитивні, але не симетричні графи.[4] Такі графи називаються напівтранзитивними.[5] Найменший зв'язний напівтранзитивний граф це граф Хольта, зі степенем 4 і 27 вершинами.[1][6] Деякі автори використовують термін «симетричний граф» для позначення графів, що вершинно-транзитивні і реберно-транзитивні, радше ніж дуго-транзитивні. Таке визначення охоплює напівтранзитивні графи, які виключені визначенням поданим вище.

У відстанево-транзитивного графу замість розглядання пар суміжних вершин (тобто вершин на відстані 1), визначення розглядає дві пари вершин, кожна з однаковою відстанню між вершинами. Такий граф автоматично симетричний за визначенням.[1]

Визначимо t-дугу як послідовність з t+1 вершин таких, що будь-які дві послідовні вершини суміжні, з допустимою відстанню між вершинами, що повторюються, більшою за два кроки. T-транзитивний граф це такий граф, що група автоморфізмів діє транзитивно на t-дугах, але не на (t+1)-дугах. Через те, що 1-дуги це просто ребра, кожний симетричний граф степені 3 або більше має бути t-транзитивний для деякого t, і значення t можна використати для подальшої класифікації симетричних графів. Куб є 2-транзитивним, наприклад.[1]