Consistent Cycles in Graphs and Digraphs

Let Γ be a finite digraph and let G be a subgroup of the automorphism group of Γ. A directed cycle of Γ is called G-consistent whenever there is an element of G whose restriction to is the 1-step rotation of . Consistent cycles in finite arc-transitive graphs were introduced by J. H. Conway in his public lectures at the Second British Combinatorial Conference in 1971. He observed that the number of G-orbits of G-consistent cycles of an arc-transitive group G is precisely one less than the valency of the graph. In this paper, we give a detailed proof of this result in a more general setting of arbitrary groups of automorphisms of graphs and digraphs.

Authors and Affiliations

1. Institute of Mathematics, Physics and Mechanics, and Faculty of Education, University of Primorska, Cankarjeva 5, SI-6000, Koper, Slovenia

   Štefko Miklavič

2. Institute of Mathematics, Physics and Mechanics, and Faculty of Mathematics and Physics, University of Ljubljana, Jadranska 19, SI-1000, Ljubljana, Slovenia

   Primož Potočnik

3. Department of Mathematics and Statistics, Northern Arizona University, Box 5717, Flagstaff, AZ, 86011, USA

   Steve Wilson

Corresponding author

Correspondence to Štefko Miklavič.

Supported in part by ``Ministrstvo za šolstvo, znanost in šport Republike Slovenije'', bilateral project BI-USA/04-05/38.

Reprints and permissions