Overlap in consistent cycles
Štefko Miklavič, Primož Potočnik, Steve Wilson · Journal of Graph Theory · 2007
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}\over{k}$ ‐consistent. We investigate ${1}\over{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}\over{k}$ ‐consistent cycles. A set of illuminating examples are provided. © 2007 Wiley Periodicals, Inc. J Graph Theory 55: 55–71, 2007