Open Journal of Discrete Mathematics, 2012, 2, 160-163
http://dx.doi.org/10.4236/ojdm.2012.24032 Published Online October 2012 (http://www.SciRP.org/journal/ojdm)
A Note on Hamiltonian Circulant Digraphs of
Outdegr ee Thr ee*
Grant Andruchuk, Shonda Gosselin
Department of Mathematics and Statistics, University of Winnipeg, Winnipeg, Canada
Email: s.gosselin@uwinnipeg.ca, chuker31@hotmail.com
Received August 16, 2012; revised September 3, 2012; accepted September 12, 2012
ABSTRACT
We construct Hamilton cycles in connected loopless circulant digraphs of outdegree three with connection set of the
form for an integer satisfying the condition
,,akab
k
gcd,1 modbaan atkn
 for some integer
such that , where
t
0gcd,ta
n
gcd ,ak
. This extends work of Miklavic and Šparl, who pr eviously deter-
mined the Hamiltonicity of these digraphs in the case where
1k
2k and
, to other values of which depend
on the generators and b. k
a
Keywords: Hamilton Cycle; Circulant Digraph
1. Definitions and Notation
The group of integers under the operation of addition
modulo is denoted by . A subset of is a
generating set for if every element of can be
written as a linear combination of elements in . For
elements of , the symbol
nn
n
Sn
S
n
,
m
a
n
12
,,aa
12
,, m
aa a, denotes the subgroup of generated
by the elements , which is comprised of all
linear combinations of the elements in .
For an element , the set
n
,
m
a
12
,,aa
a
,
m
a
n
12
aa,,n
is
called the left coset of
:bxxa
a in , and is denoted by
n
ba. For two integers , the greatest common
divisor of and is the least positive integer which
divides b oth and b, and is denoted by
,ab
ab
a
gcd ,ab .
A digraph is a pair
,VA in which V is a set of
vertices and
A
is a set of ordered pairs of elements of
called arcs. A directed path of length in a digraph
is a sequence in
which and for ,
and no vertices or arcs in the sequence are repeated
except possibly 0m
v If vv
Vm
2
,v
,DVA
i
v
V011
,,,, ,
mm
vava av
i
vA 1,2,,i
m
2
,
1,
ii
av
v.0
m
then the sequence is
called a directed cycle. A digraph is connected if there is
a directed path from vto wfor any two vertices
and . Two digraphs v
w
1
,A
11
DV and
A
22
,DV
12
V2
are isomorph ic if there is a bijection :V
such
that if and only if . Such

1
,vw A
 

2
,vwA

a mapping
is called an isomorphism from to .
An automorphism of a digraph D is an isomorphism from
D to itself. A digraph D is vertex-transitive if, for any
two vertices v and w of D, there is an automorphism of D
mapping v to w.
1
D2
D
For a subset , the circulant digraph
n
S
;Circn S
v is the digraph with vertex set and arcs
from to n
vs
for all n
v and all
S
. The
set is called the connection set of the digraph S
;Circn S, and the outdegree of Ci is the
cardinality of the connection set S. Clearly, the circulant
digraph
;n S
rc
;rcn SCi is connected if and only if S is a
generating set for . A Hamilton cycle in a digraph
with n vertices is a directed cycle with vertices. A
digraph is said to be Hamiltonian if it has a Hamilton
cycle.
n
n
Each arc in
;Circn S of the form

,vv s
is
labeled
s
. A Hamilton cycle in can be
specified by the sequence of vertices encountered or by
the sequence of arcs traversed. In the latter case, it is
often more convenient to list the labels of the arcs, rather
than the arcs themselves, since for each vertex there is
exactly one out-arc with label s for each

;n SCirc
S
12
. A Ha-
miltonian arc sequence is an ordered sequence n
s
ss
S
of the arc labels encountered in a Hamilton cycle. Since
circulant digraphs are vertex-transitive, any cyclic shift
of a Hamiltonian arc sequence of is also a
Hamiltonian arc sequence of , and traversing
a Hamiltonian arc sequence of starting from
any vertex will yield a Hamilton cycle in
;Circ n

;n S
;n S
Circ
Circ
;Circn S.
For any arc sequence
x
, t
x
denotes the concatenation
*The research of S. Gosselin was supported by a University of Winni-
p
eg Major Research Grant.
C
opyright © 2012 SciRes. OJDM
G. ANDRUCHUK, S. GOSSELIN 161
of copies of t
x
.
2. History and Statement of the Main Result
One long-standing open problem is that of determining
which circulant digraphs are Hamiltonian. Clearly, Ha-
miltonian circulant digraphs must be connected. In 1948,
Rankin [1] determined which connected circulant dig-
raphs of outdegree two are Hamiltonian, and so we need
only consider connected circulant digraphs of outdegree
at least three. There has been some recent work on the
problem of determining when a circulant digraph of out-
degree three is Hamiltonian. In 1999, Locke and Witte [2]
constructed some infinite families of connected non-
Hamiltonian circulant digraphs of outdegree three. In
2009, Witte Morris, Morris and Webb [3] proved that the
circulant digraph is not Hamiltonian if
and only if is a multiple of 6,

;2,3,Circ nc
n
 

c22,23cn n 
and is even. Also in 2009,
Miklavi and Šparl proved the following result.
c
Proposition 2.1. (Miklavic
and Šparl, [4]) For
1k
Circ n or , the circulant digraph
is Hamiltonian if and only if it is
connected, except in the special case where it is
isomorphic to .
2k
,ka b
Circ
;,a


12; 3,6,4
The result of Witte Morris et al in [3] shows that
Miklavi and Šparl’s r esult does not hold for all values
of k. For example, if 12 divide s n then
is not Hamiltonian for
c

;2,3,2Circ nk

4kn1, and if 6 divides
and n
6n is odd then

3,2k;2,Circ n is not Ha-
miltonian for

=61
a

\0k
kn . The following result shows
that Miklavi and Šparl’s result does hold for other
values of which depend on and .
c
k b
Theorem 2.2. Let , let
,, n
ab
gcd ,ka
,
and suppose that
 
gcd,1 modbaan atkn
 (1)
for an integer such that . The cir-
culant digraph is Hamiltonian if and
only if it is connected.
t
Circ

0gcd,ta
,a bn
;,na k
We prove this theorem in the next section, and in
Section 4 we obtain two corollaries to this theorem in the
case where a divides n, which yield two infinite families
of Hamiltonian circulant digraphs of the form
.


;,,Circnaka b
3. Proof of Theorem 2.1
Proof: If is Hamiltonian, then it is
certainly connected.
;,,Circna ka b
Conversely, if is connected, then
;,,Circnaka b
,,akab ab,
n, and so can be partitioned
into the cosets n


, , 2, , gcd,1ababaanba 
of a in ,ab . Let i
C denote the coset ib a
for
0,1,,gcd ,i1an
. We will show that the arc
sequence


 

1
gcd ,11
1t
an tka ka
a
abkaakab




(2)
is a Hamiltonian arc sequence of .


;,,Circnaka b
C
Starting from any vertex i
v and traversing the
arc sequence 1a
a
, we form a walk which visits every
vertex of the coset exactly once. Since
i
C
:gcd,akaak
 
 , the set of distinct cosets of
ka in a are

, , 2, , 1.kaa kaa kaa ka
 
This implies that every vertex of the coset can be
written uniquely in the form , where
i
C
r

vqka
0qka and 0r
, for any fixed vertex in
. Thus, starting from any vertex v in and tra-
v
i
Ci
C
versing the arc sequence
 

11kaka
kaa ka1

, we
visit every vertex of the coset i exactly once. Since
1ii
C
bC C
i
C, traversing arc from any vertex in coset
leads to a vertex of the coset .
b
1i
Hence, starting from any vertex v of
C
;Circn S, say
i
vC
, and traversing arc sequence

gcd ,an t
t
x
by
b,
where
x
denotes the arc sequences 1a
a and de- y
notes the arc sequence
 
1
11kaka
kaa ka

, we form
a walk which visits every vertex of this circulant digraph
exactly once, and then finishes back on a vertex of .
This walk ends back on the starting vertex , and hence
is a Hamilton cycle, if and only if the sum of the arc
labels in the arc sequence (2) is equal to 0. Hence it
remains to show that
i
C
v

 
gcd ,1
11
0mod .
antaa b
tkakaab
n





A straightforward calculation shows that this is equi-
valent to
gcd,1 mod,baan atkn

which ho lds by assumpti o n .
The construction described in the proof of Theorem
2.2 is shown in Figure 1 for the case where 105n
,
7a
, 21
ka
and 25
b
. Here ,
3
k15a
,
15ka
,
gcd
, 3ka
and

,angcd 7
. In this
case condition (1) holds for . The Hamiltonian arc
sequence in (2) for the circulant digraph
3t
105; 7,21,25Circ
4
is

 


3
2
20 4
14 .abka akab



Copyright © 2012 SciRes. OJDM
G. ANDRUCHUK, S. GOSSELIN
162
0
Figure 1. Hamilton cycle in
105; 7,21,25Circ .
th column is 257 mi+j
The vertex
in the ith row and the j f
is shown
Figur ere eachw of vertices represents a coset
f
od105 , or
07i and 0<15j.
The Hamilton cycle given by this arc sequence
e 1, wh roin
o 7 in 105
, and each column of vertices represents
a coset of 25, so the vertex in the ith row and the
jth column of the figure is 257 mod105ij, for
07i an015j . The straight horizontal arcs
have label 7a, the curved horizonarcs have label
21, and the vertical arcs have label 25b.
4. Corollaries
d l a
ka
Note that if , then the assumption in (1) is that
case Theorem 2.2 simply states that
1k
is H
ab, and in this


;Circ na amiltonian if and only if n
a.
For other values of k satisfying condition 1, Theorem
plhat


;,,Circna ka b is Hamiltonian if and
only if

gcd,, ,1akabn (i.e., the digraph is connected).
In the special case where a dides n, we obtain two
corollaries.
Corollary 4.1. If a divides n and
2.2 imies t
vi

gcd,1 1naba , thenthe circulant digraph
Ci
an if and only if
it is connected.
Proof: If a divides n the
have



;, 1,rc nabab is Hmiltoniaa
n

gcd ,an a. For
1
kba
, we


gcd ,gcd,ak nab d so 1 1a, an
.
heorem
2.2 implies the result. des n
 
1gcd,atka ntba

Thus condition (1) holds with 1t,
 
at ba  and so T
Example 4.1. If a is odd, a divi and

gcd,3 1na, then Corollary 4.1plies that
Ci
im
n
4.1 guarantees that


;,3, 2rcnaaa is Hamiltonian, since
1n and so this digraph is con
gcd,3 ,2,aaa
For example, Corollary ected.
35; 5,15,7Circ
kin’s result in [1] im
is hat Ran-
plies t
Hamiltonian. We note t
hat neither
35; 5,7Circ
nor
35; 7,15Circ is Hamiltonian, so all three arc
labels muon any Hamilton cycle in st appear
35; 5,15,7Circ .
Corolla a divides n, k divides ry 4.2. If na and
gcd ,11ak k
, then for any i such that 0in
,
the circulh ant digrap


;,,1rcnakakkakki  is Hilto-
is connected.
Proof: If a divides
1 1Ci am
nian if and only if it and divides
nkna, then
gcd ,an a
and

,kgcd na k
. Thus for
11 1bkkakk i
 and tai, we have
 



 


 
 
g
11 m
11 mod
1 mod
1mod .
akk ak
akka kkin
ak kain
atk n




1od k ian
cd,mod baan aban
Hence condition (1) holds and so the result follows
from Theorem 2.2.
Example 4.2. If divides, 3 divides
a nna,
0ia
and
gcd ,61ai
, then Corollary 4.2 implies
that
;,3,76Circ naaai is Hamiltonian, since
gcd,3,76 ,aaain 1
and s this digraps c
cted. An example of a Hamilton cycle in
oh ion-
ne
105; 7,21,25Circ is shown in Figure 1. Here
7a
and 4i
, so b25
and 3tai.
In conclusion, in Theorem 2.2 we generalized Miklavic
and Šparl’s Proposion 2.1 to include all values
(1), showing that condition (1) is a
ient conn on guaran
itof
that satisfy condition
su
k
fficditio k totee that the circulant
digraph
;,,Circnaka b is Hamiltonian if and only if
it is connected. One interesting open problem is that of
determining conditions on k which are both necessary
and sufficient to guaran this result. In Corollaries 4.1
and 4.2, for the special case where a divides n we
obtained two infinite families of Hamiltonian circulant
digraphs of the form

tee
;,,Circnaka b.
REFERENCES
[1] R. A. Rankin, “A Campanological Problem in Group The-
ory,” Mathematical Proceedings of the Cambridge Phi-
losophical Soc8, pp. 17-25.
doi:10.1017/S iety, Vol. 44, No. 1, 194
030500410002394X
[2] S. C. Locke and D. Witte, “On Non-Hamiltonian Circu-
lant Digraphs of Outdegree Three,” Journal of Graph
Theory, Vol. 30, No. 4, 1999, pp. 319-331.
doi:10.1002/(SICI)1097-0118(199904)30:4<319::AID-JG
T6>3.0.CO;2-1
[3] D. Witte Morris, J. Morris and K. Webb, “Hamiltonian
Copyright © 2012 SciRes. OJDM
G. ANDRUCHUK, S. GOSSELIN
Copyright © 2012 SciRes. OJDM
163
rete Mathe-
.001
Cycles in (2,3,c)-Circulant Digraphs,” Disc
matics, Vol. 309, No. 17, 2009, pp. 5484-5490.
doi:10.1016/j.disc.2009.01
e,” Discrete Mathematics,
[4] Š. Miklavic
and P. Šparl, “On Hamiltonicity of Circu-
lant Digraphs of Outdegree Thre
Vol. 309, No. 17, 2009, pp. 5437-5443.
doi:10.1016/j.disc.2008.12.004