Полутранзитивный граф — это граф, который и вершинно-транзитивен, и рёберно-транзитивен, но не симметричен[1]. Другими словами, граф полутранзитивен, если его группа автоморфизмов действует транзитивно как на вершины, так и на рёбра, но не на упорядоченные пары связанных вершин.
Любой связный симметричный граф должен быть вершинно-транзитивен и рёберно-транзитивен. Обратное верно для графов нечётной степени[2], так что полутранзитивные графы нечётной степени не существуют. Однако существуют транзитивные графы чётной степени[3]. Наименьшим полутранзитивным графом является граф Холта степени 4 с 27 вершинами[4][5].
Примечания
- ↑ Gross, Yellen, 2004, с. 491.
- ↑ Babai, 1996.
- ↑ Bouwer, 1970, с. 231—237.
- ↑ Biggs, 1993.
- ↑ 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.
 | Для улучшения этой статьи желательно: |
Данная страница на сайте WikiSort.ru содержит текст со страницы сайта "Википедия".
Если Вы хотите её отредактировать, то можете сделать это на странице редактирования в Википедии.
Если сделанные Вами правки не будут кем-нибудь удалены, то через несколько дней они появятся на сайте WikiSort.ru .