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

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

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

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

Примечания
  1. Gross, Yellen, 2004, с. 491.
  2. Babai, 1996.
  3. Bouwer, 1970, с. 231—237.
  4. Biggs, 1993.
  5. Holt, 1981, с. 201–204.

Литература
  • 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.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.