Полутранзитивный граф

Граф Холта является наименьшим полутранзитивным графом. Недостаточность зеркальной симметрии на этом рисунке отражает факт, что рёбра не эквивалентны их симметричным.

Полутранзитивный граф — это граф, который и вершинно-транзитивен, и рёберно-транзитивен, но не симметричен. Другими словами, граф полутранзитивен, если его группа автоморфизмов действует транзитивно как на вершины, так и на рёбра, но не на упорядоченные пары связанных вершин.

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

Литература

• Gross J.L. Yellen J. Handbook of Graph Theory. — CRC Press, 2004. — ISBN 1-58488-090-2.
• Babai L. Automorphism groups, isomorphism, reconstruction // Handbook of Combinatorics / Graham R., Grötschel M., Lovász L. — Elsevier, 1996.
• Norman Biggs. Algebraic Graph Theory. — 2nd. — Cambridge: Cambridge University Press, 1993. — ISBN 0-521-45897-8.
• Derek F. Holt. A graph which is edge transitive but not arc transitive // Journal of Graph Theory. — 1981. — Т. 5, вып. 2. — doi:10.1002/jgt.3190050210.
• Bouwer Z. Vertex and Edge Transitive, But Not 1-Transitive Graphs // Canad. Math. Bull.. — 1970. — Т. 13.