 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. ka 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Sn,man12,,aa12,, maa 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,ma12,,aaa,man12aa,,n is called the left coset of :bxxaa 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 ,ababa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 0mv If vvVm2,v,DVAivV011,,,, ,mmvava avivA 1,2,,im2,1,iiavv.0m 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 vw1,A11DV and A22,DV12V2 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. 1D2DFor a subset , the circulant digraph nS;Circn Sv is the digraph with vertex set and arcs from to nvs for all nv and all sS. 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nEach 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 SCircsS12. A Ha- miltonian arc sequence is an ordered sequence nsss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 SCircCirc;Circn S. For any arc sequence x, tx denotes the concatenation *The research of S. Gosselin was supported by a University of Winni-peg Major Research Grant. Copyright © 2012 SciRes. OJDM G. ANDRUCHUK, S. GOSSELIN 161of copies of tx. 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  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  constructed some infinite families of connected non- Hamiltonian circulant digraphs of outdegree three. In 2009, Witte Morris, Morris and Webb  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, ) 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 bCirc;,a12; 3,6,4The result of Witte Morris et al in  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4kn1, and if 6 divides and n6n 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 bTheorem 2.2. Let , let ,, nab 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. tCirc0gcd,ta,a bn;,na kWe 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 b3. Proof of Theorem 2.1 Proof: If is Hamiltonian, then it is certainly connected. ;,,Circna ka bConversely, 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 iC denote the coset ib a for 0,1,,gcd ,i1an. We will show that the arc sequence  1gcd ,111tan tka kaaabkaakab (2) is a Hamiltonian arc sequence of . ;,,Circnaka bCStarting from any vertex iv and traversing the arc sequence 1aa, we form a walk which visits every vertex of the coset exactly once. Since iC: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 iCrvqka0qka and 0r, for any fixed vertex in . Thus, starting from any vertex v in and tra- viCiCversing the arc sequence  11kakakaa ka1, we visit every vertex of the coset i exactly once. Since 1iiCbC CiC, traversing arc from any vertex in coset leads to a vertex of the coset . b1iHence, starting from any vertex v of C;Circn S, say ivC, and traversing arc sequence gcd ,an ttxbyb, where x denotes the arc sequences 1aa and de- ynotes the arc sequence  111kakakaa 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 iCv gcd ,1110mod .antaa btkakaabn 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, 21ka and 25b. Here , 3k15a, 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,25Circ4 is  3220 414 .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 fod105 , or07i and 0<15j. The Hamilton cycle given by this arc sequence e 1, wh roino 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 akaNote that if , then the assumption in (1) is that case Theorem 2.2 simply states that 1k is Hab, and in this;Circ na amiltonian if and only if na. 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 tvi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 Hmiltoniaan gcd ,an a. For 1kba, 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 TExample 4.1. If a is odd, a divi and gcd,3 1na, then Corollary 4.1plies that Ci im n4.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  imis hat Ran- plies tHamiltonian. We note that 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 amnian 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     g11 m11 mod 1 mod 1mod .akk akakka kkinak kainatk 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 ccted. 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 aient conn on guaranitof that satisfy conditionsuk 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  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, 194030500410002394X  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-JGT6>3.0.CO;2-1  D. Witte Morris, J. Morris and K. Webb, “Hamiltonian Copyright © 2012 SciRes. OJDM G. ANDRUCHUK, S. GOSSELIN Copyright © 2012 SciRes. OJDM 163rete Mathe-.001Cycles in (2,3,c)-Circulant Digraphs,” Discmatics, Vol. 309, No. 17, 2009, pp. 5484-5490. doi:10.1016/j.disc.2009.01 e,” Discrete Mathematics,  Š. Miklavic and P. Šparl, “On Hamiltonicity of Circu-lant Digraphs of Outdegree ThreVol. 309, No. 17, 2009, pp. 5437-5443. doi:10.1016/j.disc.2008.12.004