Overlap in consistent cycles |
| |
Authors: | Štefko Miklavič Primož Potočnik Steve Wilson |
| |
Institution: | 1. Faculty of Education, University of Primorska, Cankarjeva 5, SI‐6000 Koper, Slovenia;2. Institute of Mathematics, Physics and Mechanics, Jadranska 19, SI‐1000 Ljubljana, Slovenia;3. Faculty of Mathematics and Physics, University of Ljubljana, Jadranska 19, SI‐1000 Ljubljana, Slovenia;4. Department of Mathematics and Statistics, Northern Arizona University, Box 5717, Flagstaff, Arizona 86011, USA |
| |
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 ‐consistent. We investigate ‐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 ‐consistent cycles. A set of illuminating examples are provided. © 2007 Wiley Periodicals, Inc. J Graph Theory 55: 55–71, 2007 |
| |
Keywords: | graph automorphism group symmetry consistent cycle |
|
|