4-cycle Systems of Line Graphs of Complete Multipartite Graphs Except where reference is made to the work of others, the work described in this thesis is my own or was done in collaboration with my advisory committee. This thesis does not include proprietary or classified information. Nidhi Sehgal Certificate of Approval: Dean G Hoffman Professor Mathematics and Statistics Chris A Rodger, Chair Professor Mathematics and Statistics Charles C Lindner Professor Mathematics and Statistics George T. Flowers Interim Dean Graduate School 4-cycle Systems of Line Graphs of Complete Multipartite Graphs Nidhi Sehgal A Thesis Submitted to the Graduate Faculty of Auburn University in Partial Fulfillment of the Requirements for the Degree of Master of Science Auburn, Alabama August 9, 2008 4-cycle Systems of Line Graphs of Complete Multipartite Graphs Nidhi Sehgal Permission is granted to Auburn University to make copies of this thesis at its discretion, upon the request of individuals or institutions and at their expense. The author reserves all publication rights. Signature of Author Date of Graduation iii Vita Nidhi Sehgal was born on January 27th 1984, in a small town named Jallandhar, in North India. She grew up in the coastal city of Mumbai on the West coast of India. She completed her high school education at Conossa Convent, Mumbai. She then went on to pursue her Bachelor of Science at St. Xavier?s College in Mumbai. She studied at five educational institutions due to the nature of her father?s profession. This exposed her to the flavor of India and she learnt from such a diverse experience. Then she came to Auburn University, to pursue her doctoral studies in Mathematics, at the Mathematics department of the Auburn University. Nidhi has also learnt Indian Classical dance (Bharatnattyam) for a period of eight years. She is interested in learning various art forms and travelling. She also loves to teach and enjoys cooking in her free time. iv Thesis Abstract 4-cycle Systems of Line Graphs of Complete Multipartite Graphs Nidhi Sehgal Master of Science, August 9, 2008 (B.S., St. Xavier?s College, Mumbai University, 2005) 29 Typed Pages Directed by Chris A Rodger Here we investigate the necessary and sufficient conditions for the existence of 4 - cycle systems of the line graphs of complete multipartite graphs. v Acknowledgments The author is greatly indebted to her Master?s advisor Dr. Chris A. Rodger for his valuable guidance and inpiration. She would like to thank him for his patient endurance and support in times of dificulties without which it would be very difficult for her to complete this work. Also, she would like to thank her committee members Dr. Dean Hoffman and Dr. Charles C Lindner for their support. She is thankful to her grandfather, parents, sister- in-law and brother for their understanding and moral support. Finally she also expresses her gratitude towards her friends who have always been here for her. vi Style manual or journal used Journal of Approximation Theory (together with the style known as ?aums?). Bibliograpy follows van Leunen?s A Handbook for Scholars. Computer software used The document preparation package TEX (specifically LATEX) together with the departmental style-file aums.sty. vii I dedicate this work to maa and papa for their unflagging support. viii Table of Contents List of Figures x 1 Introduction 1 1.1 Definitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.2 History . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.3 Notation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 2 Necessary Conditions 4 3 all parts even all parts odd: odd number of parts 7 4 All parts odd:even number of parts 10 4.1 Line Graphs of Kn ?Ku . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 4.2 4-cycle system of L(K(1,1,...,1,8x + 1)), p negationslash= 6 . . . . . . . . . . . . . . . . 14 4.3 4-cycle system of L(K(1,1,...,1,8x + 1)), p = 6 . . . . . . . . . . . . . . . . 16 5 Conclusion 18 Bibliography 19 ix List of Figures 3.1 4-cycle system . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 4.1 F(1): 1 factor of K8x . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 4.2 F(2): 1 factor of K8x . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 4.3 F(3): 1-factor of K8x . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 4.4 F(4): 1-factor of K8x . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 x Chapter 1 Introduction 1.1 Definitions An m-cycle system of a graph G is a set of m-cycles, the edges in which partition the edge set of G. The line graph of a graph G = (V,E) is the graph L(G) = (E,E1) where E1 is the set of edges that join two vertices if and only if the corresponding edges in G are adjacent. The complete multipartite graph K(a1,a2,...,ap) is the graph with vertex set partitioned into parts {V1,V2,...,Vp}, with |Vi| = ai, in which two vertices in E are adjacent if and only if they are in different parts. By solving this problem we investigate the existence of 4-cycle systems of L(K(a1,a2,...,ap)). 1.2 History There is a long history of problems in this area. In a more general context, Dudeney [3] posed the following problem of seating n people at a dinner table on consecutive evenings so that no person was ever to have the same pair of neighbors more than once. Any solution to this problem is equivalent to finding a set of hamilton cycles of Kn with the property that each 2-path in Kn occurs in exactly one hamilton cycle. This problem was solved when n is even by Kobayashi, Kiyasu-Zen?iti and Nakamura[7], and some results exist when n is odd. And this set S of 4-cycles is known as the Dudeney set. This result was extended further by looking at the case when each pair of people is a neighbor twice. Which was equal to 1 finding a set of hamilton cycles of Kn such that each two path in Kn occurs in exactly two hamilton cycles. And this was solved by Midori, Mutoh, Kiyasu-Zen?iti and Nakamura[9]. It is quite conceivable that the restaurant has many tables of a small size, say m, instead of just one big table. So it is natural to solve the related problem of finding a set of 2-factors in Kn, each cycle in each 2-factor having length m, such that each 2-path in Kn occurs in exactly one m-cycle. This problem was solved by Kobayashi and Nakamura when k = 4 [8]. Notice that in any solution to such a problem, taking the line graph of each 4-cycle produces a 4-cycle system of L(Kn). In [6], Henrich and Nonay removed the requirement that the set of 4-cycles be resolvable (partitionable into 2-factors), finding necessary and sufficient conditions for the existence of a set of 4-cycles such that each 2-path is in exactly one 4-cycle; this provides a 4-cycle system of L(Kn) with the property that every 4-cycle in L(Kn) corresponds to a 4-cycle in Kn. In the same spirit Colby and Rodger[2] found necessary and sufficient conditions for the existence of a 4-cycle system of L(Kn); when n ? 1 (mod 8) no solutions can correspond to the existence of set of 4-cycles in Kn such that each 2-path in Kn is in exactly one 4-cycle. The reader may be interested in a related problem posed by Dudeney [3].Twelve meme- bers of a club arranged to play bridge of eleven evenings, but no player was ever to have the same partner more than once or the same opponent more than twice. And the question was to find a scheme of seating them at three tables every evening. By dropping the require- ment that each player partner each other player atmost once, the solution was equivalent to finding a set S of 4-cycles of K12 with the property that each 2-path in K12 occurs in exactly two 4-cycles. And taking the line graph of each 4-cycle in S produces a 4-cycle system of 2L(K12). 2 In this paper, we extend these results in the literature by investigating the existence of a 4-cycle system of K(a1,a2,...,ap). 1.3 Notation Throughout this paper, letG = K(a1,a2,...,ap). For 1 ? i ? pletVi = {vi,1,vi,2,...,vi,ai}. So the vertex set of L(G) is {{vi,x,vj,y} | 1 ? x ? ai,1 ? y ? aj,1 ? i < j ? p}. Define n =summationtext1?i?p ai to be the number of vertices in G. It will be useful to define hatwidestaiaj = n?ai?aj. 3 Chapter 2 Necessary Conditions In this chapter we investigate some neat necessary conditions which we conjecture are sufficient. Lemma 2.1 If there exists a 4-cycle system of L(G) then 1. ai ? aj (mod 2) for 1 ? i < j ? p, and 2. If ai is odd for 1 ? i ? p then, (a) p ? 1(mod 8) if p is odd, and (b) p ? n(mod 8) if p is even. Proof. The degree of each vertex in L(G) is clearly d({vi,x,vj,y}) = ai +aj ?2 + 2hatwidestaiaj since in G there are aj ?1 + hatwidestaiaj edges incident with vi,x and ai ?1+ hatwidestaiaj edges incident with vj,y. Since we are assuming that a 4-cycle system of L(G) exists, each vertex in L(G) must have even degree. Therefore, we conclude that ai ? aj (mod 2) and so condition (1) is necessary. Now suppose that ai is odd for 1 ? i ? p. We consider the cases where p is odd and even in turn. Case (1) If p is odd then clearly n is odd, being the sum of an odd number of odd numbers. Since there exists a 4-cycle system of L(G), the number of edges in L(G) must 4 be divisible by 4. Each vertex in Vi in G is incident with n ? ai edges. By considering, adjacent pairs of edges at each vertex in G in turn it follows that |E(L(G))| = psummationdisplay i=1 (ai(n?ai)(n?ai ?1))/2. So, 8 must divide 2|E(L(G))| = psummationtext i=1 (ain2)?2 psummationtext i=1 (na2i) + psummationtext i=1 (a3i) + psummationtext i=1 (a2i)? psummationtext i=1 (nai) = n3 ?(2n?1) psummationtext i=1 (a2i) + psummationtext i=1 (a3i)?n2. (?) Notice that, since ai is odd we can write ai = 8z + l for some l ? {1,3,5,7} so, a2i = 64z2 + 16zl +l2, so, a2i ? 1 (mod 8) This also implies that a3i = a2iai ? ai (mod 8). Similarly, since n is also odd we can see that n2 ? 1(mod 8) and n3 ? n (mod 8). Thus from (*), we can say that mod 8: 0 ? 2|E(L(G))| ? (n?(2n?1)p+n?1) = ((2n?1)(1?p)). So clearly p ? 1 (mod 8). Hence condition (2a) is necessary. Case (2) Now supose that p is even and therefore, n is also even. Clearly n3 ? 0 (mod 8). Again we know that 2|E(L(G))| is divisible by 8 and so, from (*) we have mod 8: 5 0 ? 2|E(L(G))| ? (0?(2n?1)p+n?n2) ? (?(2n?1)p?n) ? (p?n) which implies that p ? n (mod 8), thus proving that condition (2b) is necessary. 6 Chapter 3 all parts even all parts odd: odd number of parts In this chapter, we first show that the necessary conditions in Lemma 2.1 are sufficient when all vertices in G have even degree. Then we deal with the case when all parts are odd and there is an odd number of parts. We begin with some useful decompositions. In [10] Sajna proved the necessary and sufficient conditions for the even length cycle decomposition of Kn when n is odd. Also, in [11] Sotteau proved a result regarding even length cycle decompositions of the complete graph Kx,y These results were a more general solution to the following lemma, which is easy to obtain for 4-cycles. Lemma 3.1 There exists a 4-cycle system of: 1. Kn if and only if n ? 1 (mod 8), and 2. Of the complete bipartite graph Kx,y if and only if x and y are even. In [1] Cavenagh and Billington investigated the necessary and sufficient conditions for the existence of an edge-disjoint decomposition of any complete multipartite graph into 4-cycles. The next result is again part of a more general result, and again follows quite readily from Lemma 3.1. Theorem 3.1 [1] There exists a 4-cycle system of G if and only if 1. All parts have even size, or 7 2. All parts have odd size and p ? 1 (mod 8). The last result we need now is well known, but easy to prove here. Let K ?F be the graph formed from the graph K by removing the edges in F. Lemma 3.2 There exists a 4-cycle system of Kn ?F for any even n and any 1-factor F. Proof. Let n = 2x. Let the vertex set of Kn be {1,2,...,x}?{1,2}. The following 4-cycles form the required 4-cycle system: {((a,1),(b,1),(a,2),(b,2)) | 1 ? a < b ? x}. Figure 3.1: 4-cycle system We are now ready to consider 4-cycle systems of L(G). Theorem 3.2 There exists a 4-cycle system of L(G) if 1. ai is even for 1 ? i ? p, or 8 2. ai is odd for 1 ? i ? p and p ? 1(mod 8). Proof. The edges of L(G) can be partitioned into sets that induce complete graphs, namely the complete graphs K(vi,x) with vertex set {{vi,x,vj,y} | 1 ? y ? aj and 1 ? j ? p,j negationslash= i} for each vertex vi,x in V(G). So the edges in K(vi,x) correspond to all the 2-paths in G with middle vertex vi,x. By Theorem 3.1, there exists a 4-cycle system B of G. Consider the set of 4-cycles S in L(G) formed by taking the line graph of each 4-cycle in B. For each vertex vi,x in V(G), the edges in K(vi,x) contained in 4-cycles in S form a 1-factor F(vi,x) of K(vi,x) (to see this, observe that the 4-cycles in P pair the edges incident with vi,x in V(G), and each such pair produces an edge in K(vi,x) which is vertex-disjoint from the other such pairs). Also, each such complete graph has even order, so by Lemma 3.2 there exists a 4-cycle system T(vi,x) of K(vi,x)?F(vi,x). So the union of the T(vi,x) over all the vertices vi,x in V(G) together with the 4-cycles in S produce the required 4-cycle system. 9 Chapter 4 All parts odd:even number of parts 4.1 Line Graphs of Kn ?Ku In this chapter we make progress in tackling the difficult last case, solving a problem that is of interest in its own right. Much progress solving existence problems for graph designs has been made by using decompositions of complete graphs with holes; that is, of Kn ? Ku. Such decompositions are now of interest in their own right. This is a graph in the family we are considering in this paper, namely the graph G with ap = u, and ai = 1 for 1 ? i ? p?1, and p = n?u+1. We begin with a result by Henrich and Nonay referred to in the introduction. Throughout this chapter we deal with the case where ai is odd for 1 ? i ? p and p is even. Theorem 4.1 [6] Let p be even. There exists a 4-cycle system of L(Kp). We shall also use some of the results by Fu, Fu and Rodger regarding 4-cycle systems of Kn - E(F) and 2Kn - E(F) for all 2 regular subgraphs F. Theorem 4.2 [4, 5] There exists a 4-cycle system of Kz ?P for any graph P of maximum degree at most 3 if and only if 1. z is odd, 2. the number of edges in Kz ?P is divisible by 4, and 3. if z = 8x+1 then P is not one of two exceptional graphs, both of which are 3-regular. 10 We will use this result several times, including the following corollary. Let Cz denote a cycle of length z. Corollary 4.1 There exists a 4-cycle system of Kz ?P if: 1. z ? 1 (mod 8) and P = ?, 2. z ? 3 (mod 8) and P = C3, 3. z ? 5 (mod 8), z negationslash= 5, and P = C6, and 4. z ? 7 (mod 8) and P = C5. Our final preparatory result is needed just for the case when p = 6. Form the graph G?H from G?H by joining each vertex in G to each vertex in H. Lemma 4.1 There exists a set F = {F(1),...,F(4)} of four 1-factors in K8x for which there exists a 4-cycle system of (K8x ?F)?K1. Proof. Let the vertex set be (Z4 ?Z2 ?Zx)?{v}. The required cycle system can be formed by taking: 1. F(k) = {{(j,0,i),(j +k,1,i)} | j ? Z4,i ? Zx} for each k ? {1,2,3}, 2. F(4) = {{(j,k,i),(j + 2,k,i)} | j,k ? Z2,i ? Zx}, 3. B(1) = {((0,0,i),(1,0,i),(2,0,i),(3,0,i)),(v,(j,0,i),(j,1,i),(j + 1,1,i)) | j ? Z4, i ? Zx}, and 4. A 4-cycle system B(y,z) of K8,8 with bipartition {{Z4 ?Z2 ?{y}},{Z4 ?Z2 ?{z}} for 0 ? y < z < x (see Lemma 3.1). 11 Figure 4.1: F(1): 1 factor of K8x Figure 4.2: F(2): 1 factor of K8x 12 Figure 4.3: F(3): 1-factor of K8x Figure 4.4: F(4): 1-factor of K8x 13 We are now ready to find 4-cycle systems of L(Kn?Ku), which we state in the following form. By Lemma 2.1, u ? 1 (mod 8) is a necessary condition when p is even. The case where p is odd is handled in the previous chapter. 4.2 4-cycle system of L(K(1,1,...,1,8x + 1)), p negationslash= 6 Theorem 4.3 There exists a 4-cycle system of L(G) if p is even, ai = 1 for 1 ? i ? p?1 and ap = 8x+ 1. Proof. Let Vj = {t(j)} for 1 ? j ? p ? 1 and let Vp = {t(0),s(i) | 1 ? i ? 8x}. For each vertex w ? V(G), let K(w) be the complete subgraph of L(G) induced by the vertex set {{w,wprime} | wprime ? V(G) \ {w}}. So K(w) contains p ? 1 vertices if w ? Vp, and K(w) contains p + 8x ? 1 vertices otherwise. For 1 ? j ? p ? 1 it will also be useful to define Kprime(t(j)) to be the subgraph of K(t(j)) induced by the vertices in {{t(j),s(i)} | 1 ? i ? 8x}. If p = 2 then L(G) is isomorphic to K8x+1, and if x = 0 then L(G) is isomorphic to K1, so the result follows from Lemma 2.1. Now assume that x ? 1 and p ? 4. We will handle the case p = 6 last, so for now assume that p negationslash= 6. Let F = {F(i) | 1 ? i ? 3} be a set of 3 edge disjoint 1-factors in K8x defined on the vertex set {1,2,...,8x}. The construction contains 5 types of 4-cycles. Type 1. Let B(1) be a 4-cycle system of L(Kp) in which Kp is defined on the vertex set {t(j) | 0 ? j ? p?1}. This exists by Theorem 4.1. Type 2. For 1 ? i ? 8x let B(2,i) be a 4-cycle system of K(s(i)) ? C(s(i)), where C(s(i)) is the cycle ({s(i),t(1)},{s(i),t(2)},...,{s(i),t(?)}), and where ? = 0,3,6 or 5 14 when p ? 1 ? 1,3,5 or 7 (mod 8) respectively. Such a 4-cycle system exists by Corollary 4.1. Notice that since p negationslash= 6, p?1 ? ?, so K(s(i))?C(s(i)) is well defined. Type 3. If ? > 0 then define the following 4-cycle systems. For 1 ? i ? 8x, al- ternately color the edges of C(s(i)) with 1 and 2, except if ? is odd then the last edge {{s(i),t(1)},{s(i),t(?)}} is colored 3; so the same proper edge-coloring is used on each of the 8x cycles. For each edge {{s(i),t(j)},{s(i),t(j+1)}} (reducing j+1 mod ?) in C(s(i)) colored k, form the 4-cycle ({s(i),t(j)},{s(i),t(j+1)},{s(i1),t(j+1)},{s(i1),t(j)}), where {i,i1} is the edge incident with vertex i in F(k). (This same 4-cycle is defined again when i1 is used instead of i, but we only use it once, of course, in the following union.) Let B(3) be the union of all such 4-cycles. Note that the edges in the 4-cycles in B(3) contain: 1. All the edges in C(s(i)) for 1 ? i ? 8x, and 2. The edges in a 2-factor R(t(j)) of Kprime(t(j)) for 1 ? j ? ?. The second property holds since, when j ? ?, for each vertex {t(j),s(i)} in Kprime(t(j)), the two 4-cycles containing the edges {{s(i),t(j?1)},{s(i),t(j)}}, and {{s(i),t(j)},{s(i),t(j+1)}} (reducing sums mod?) colored sayaandbalso contain the 2 edges{{t(j),s(i)},{t(j),s(ia)}}, and {{t(j),s(i)},{t(j),s(ib)}} where {i,ia} and {i,ib} are edges in F(a) and F(b) respec- tively. So by this explanation, in fact R(t(j)) is isomorphic to F(a) ? F(b). If j > ? or if p?1 ? 1 (mod 8) (this is the case where ? = 0) then define R(t(j)) = ?. Type 4. For 1 ? j ? p ? 1, let B(4,j) contain the 4-cycles in a 4-cycle system of K8x+1 ? R(t(j)) defined on the vertex set V(Kprime(t(j))) ? {{t(j),t(0)}}. This exists by Theorem 4.2 since: 1. Each vertex has degree 8x or 8x?2 which is even, 15 2. The number of edges is (8x+1)4x if R(t(j)) = ? and is (8x+1)4x?8x = (8x?1)4x otherwise, so is divisible by 4, and 3. R(t(j)) for 1 ? j ? ? is not one of the exceptional graphs since it is 2-regular. Type 5. For 1 ? j ? p ? 1 let B(5,j) be a 4-cycle system of the complete bipar- tite graph Kp?2,8x with bipartition of the vertex set {{{t(j),t(z)} | 1 ? z ? p ? 1,z negationslash= j},V(Kprime(t(j)))}. This exists by condition (2) of Lemma 3.1. Then B(1)?(?1?i?8xB(2,i))?B(3)?(?1?j?p?1B(4,j))?(?1?j?p?1B(5,j)) provides the required 4-cycle system. 4.3 4-cycle system of L(K(1,1,...,1,8x + 1)), p = 6 Finally, suppose that p = 6. The difficulty here is that the Type 2 4-cycles must be different because it is impossible to fit a 6-cycle in a graph with only 5 vertices. This can be overcome by the use of 4 1-factors in Kprime(t(1)), for example. Nevertheless, the construction is very similar, so a brief description follows, again defining the five types of 4-cycles in turn. If the same set of cycles is used, we simply state that. In this case, let {F(1),...,F(4)} be a copy of the 4 1-factors defined in Lemma 4.1 on the vertex set {1,2,...,8x}. Type 1. Same as before. 16 Type 2. Let B(2) = {({s(i),t(2)},{s(i),t(4)},{s(i),t(3)},{s(i),t(5)}) | 1 ? i ? 8x}. Let C(s(i)) be the set of 6 edges occurring in no 4-cycle in B(2) (these edges induce two copies of K3 with one vertex in common). Type 3. For 1 ? i ? x, properly color the edges of C(s(i)) with the 4 colors in {1,2,3,4}. For each edge {{s(i),v1},{s(i),v2}} in C(s(i)) colored k, form the 4-cycle ({s(i),t(j)},{s(i),t(j +1)},{s(i1),t(j +1)},{s(i1),t(j)}), where {i,i1} is the edge incident with vertex i in F(k). These 4-cycles use the edges forming: 1. a 4-factor R(t(1)) isomorphic to ?1?k?4F(k) in Kprime(t(1)), and 2. for 2 ? j ? 5 a 2-factor R(t(j)) in Kprime(f(j)), each being isomorphic to the union of two of these four 1-factors. Type 4. For 1 ? j ? p ? 1, let B(4,j) contain the 4-cycles in a 4-cycle system of K8x+1 ? R(t(j)) defined on the vertex set V(Kprime(t(j))) ? {{t(j),t(0)}}. This exists by Lemma 4.1 if j = 1 and by Theorem 4.2 otherwise. Type 5. Same as before. 17 Chapter 5 Conclusion By pooling all the results in this thesis we see that there exists a 4-cycle system of the line graph of G for the following cases: 1. All parts are even. 2. All parts are odd and (a) p ? 1 (mod 8), when p is odd (b) ai = 1 for 1 ? i ? p?1 and ap = 8x +1, when p is even, Finally, we conjecture the following: Conjecture 5.1 There exists a 4-cycle system of the line graph of G for the following case: 1. All parts are odd and p is even. 18 Bibliography [1] N. J. Cavenagh and E. J. Billington, Decomposition of complete multipartite graphs into cycles of even length, Graphs Combin., 16 (2000), 49?65. [2] M. Colby and C.A. Rodger, Cycle Decompositions of the Line Graph of Kn, J. Combin. Theory (A), 62 (1993), 158?161. [3] H. E. Dudeney, Amusements in Mathematics, Dover, New York, 1959. [4] C. M. Fu, H. L. Fu, C. A. Rodger and T. Smith, All graphs with maximum degree 3 whose complements have a 4-cycle decomposition, Discrete Math., to appear. [5] H. L. Fu and C. A. Rodger, Four-cycle systems with two-regular leaves, Graphs Com- bin., 17 (2001), 457?461. [6] K. Henrich and G. Nonay, Exact coverings of 2-paths by 4-cycles, J. Combin. Theory (A), 45 (1987), 50?61. [7] M. Kobayashi, Kiyasu-Zen?iti and G. Nakamura, A solution of Dudeney?s round table problem for an even number of people, J. Combin. Theory (A), 63 (1993), 26?42. [8] M. Kobayashi and G. Nakamura, Resolvable coverings of 2-paths by 4-cycles. J. Com- bin. Theory (A), 60 (1992), 295?297. [9] Midori, N. Mutoh, Kiyasu-Zen?iti and G. Nakamura, Double coverings of 2-paths by hamilton cycles. J. Combin. Des., 10 (2002), no. 3, 195?206. [10] M. Sajna, Cycle decompositions III. Complete graphs and fixed length cycles, J. Com- bin. Des., 10 (2002), 27?78. [11] D. Sotteau, Decomposition of Km,n(K?m,n) into cycles (circuits) of length 2k, J. Combin. Theory (B), 30 (1981), 75?81. [12] D. Hoffman, David Pike, 4-Cycle decompositions of the cartesian product of two com- plete graphs, Journal of Combin. Math. and Combin. Computing 28 (1998) 215-226. 19