Abstract
A (directed) cycle C in a graph Γ is called consistent provided there exists an automorphism of Γ, acting as a 1-step rotation of C. A beautiful but not well-known result of J.H. Conway states that if Γ is arc-transitive and has valence d, then there are precisely d - 1 orbits of consistent cycles under the action of Aut(Γ). In this paper, we extend the definition of consistent cycles to those which admit a k-step rotation, and call them 1/k-consistent. We investigate 1/k-consistent cycles in view of their overlap. This provides a simple proof of the original Conway's theorem, as well as a generalization to orbits of 1/k-consistent cycles. A set of illuminating examples are provided.
Original language | English (US) |
---|---|
Pages (from-to) | 55-71 |
Number of pages | 17 |
Journal | Journal of Graph Theory |
Volume | 55 |
Issue number | 1 |
DOIs | |
State | Published - May 2007 |
Keywords
- Automorphism group
- Consistent cycle
- Graph
- Symmetry
ASJC Scopus subject areas
- Geometry and Topology