Open Journal of Discrete Mathematics, 2012, 2, 160163 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 :bxxa 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 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 vertextransitive 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 . 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 outarc with label s for each ;n SCirc S 12 . A Ha miltonian arc sequence is an ordered sequence n ss S of the arc labels encountered in a Hamilton cycle. Since circulant digraphs are vertextransitive, 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 , t denotes the concatenation *The research of S. Gosselin was supported by a University of Winni eg Major Research Grant. C opyright © 2012 SciRes. OJDM
G. ANDRUCHUK, S. GOSSELIN 161 of copies of t . 2. History and Statement of the Main Result One longstanding 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 by b, where 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. 1725. doi:10.1017/S iety, Vol. 44, No. 1, 194 030500410002394X [2] S. C. Locke and D. Witte, “On NonHamiltonian Circu lant Digraphs of Outdegree Three,” Journal of Graph Theory, Vol. 30, No. 4, 1999, pp. 319331. doi:10.1002/(SICI)10970118(199904)30:4<319::AIDJG T6>3.0.CO;21 [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. 54845490. 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. 54375443. doi:10.1016/j.disc.2008.12.004
