Also available at http://amc.imfm.si
ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.)
ARS MATHEMATICA CONTEMPORANEA 6 (2013) 389–392
A note on a conjecture on consistent cycles
Štefko Miklavič ∗
University of Primorska, Andrej Marušič Institute, Muzejski trg 2, 6000 Koper, Slovenia
Received 28 December 2011, accepted 9 July 2012, published online 17 April 2013
Abstract
Let Γ denote a finite digraph and let G be a subgroup of its automorphism group. A
directed cycle ~C of Γ is called G-consistent whenever there is an element of G whose
restriction to ~C is the 1-step rotation of ~C. In this short note we prove a conjecture on
G-consistent directed cycles stated by Steve Wilson.
Keywords: Digraphs, consistent directed cycles.
Math. Subj. Class.: 05C20, 05C38, 05E18
1 Introduction
Let Γ denote a finite digraph (without loops and multiple arcs). By a directed cycle in Γ
we mean a cyclically ordered set ~C = {v0, v1, v2, . . . , vr−1}, r ≥ 3, of pairwise distinct
vertices of Γ such that (vi, vi+1) is an arc of Γ for every i ∈ Zr (the addition being mod
r). Let G be a subgroup of the automorphism group of Γ. Directed cycle ~C is called G-
consistent, if there exists g ∈ G such that vgi = vi+1 for each i ∈ Zr. In this case g is
called a shunt for ~C. Clearly, G acts on the set of G-consistent directed cycles: for h ∈ G,
~Ch = {vh0 , vh1 , vh2 , . . . , vhr−1} is G-consistent with a shunt h−1gh.
Consistent cycles in finite arc-transitive graphs were introduced by J. H. Conway in one
of his public lectures [3]. Since then a number of papers on consistent cycles and their
applications appeared, see [1, 2, 4, 5, 6, 7, 8, 9, 10, 11].
Observe that if (u, v) is an arc of Γ and g ∈ G is such that ug = v, then the orbit of u under
g induces a G-consistent directed cycle {u, v = ug, ug2 , . . .} (provided that ug2 6= u).
Steve Wilson [12] stated the following conjecture on consistent cycles.
∗This work is supported in part by “Agencija za raziskovalno dejavnost Republike Slovenije”, research pro-
gram P1-0285 and research project J1-4010.
E-mail address: stefko.miklavic@upr.si (Štefko Miklavič)
Copyright c© 2013 DMFA Slovenije
390 Ars Math. Contemp. 6 (2013) 389–392
Conjecture 1.1. Let Γ denote a finite digraph (without loops and multiple arcs) and let
G be an arc-transitive subgroup of its automorphism group. Pick vertices u, v of Γ, such
that (u, v) is an arc of Γ. For a G-orbit A of G-consistent directed cycles, let BA denote
the set of all automorphisms g ∈ G, such that ug = v, and the orbit of u under g is in A.
Let G(u,v) denote the G-stabilizer of the arc (u, v). Then the number of elements in BA is
independent of A, and is equal to the order of G(u,v).
In this short note we prove the above conjecture.
2 Proof of the conjecture
In this section we prove Conjecture 1.1. We prove Conjecture 1.1 in two steps. In Propo-
sition 2.1 we prove that |G(u,v)| ≤ |BA|, and in Proposition 2.2 we prove that |BA| ≤
|G(u,v)|.
Proposition 2.1. With the notation of Conjecture 1.1, we have |G(u,v)| ≤ |BA|.
Proof. Since G is arc-transitive, there exists a G-consistent directed cycle ~C in A, which
contains the arc (u, v). Let g denote a shunt for ~C. Let G~C denote the pointwise stabiliser
of ~C and let k be the index of G~C in G(u,v). Let g1, . . . , gk be representatives of cosets of
G~C in G(u,v).
Observe that for each 1 ≤ i ≤ k and each h ∈ G~C , the automorphism g
−1
i ghgi sends u to
v. Furthermore, the orbit of u under g−1i ghgi is the directed cycle ~C
gi . Namely, since g is
a shunt for ~C and h ∈ G~C , the image of v
gjgi under g−1i ghgi is v
gj+1gi . Moreover, ~Cgi is
clearly in A. Therefore, g−1i ghgi ∈ BA.
We claim that if either i 6= j or h1 6= h2 (h1, h2 ∈ G~C), then α = g
−1
i gh1gi and
β = g−1j gh2gj are distinct. Indeed, assume first that i 6= j. Note that ~Cgi 6= ~Cgj since gi
and gj are from different cosets of G~C in G(u,v). Moreover, α is a shunt for ~C
gi and β is
a shunt for ~Cgj . Since ~Cgi 6= ~Cgj (and since ~Cgi and ~Cgj have at least the arc (u, v) in
common), it follows that also α 6= β. On the other hand, if i = j and α = β, then h1 = h2.
Therefore, if h1 6= h2 and i = j, then α 6= β. This proves the claim.
It follows that |BA| ≥ k|G~C | = |G(u,v)|.
Proposition 2.2. With the notation of Conjecture 1.1, we have |BA| ≤ |G(u,v)|.
Proof. Let X denote the set of all G-consistent directed cycles in A, containing the arc
(u, v). Clearly, BA is exactly the set of all shunts of directed cycles from X . Since all
directed cycles from X have the arc (u, v) in common, every element of BA is a shunt for
exactly one directed cycle from X . Note also that X is nonempty as G is arc-transitive.
We now define a mapping Ψ from BA to G(u,v) as follows.
Fix ~C ∈ X and a shunt g~C of ~C. For each ~D ∈ X there exists an element of G which
sends ~D to ~C. Pick such an element and denote it by h( ~D). Composing h( ~D) with an
appropriate power of g~C , we could assume that h( ~D) ∈ G(u,v). For each g ∈ BA, let ~D(g)
denote the unique directed cycle in X , for which g is a shunt (see Figure 1). For g ∈ BA
define Ψ(g) = gh( ~D(g))g−1~C and note that Ψ(g) ∈ G(u,v).
We now show that Ψ is an injection. Pick g1, g2 ∈ BA and assume that Ψ(g1) = Ψ(g2).
Let ~D(g1) = {u, v, v1, v2, . . . , vn−1} and ~D(g2) = {u, v, w1, w2, . . . , wn−1}. We first
S. Miklavič: A note on a conjecture on consistent cycles 391
v
g
c
u
g
C   
D = D(g )   
~
   ~   
~   ~   
h
(D
) =
h
(D
(g
))
  
~   
~
   
Figure 1: Directed consistent cycles ~C and ~D.
show that ~D(g1) = ~D(g2). Since Ψ(g1) = g1h( ~D(g1))g−1~C = g2h(
~D(g2))g
−1
~C
= Ψ(g2),
we have g−12 g1 = h( ~D(g2))h( ~D(g1))
−1. This implies that g−12 g1 is in G(u,v). We claim
that vn−i = wn−i for i = 0, 1, . . . n − 1, where vn = wn = u. We prove our claim
using induction on i. Note that our claim is true for i = 0. Assume that our claim is true
for i = 0, 1, . . . , t, where 0 ≤ t ≤ n − 2. Note that h( ~D(g2))h( ~D(g1))−1 fixes the arc
(vn−t, vn−t+1, . . . vn−1, u, v), and therefore also g−12 g1 fixes this arc. But since
vg1n−t−1 = vn−t = v
g−12 g1
n−t = w
g1
n−t−1,
we have vn−t−1 = wn−t−1, verifying the claim. It follows that ~D(g1) = ~D(g2). But since
~D(g1) = ~D(g2), also h( ~D(g1)) = h( ~D(g2)). As g1h( ~D(g1))g−1~C = g2h(
~D(g2))g
−1
~C
, it
follows that g1 = g2. Therefore Ψ is an injection and so |BA| ≤ |G(u,v)|.
Corollary 2.3. With the notation of Conjecture 1.1, we have |BA| = |G(u,v)|.
Proof. Immediately from Propositions 2.1 and 2.2.
References
[1] M. Boben, Š. Miklavič and P. Potočnik, Consistent cycles in half-arc-transitive graphs, Elec-
tron. J. Combin. 16 (2009), R5.
[2] M. Boben, Š. Miklavič and P. Potočnik, Rotary polygons in configurations, Electron. J. Combin.
18 (2011), P119.
[3] J. H. Conway, Talk given at the Second British Combinatorial Conference at Royal Holloway
College, Egham, 1971.
[4] H. H. Glover, K. Kutnar, A. Malnič and D. Marušič, Hamilton cycles in (2,odd,3)-Cayley
graphs, J. London Math. Soc. 104 (2012), 1171–1197.
392 Ars Math. Contemp. 6 (2013) 389–392
[5] H. H. Glover, K. Kutnar and D. Marušič, Hamiltonian cycles in cubic Cayley graphs: the
〈2, 4k, 3〉 case, J. Algebraic Combin. 30 (2009), 447–475.
[6] W. M. Kantor, Cycles in graphs and groups, Amer. Math. Monthly 115 (2008), 559–562.
[7] I. Kovács, K. Kutnar and J. Ruff, Rose window graphs underlying rotary maps, Discrete Math.
310 (2010), 1802–1811.
[8] I. Kovács, K. Kutnar and D. Marušič, Classification of edge-transitive rose window graphs, J.
Graph Theory 65 (2010), 216–231.
[9] K. Kutnar and D. Marušič, A complete clasification of cubic symmetric graphs of girth 6,
J. Combin. Theory Ser. B 99 (2009), 162–184.
[10] Š. Miklavič, P. Potočnik and S. Wilson, Consistent cycles in graphs and digraphs, Graphs
Combin. 23 (2007), 205–216.
[11] Š. Miklavič, P. Potočnik and S. Wilson, Overlap in consistent cycles, J. Graph Theory 55
(2007), 55–71.
[12] S. Wilson, Personal communication (2009).