Premium
Overlap in consistent cycles
Author(s) -
Miklavič Štefko,
Potočnik Primož,
Wilson Steve
Publication year - 2007
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.20224
Subject(s) - mathematics , combinatorics , generalization , automorphism , graph , transitive relation , automorphism group , simple (philosophy) , rotation (mathematics) , discrete mathematics , geometry , mathematical analysis , philosophy , epistemology
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