Полутранзитивный граф (Hklrmjgu[nmnfudw ijgs)

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

Полутранзитивный граф — это граф, который и вершинно-транзитивен, и рёберно-транзитивен, но не симметричен[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.
Источник — https://ru.wikipedia.org/w/index.php?title=Полутранзитивный_граф&oldid=139201355