2^(r+1) - Cycle Systems of K

Graphs and Combinatorics (2002) 18:687–690

Graphs and Combinatorics  Springer-Verlag 2002

3
2rþ1 -Cycle Systems of Kn  Cn Shung-Liang Wu National Lien-Ho Institute of Technology, Miaoli, Taiwan, R.O.C. e-mail: [email protected]

Abstract. In this paper we investigate the necessary and sufficient conditions for the existence of 3 Æ 2r+1-cycle system of Kn – Cn, where Cn is any Hamilton cycle of Kn and r ‡ 0.

1. Introduction An m-cycle system of a graph G is an ordered pair (V(G), C), where C is a set of mcycles whose edges decompose the edge set of G. There have been many results considering the existence of m-cycle systems of Kn and of Km,n [1, 5]. Recently the set of integers n for which there exists an m-cycle system of Kn where m is odd has been completely settled [1]. Another particularly interesting problem is to let H be one of a family of spanning subgraphs of Kn, and find an m-cycle system of Kn – H. By using difference methods, inductive methods, and amalgamations of graphs, this problem has been solved if H is a 1-factor [1], and if m ¼ 3, 4 or n when H is any 2-factor of Kn [2, 3, 4]. In this paper it is proved that for any Hamilton cycle Cn of Kn and r ‡ 0, there exists a 3 Æ 2r+1-cycle system of Kn ) Cn if and only if 3 Æ 2r+1 divides jEðKn Þj jEðCn Þj, and n is odd.

2. The Results We begin by introducing Lemmas 2.1 to 2.4 which are vital for the proof of the following main theorem. For any edge (v, u) in an m-cycle, let ju  vj denote the edge value of edge (v, u), and let S be the set of edge values of edges in the m-cycle. A 2m-cycle (v0, u0, v1, u1,…, vm)1, um)1) is bipartite if max {v0, v1,…, vm)1} < min {u0, u1,…, um)1}. A bipartite 2m-cycle is exact if the edge-value set S is a sequence Present address: 15 Guang Ming 10 St. Sec. 1, Chu-Bei, Hsin-Chu, 302, Taiwan, ROC

688

S.-L. Wu

of distinct consecutive integers. By easy calculation, Lemmas 2.1 to 2.4 follow, and hence their proofs are omitted. We shall assume that V(Kn) ¼ Zn in what follows. Lemma 2.1. (1) ( 0, 8, 2, 6, 1, 3 ) is a bipartite 6-cycle with S ¼ {2, 3, 4, 5, 6, 8}. (2) ( 2, 9, 0, 11, 1, 14 ) is a bipartite 6-cycle with S ¼ {7, 9, 10, 11, 12, 13}. (3) ( 0, 3 Æ 2r+1, 1, 3 Æ 2r+1 ) 1,…, 3 Æ 2r)1 ) 1, 32 Æ 2r)1 + 1, 3 Æ 2r)1, 32 Æ 2r)1 ) 1, 3 Æ 2r)1 + 1, 32 Æ 2r)1 ) 2,…, 3 Æ 2r ) 1, 3 Æ 2r) is an exact bipartite 3 Æ 2r+1cycle with S ¼ {1, 2,…, 3 Æ 2r+1}, r > 0. There does not exist an exact bipartite 6-cycle. Thus, we will amalgamate two 6-cycles such that they are exact and bipartite. Let Ci (1 £ i £ k) be 2micycles. We use the symbol C1 ¨ C2 ¨ … ¨ Ck (k ‡ 2) to denote the union of edge disjoint graphs C1, C2,…, Ck. The graph C1 ¨ C2 ¨ … ¨ Ck is called exact and bipartite if its edge-value set consists of a sequence of distinct consecutive integers and each 2mi-cycles Ci in C1 ¨ C2 ¨ … ¨ Ck, 1 £ i £ k, is bipartite. Lemma 2.2. ( 0, 8, 2, 6, 1, 3 ) ¨ ( 2, 9, 0, 11, 1, 14 ) is an exact bipartite 6 ¨ 6-cycle with S ¼ {2, 3,…, 13}. Lemma 2.3. If (v0, u0, v1, u1,…, vm)1, um)1) is an exact bipartite 2m-cycle with S ¼ fk; k þ 1; . . . ; k þ 2m  1g; k 1, then ðv0 ; u0 þ j; v1 ; u1 þ j; . . . ; vm1 ; um1 þ jÞ is also an exact bipartite 2m-cycle with S ¼ fk þ j; k þ j þ 1; . . . ; kþ2mþ j  1g. Lemma 2.4. [6] Let ai, bi, c, and d be elements of Zn, and ai „ bi. If |ai – bi| = i or n ) i, 1 £ i £ [n/2], then (ai + c, bi + c) „ (aj + d, bj + d), where all addition is taken mod n, 1 £ i, j £ [n/2], and i „ j. Proof. Since jðai þ cÞ  ðbi þ cÞj ¼ jai  bi j and ðaj þ dÞ  ðbj þ dÞ ¼ aj  bj for c, d ˛ Zn, we have therefore that (ai + c, bi + c) „ (aj + d, bj + d). ( Theorem 2.5. Let Cn be any Hamilton cycle of Kn, and let r ‡ 0. Then there exists a 3 Æ 2r+1-cycle system of Kn ) Cn if and only if 3 Æ 2r+1 divides jEðKn Þj  jEðCn Þj, and n is odd. Proof. Since each 3 Æ 2r+1-cycle contains 3 Æ 2r+1 edges, and each vertex in 3 Æ 2r+1-cycle has even degree, the necessity is clear. Now we proceed with proving the sufficiency. Recall that the vertex set of Kn is Zn. All addition of vertex labels is done mod n. Clearly, jEðKn Þj  jEðCn Þj ¼ nðn  3Þ=2. Since n is odd, and 3 Æ 2r+1 divides n(n ) 3)/2, it follows that n = 3k Æ 2r+2 + 3, k ‡ 1 and r ‡ 0. For convenience, set (n ) 1)/2 = 3k Æ 2r+1 + 1 = q, and denote by C(i) the m-cycle (c0, c1,…, cm)1).

3
2rþ1 -Cycle Systems of Kn  Cn

689

Case 1. r = 0. Without loss of generality we may assume that Cn = (0, 1, 2,…, n)1). Obviously, for any two adjacent vertices x, y in Cn, jx  y j ¼ 1 or n)1. h1i k is even, say k = 2s, s ‡ 1. Let C(i), 1 £ i £ 2s, be 6-cycles defined as Cð1Þ ¼ ð0; 8; 2; 6; 1; 3Þ; Cð2Þ ¼ ð2; 9; 0; 11; 1; 14Þ; .. . Cð2i þ 1Þ ¼ ð0; 8 þ 12i; 2; 6 þ 12i; 1; 3 þ 12iÞ; Cð2i þ 2Þ ¼ ð2; 9 þ 12i; 0; 11 þ 12i; 1; 14 þ 12iÞ; ð0 i s  1Þ .. . Cð2s  1Þ ¼ ð0; 8 þ 12ðs  1Þ; 2; 6 þ 12ðs  1Þ; 1; 3 þ 12ðs  1ÞÞ; and Cð2sÞ ¼ ð2; 9 þ 12ðs  1Þ; 0; 11 þ 12ðs  1Þ; 1; 14 þ 12ðs  1ÞÞ: Let C0 be the union of edge disjoint 6-cycles C(1), C(2),…, C(2s). By Lemmas 2.1 to 2.3, we have that C0 is exact and bipartite with the edge-value set S0 = {2, 3,…, q}. Suppose that (ai, bi) are edges of C0 with jai  bi j = i, 2 £ i £ q. Let Cp = {(ai + p, bi + p) | 2 £ i £ q}, 1 £ p £ n ) 1. Of course, Cp @ C0, 1 £ p £ n ) 1. Since S0 = {2, 3,…, q}, by Lemma 2.4, it follows that for any distinct edges (ai, bi), (aj, bj) in C0, (ai + c, bi + c) „ (aj + c, bj + d), c, d ˛ Zn. This means that all edges in Ci (1 £ i £ n ) 1) are mutually distinct. h2i k is odd, say k = 2s + 1, s ‡ 0. Let C(i), 1 £ i £ 2s +1, be 6-cycles given by ð1Þ s ¼ 0 Cð1Þ ¼ ð0; 8; 2; 6; 1; 3Þ: ð2Þ s 1 Cð1Þ ¼ ð0; 8; 2; 6; 1; 3Þ; Cð2Þ ¼ ð2; 9; 0; 11; 1; 14Þ; .. . Cð2i þ 1Þ ¼ ð0; 8 þ 12i; 2; 6 þ 12i; 1; 3 þ 12iÞ; Cð2i þ 2Þ ¼ ð2; 9 þ 12i; 0; 11 þ 12i; 1; 14 þ 12iÞ; ð0 i s  1Þ .. . Cð2s  1Þ ¼ ð0; 8 þ 12ðs  1Þ; 2; 6 þ 12ðs  1Þ; 1; 3 þ 12ðs  1ÞÞ; Cð2sÞ ¼ ð2; 9 þ 12ðs  1Þ; 0; 11 þ 12ðs  1Þ; 1; 14 þ 12ðs  1ÞÞ; and Cð2s þ 1Þ ¼ ð0; 8 þ 12s; 2; 6 þ 12s; 1; 3 þ 12sÞ: Note that S0 = {2, 3,…, q ) 1, q + 1}. The remaining proof is similar to that in h1i, and omitted.

690

S.-L. Wu

Case 2. r ‡ 1. Without loss of generality we may assume that Cn = (0, q, 2q, q ) 1, 2q ) 1, q ) 2, 2q ) 2,…, 1, q + 1). Note that for any two adjacent vertices x, y in Cn, jx  y j ¼ q, or q + 1. Let C(i), 1 £ i £ k, be 3 Æ 2r+1-cycles defined as Cð1Þ ¼ ð0;3
2rþ1 ;1;3
2rþ1  1;...;3
2r1  1;32
2r1 þ 1;3
2r1 ;32
2r1  1;3
2r1 þ 1;32
2r1  2;...;3
2r  1;3
2r Þ; .. . Cði þ 1Þ ¼ ð0;3
2rþ1 þ 3i
2rþ1 ;1;3
2rþ1 þ 3i
2rþ1  1;...;3
2r1  1;32
2r1 þ 3i
2rþ1 þ 1;3
2r1 ;32
2r1 þ 3i
2rþ1  1;3
2r1 þ 1;32
2r1 þ 3i
2rþ1  2;...;3
2r  1;3
2r þ 3i
2rþ1 Þ; .. .

ð0 i k  1Þ

CðkÞ ¼ ð0;3
2rþ1 þ 3ðk  1Þ
2rþ1 ;1;3
2rþ1 þ 3ðk  1Þ
2rþ1  1;...;3
2r1  1;32
2r1 þ 3ðk  1Þ
2rþ1 þ 1;3
2r1 ;32
2r1 þ 3ðk  1Þ
2rþ1  1;3
2r1 þ 1;32
2r1 þ 3ðk  1Þ
2rþ1  2;...;3
2r  1;3
2r þ 3ðk  1Þ
2rþ1 Þ: Clearly, S0 = {1, 2,…, q ) 1}. The remaining proof is still analogous to that in h1i, and omitted. From the facts that in each case each Ci contains k 3 Æ 2r+1-cycles and has 3 Æ 2r+1 edges, 0 £ i £ n ) 1, it is clear that there exists a 3 Æ 2r+1-cycle system of Kn ) Cn. (

References 1. Alspach, B., Gavlas, H.: Cycle decompositions of Kn and Kn ) I. (submitted) 2. Colbourn, C.J., Rosa, A.: Quadratic leaves of maximal partial triple system. Graphs Comb. 2, 317–337 (1986) 3. Buchanan, H. Ph.D. dissertation. University of West Virginia 1996 4. Fu, H.L., Rodger, C.A.: Four-cycle system with two-regular leaves. Graphs Comb. (to appear)  5. Sotteau, D.: Decompositions of Km,n ðKm;n Þ into cycles (circuits) of length 2k. J. Comb. Theory, Ser. B 30, 75–81 (1981) 6. Wu, S.-L.: Even (m1, m2,…, mr)-cycle system of Kn ) Cn. (submitted)

Received: December 17, 1999 Final version received: July 25, 2000