Cycle Systems by Nidhi Sehgal A dissertation submitted to the Graduate Faculty of Auburn University in partial ful llment of the requirements for the Degree of Doctor of Philosophy Auburn, Alabama May 6, 2012 Keywords: 4-cycle systems, 6-cycle systems, fair m-cycle systems, line graph, cartesian product, complete graph, leave Copyright 2012 by Nidhi Sehgal Approved by Dr. C.A. Rodger, Chair, C. Harry Knowles Professor, Assoc. Dean for Research and Graduate Studies Dr. Curt Lindner, Distinguished University Professor Dr. Dean Ho man, Professor Dr. Pete Johnson, Professor Abstract In this dissertation the author has found the necessary and su cient conditions for obtaining a 6-cycle system of the Cartesian product of two complete graphs covering 2- paths in the corresponding bipartite graph. She has found the maximum fair 6-cycle system as well as 6-cycle system of the Cartesian product of two complete graphs. As a part of this dissertation, the author has also found the necessary and su cient conditions required to obtain a 4-cycle system of complete graph on n vertices with a nearly 2-regular leave. Finally the author has worked on the problem of nding a 4-cycle system of the line graph of a complete multipartite graph. ii Acknowledgments My Back Pages Nidhi was born in a small town called Jallandhar in the northern state of Punjab in India. She grew up in Mumbai on the western coast of India. She completed her Bachelor of Science from St. Xavier?s College in Mumbai. She completed her Master in Science from Auburn University under the guidance of Dr. Chis Rodger. After completing her MSc. in 2008, she continued to work under the guidance of Dr. Chris Rodger for doctoral research. Nidhi worked on the problem of nding the necessary and su cient conditions for obtaining the 4- cycle system of the Line graph of a complete multipartite graph during her Masters. She then continued to work on this problem for her doctoral research. And went on to work on four other problems too for her doctoral research. She would like to thank her Major professor Dr. Rodger for his continued support and guidance. He is a great mentor and friend. She would like to thank her other committee members: Dr. Lindner, Dr. Ho man and Dr. johnson for their support. she would also like to express her thanks to all the members/colleagues of the Dept. of Mathematics and Statistics for their support. Nidhi would also like to express her heartfelt gratitude to her family and friends for their continued support throughout the ve years. \Ah, but I was so much older then Im younger than that now" iii Table of Contents Abstract . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ii Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iii List of Tables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . vi 1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 2 6-cycle system of the Cartesian Product of Kx Ky covering 2-paths in Kx;y . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 2.2 Notation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 2.3 Preliminary Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 2.4 Propositions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 2.5 Main Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 3 Maximum fair 6-cycle system of the Cartesian Product of two Com- plete Graphs Kx Ky . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28 3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28 3.2 Notation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 3.3 Preliminary Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30 3.4 Proposition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41 4 6-cycle system of the Cartesian Product of two Complete Graphs . . . 43 4.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43 4.2 Preliminary Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44 4.3 Propositions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48 5 Nearly 4-regular Leave of the Complete Graph on n vertices, Kn . . . . 66 iv 5.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66 5.2 Applications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67 5.3 Proposition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85 6 4-cycle system of the line graph of a complete multipartite graph: adding eight vertices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93 6.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93 Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 96 v List of Tables 2.1 An ordered STS(7) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 2.2 An ordered STS(9) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 vi Chapter 1 Introduction 1.1 Introduction A graph G, consists of a set of vertices or points, and a set of edges. G is denoted as an ordered pair, (V(G);E(G)), where V(G) denotes the set of vertices or points, and E(G) denotes the set of edges or line segmentsfu;vg(or more simply uv), such that u;v2V(G). The number of vertices in G is said to be the order of G and the number of edges in G is said to be the size of G. Edges (e) are unordered pairs of vertices (fu;vg) that can be depicted as line segments that connect the vertices, and the two vertices (u and v) that are connected by the edge (e) are said to be it?s endpoints, and the edge (e) is said to be incident to the two vertices (u and v). Any two vertices (u and v) are said to be adjacent if they form the endpoints of an edge (e). The degree of a vertex v in V(G) is the number of vertices adjacent to the vertex v in G. The degree of a vertex is also denoted by deg(v). A loop is an edge that connects a vertex to itself. A graph is said to have multiple edges if at least one pair of vertices are connected by more than one edge. A simple graph is a graph that contains no loops nor multiple edges. A graph G0 is said to be a subgraph of a graph G if V 0(G) V(G) and E0(G) E(G). And G0 is said to be an induced subgraph of a graph G if it is formed by the set of vertices V 0(G), where V 0(G) V(G), and the edge set of G0 contains the edges in E(G) that join the vertices in V 0(G). A graph on n vertices in which each vertex is adjacent to every other vertex is said to be a complete graph. It is denoted by Kn, where n is the order of the graph. The numbers of edges in Kn is given byjE(G)j= (n)(n 1)=2. Kn denotes the graph formed by joining each pair of adjacent vertices in Kn by edges. 1 A complete multipartite graph is denoted by G = K(a1;:::;ap); the vertex set of G can be expressed as the disjoint union, V(G) = V(Ka1)[V(Ka2)[:::V(Kap), and fu;vg2E(G) if and only if u2V(Kai), u2V(Kaj) such that i6= j. The case when p = 2 is de ned to be the bipartite graph denoted by K(m;n) where a1 = m and a2 = n. An m-path is a sequence of m + 1 vertices such that each vertex is connected to the next vertex and two vertices have degree one, rest have degree two. It is also denoted by Pm+1 =fv1;v2;:::;vp+1g. An m-cycle is an m-path with the property that v1 = vp+1. It is also denoted by Cm = (v1;v2;:::;vp). Any connected graph with no cycles is said to be a tree. A forest is a disjoint union of trees. A hamilton path is a path that spans the vertex set of a graph G. Simillary we also de ne a hamilton cycle which spans the vertex set of a graph G. An m-cycle system of a graph G is denoted by (V(G);C) where the set C contains cycles of length m whose edges form a partition of the edge set of G. The line graph of a graph G, L(G) is de ned as follows: Every edgefu;vg2 E(G) is a vertex in L(G) and two vertices are adjacent in L(G) if the corresponding edges in G have a common end point. A clique of a graph G is a subset of the vertex set of G such that any two vertices in the clique are adjacent to one another. The history presented below is in chronological order. In 1847, Kirkman [62] posed one of the earliest problems of graph theoretical im- portance given below. Historically the problem is stated as follows: \If Qx denotes the greatest number of triads that can be formed with x symbols, so that no duad shall be twice employed, then 2 3Qx = c(x 1)=2 Vx if for Vx we put 6k+4, when x = 6n 1;x=2+3k+1, when x = 6n 2; 0 when x = 6n+1 or 6n+ 3; and x=2, when x = 6n or 6n+ 2: where 2m(2k+ 1) = n;x;n;m;k, being all integers 0". Notice that Vx is the number of duads excluded from Qx . He then gave solutions for Q3;Q7;Q15 and Q25. In graph theory terminology, this problem asks for a 3-cycle system of as big a subgraph of Kx as possible. Kirkman gave the solution for the 3-cycle systems of K3;K7;K13 and K25. Since then, there has been a lot of interest in problems pertaining to m-cycle systems of G, especially the case where G = Kn. In 1965, K otzig [63] gave several results regarding even cycle systems of Kn. He rst showed that there exists a 4k-cycle system of Kn when n 1 (mod 8k) (su cient condition). For the case where n and k are relatively prime he gave necessary and su cient conditions to obtain a 4k-cycle system of Kn where n 1 (mod 8k). Finally he showed that Kn can be decomposed into 2p-cycles, where p is prime if and only if n 1 (mod 2p+1). In 1966, Rosa [80] completed K otzig?s result regarding even cycle systems of Kn by giving a solution for the case where m 2 (mod 4). He showed that there exists a cyclic decomposition of Kn into p-cycles where p 2 (mod 4) and n = 2kp+1 for any k and p. In 1966 Rosa [81], solved the problem further by giving partial solutions to the case where m is odd, n 1 (mod 2m), and n is an odd prime number satisfying the condition, n m (mod 2m). There are results in literature about various other type of H decompositions of Kn too, where H is a subgraph of Kn. In 1979, Tarsi [88] gave necessary and su cient conditions for obtaining the star decomposition, Sn of Kn. A star Sn is de ned to be the bipartite graph K1;n. A few years later in 1983, Tarsi [89] gave a result regarding path decompositions of Kn. He showed that the obvious necessary condition for obtaining an 3 m-path decomposition of Kn, n(n 1) 0 (mod 2m) and n m + 1, is also su cient. In 1980, Alspach and Varma [4] gave necessary and su cient conditions for obtaining a 2pe- cycle system of Kn, where p is prime and e is any positive integer. They showed that there exists a 2pe-cycle system of Kn if and only if n is odd, n 2pe and 2pe divides (n2 ). In 1981, D. Sotteau [84] proved a prominent result on cycle systems of the complete bipartite graphs, K(m;n). She showed that the complete bipartite graph K(m;n) can be decomposed into cycles of length 2k if and only if m and n are even integers not less than k and 2k divides mn. She also gave the conditions for obtaining a directed 2k-cycle system of the digraph K(m;n) . In 1988, Jackson [51] gave a result for obtaining odd cycle systems of Kn. He proved that there exists an m-cycle system of Kn, where n 1 or m (mod 2m) and m is odd . Finally in 1989, Ho man, Rodger, Lindner [45] gave necessary conditions for nding the m-cycle system of Kn, when m is odd. They showed that these necessary conditions are also su cient if and only if there is an m-cycle system of all orders n satisfying the necessary conditions with m n< 3m. In this paper the authors also gave an important result about complete graphs with a hole of size v, where v is odd. They showed that for odd v = ql+r, where 1 r l, if q m+2r 1, there exists an m-cycle system of K2m+v with a hole of size v. The reader is referred to the paper by Rodger [79] in 1990 for a complete survey on the above mentioned results. By 1992, many researchers had solved the problem of nding an m-cycle system of Kn for values of m 37. In 1993, Saad Zanati and Rodger [28] solved the problem of obtaining the H decomposition of Kn, where H is a simple connected subgraph of Kn containing at most 5 edges, which had the additional property of being able to 2-color the vertices so that no copy of H is monochromatic. The existence of m-cycle systems of L(Kn) was settled when m 2f4;6gin [16, 21, 20]. In 1993, Colby and Rodger [21] showed that there exists a 4-cycle system of Kn if and only if n and satisfy (a) n is even, or (b) n 1 (mod 4) and 0 (mod 2), or (c) n 3 (mod 4) and 0 (mod 4), or (d) n 1 (mod 8) and is odd. Continuing the work on 4 m-cycle systems of L(Kn), Cox and Rodger [20] in 1996 showed that such cycle systems exist for n 1 (mod 2m)n and for all m;n with m 0 (mod 4) and n 0 or 2 (mod m). Also, there have been some results for obtaining m-cycle systems of K(a1;a2;:::;ap), for example being settled when all parts have the same size in [28] where m is even and when p is small and then: There is a companion result for obtaining 4-cycle systems [78] of L(K(a1;a2:::;an)), but much remains to be done in this area. Some new results regarding this problem are discussed in Chapter 6. By that time, a lot of research had been done on nding necessary and su cient conditions for obtaining m-cycle systems of Kn in the case where n is odd. However, when n is even, the vertices of Kn have odd degree and therefore it is not possible to obtain an m- cycle system of Kn in this case. Thus, the natural question to ask was what is the maximum number of m-cycles that can be obtained in the case when n is even? Due to the odd degree of each vertex in this case, we will have to remove some edges from Kn in order to be able to construct an m-cycle system. The set of edges removed from the graph G is said to be the leave, (F). The problem of nding necessary and su cient conditions to obtain m-cycle systems of Kn and Kn F, where F is a leave, has generated a lot of interest. A k-regular graph is a graph in which every vertex has degree k. A k-factor of a graph G is a spanning k-regular subgraph of the graph G. In 1986, Colbourn and Rosa [19] used di erence methods to show that there exists a 3-cycle system of Kn F where F is any 2-regular leave. The problem of obtaining an m-cycle system of Kn minus a 1-factor was looked at by Alspach and Marshall in 1994 [3]. In their paper they gave necessary conditions for obtaining an m-cycle system of Kn I where m and n are both even and I is a 1-factor. In 1996, Buchanan in his PhD dissertation solved the problem of nding an n-cycle system (or hamilton cycle system) of Kn with a 2-regular leave. Later Bryant [12] in 2004 and McCauley [68] in 2008 gave di erent proofs for this problem. 5 In 2000, Fu and Rodger [31] found necessary and su cient conditions for decom- posing Kn F into 4-cycles, where F is an n vertex forest. In 2001 [32], the same authors solved the problem of obtaining 4-cycle systems of Kn F and 2Kn F, where F is a 2-regular leave, using the method of induction. Finally in 2001, Alspach and Gavlas [2] found necessary and su cient conditions for half the cases of the problem of nding m-cycle systems of Kn and of Kn I, where I is a 1-factor. In their remarkable paper they proved that the obvious necessary conditions, that each vertex in Kn have even degree and the total number of edges in Kn be divisible by the length of the cycle m, are also su cient conditions to obtain the m-cycle system of Kn where m and n are both odd, and to obtain the m-cycle system of Kn I where m and n are both even. In 2002, Sajna [82] showed that if for all n satisfying the equation m n 3m there exists an m-cycle system of Kn I, when m is odd, then there exists an m-cycle system of Kn I for all values of n m. In 2002, Sajana [83] settled the existence problem of necessary and su cient conditions of m-cycle systems of G by solving the last two cases remaining in Alspach and Gavlas?s paper. He proved that necessary conditions are also su cient for the cases when m is even and G = Kn, and when m is odd and G = Kn I. The case where the leave F is any 2-regular graph and m = 4 was solved in [31]. The case where F is any graph with maximum degree 3 and m = 4 was solved in [34]. In 2003, Leach and Rodger [65] showed that for n 1, p 2 and any given set of integers s1;s2:::;sq satisfying the conditions sj p+ 1 for 1 j q and Pqj=1sj = np, there exists an n-cycle system of the complete p-partite graph K(n;n;:::;n) minus a 2-factor containing q cycles where the jth cycle is of length sj. In 2004, Ashe and Rodger [5] carried forward the research of Fu and Rodger on m-cycle systems of Kn F, where F is a forest (solved in 2000). Ashe and Rodger found necessary and su cient conditions for existence of a 6- cycle system of Kn F, where F is any spanning forest of Kn. In 2004, Leach and Rodger 6 [66] showed that there exist n-cycle systems of Kn F, where F is a 3-factor. They also proved that given any 2-factor of Kn there exists a 3-factor, F of Kn containing the given 2-factor which statis es the previous statement. In 2005, Ashe and Rodger [6] continued their research on 6-cycles systems of Kn with a leave. They gave necessary and su cient conditions to settle the existence of 6-cycle systems of Kn F, where F is any 2-regular leave, not just a spanning subgraph of Kn like in their previous paper in 2004. This result was taken further in 2007 by Ashe, Leach and Rodger [7]. They gave necessary and su cient conditions for obtaining 8-cycle systems of Kn F, where F is any 2-regular leave. We have carried forward the reasearch done by Fu and Rodger in 2001, by settling the necessary and su cient conditions for the 4-cycle systems of Kn F , where F is a nearly regular leave in 2009. A nearly 2-regular leave is a 2-regular leave with the additional property that one special vertex, say1having degree k, k> 2. The details of this result are given in Chapter 5 and can also be found in [85]. There are some results regarding m-cycle systems of G F, where G is a complete multipartite graph and F is a leave. One of the rst results about this problem was by Byrant, Leach and Rodger in 2005 [12]. They showed that there exists a n-cycle system of K(n;n) F, where F is a 3-regular leave. Another problem of graph theoretical importance was posed by Judson in 1899 [30]: \Seven persons met at a summer resort, and agreed to remain as many days as there are ways of sitting at a round table, so that no one shall sit twice between the same two companions. They remained fteen days. It is required to show in which way they may be seated." In 1900, Philbrick, [48] gave a solution to Judson?s problem for the cases when there are 6 people (can be seated on 10 days) and when there are 8 people (he showed that they can be seated as per Judson?s conditions for 21 days). In 1904, Sa ord, [50] gave the solution 7 to Judson?s original problem for 7 people. In 1905, Dickson [25] gave a generalization of Judson?s problem using group theory. His problem statement was \The general problem is to nd all complete sets Smi of dihedrons"?, where Smk was de ned to be a set of k mutually consistent dihedrons on m letters when every dihedron on m letters was inconsistent with at least one dihedron of Smk . He then went on to solve his problem (another version of Judson?s problem) for the cases when m (number of persons) was 6 (solution: 10 days), 8(solution: 21 days), 10(solution: 36 days) and 12(solution: 55 days). Rather than explain this notation, instead we consider the equivalent problem posed by Dudeney in 1905 [26] which can be described in graph theoretical terminology as follows: \Seat the same n persons at a round table on (n 1)(n 2)=2 occasions so that no person shall ever have the same two neighbors twice. This is, of course, equivalent to saying that every person must sit once, and only once, between every possible pair". This problem is now known as Dudeney?s Round Table problem. In 1917, Dudeney [27] gave solutions for the cases 3 n 12. He claimed to have solved the problem for the cases where 2 n 25 and n = 33. In graph theory this problem is equivalent to asking for a set of hamilton cycles of Kn, with the added property that every 2-path lies in exactly one hamilton cycle. This set of hamilton cycles is also known as the Dudeney set. Some other generalizations of this problem could be formed by looking at x tables of size m each instead of considering one large table. 8 An (H;J) -covering of G is de ned to be a set U of copies of the subgraph H in G such that each copy of J in G is contained in exactly of the copies of H in the set U. More informatively, this is also known as a set of copies of H that cover each copy of J in G. There are various results about 2-path coverings; that is, the case where J is the 2-path, P3. One of the earliest results was by Hanani in 1960 [40]. He proved that the condition n 2 or 4 (mod 6) is necessary and su cient in order to obtain a 4-cycle system of Kn which covers each 2-path in Kn exactly once. In 1973, Huang and Rosa [47] solved Dudeney?s Round table problem for the case when n = p+ 1, p prime, and they mentioned that they found cyclic solutions for n = 13;15. In 1983, Heinrich [41] showed that Kn can be decomposed into oriented 2-paths. She proved that whenever the two arcs in the 2-path have consistent orientation the result is true if and only if n is odd. Otherwise, the result holds for all n 4. In 1987, Heinrich and Nonay [43] proved that there exists a set of 4-cycles, (C4;P3) -covering of Kn if and only if one of the following conditions is satis ed:(1) n is even, (2) n 1 (mod 4) and 0 (mod 2), or (3) n 3 (mod 4)and 0 (mod 4). As a continuation of this result the same authors in 1988 [44] solved the problem of obtaining the minimum (maximum) number of 4-cycles in Kn such that each 2-path in Kn is contained in exactly 4-cycles. In 1992, Kobayashi and Nakamura [54] gave necessary and su cient conditions to obtain an n-cycle system of K2n such that each 2-path in K2n lies in exactly two n-cycles. Later in 1993, these authors along with Kiyasu [53] gave the solution to Dudeney?s Round Table problem for the case where n is even. A set of n-cycles of Kn is said to be a double Dudeney set if each 2-path in Kn is contained in exactly two n-cycles. Thus, these authors rst constructed a double Dudeney set and then also gave the construction for a Dudeney set for the case when n is even. Heinrich, Langdeau and Verall [42] in 2000 solved the problem of nding n-cycle systems of Kn such that each 2-path in Kn is covered in exactly n-cycles. In this paper they also showed there exists an H decomposition of Kn such that each 2-path in Kn is covered in exactly copies of H, for each subgraph H of Kn 9 having at most 4 vertices. Finally, they proved that there exists a 3-path decomposition of K(n;n) covering each 2-path of K(n;n) exactly once. In the following year, McGhee and Rodger [69] took the previous result further by giving two new constructions for the problem of nding a set of 3-paths in Kn such that each 2-path is contained in exactly one 3-path. They also solved a more general problem of nding an m-path decomposition of Kn covering (m 1)-paths. In 2001, Kobayashi and Nakamura [55] solved the problem of nding a set of 4-paths in Kn which cover each 2-path exactly once. The authors along with Nobuaki and Kiyasu [56] gave constructions for a double Dudeney set for the case when n 3 is odd. Kobayashi et. al. [57] solved the problem of obtaining a set of 5-paths in Kn such that each 2-path is contained in exactly one 5-path in Kn. In 2004, McGhee and Rodger [70] proved that for all n 4 there exists a set of 4-paths in Kn such that each 2-path is contained in exactly one 4-path. In the same year these authors [71] also gave a result about embedding coverings of 2-paths with 3-paths. Kobayashi et. al. have de ned the uniform covering of the 2-paths in Kn with m-paths (m-cycles) as a set S of m-paths (m-cycles) having the property that each 2-path in Kn lies in exactly one m-path (m-cycle) in S. In 2005, Kobayashi et. al. [58] proved that there exists a uniform covering of 2-paths with 5-paths in Kn. Akiyama, Kobayashi and Nakamura also proved that there exists a uniform covering of 2-paths with 6-paths in 2005 [1], 6-cycles in 2006 [59]. In Chapter 2, we have given the constructions for obtaining a 6-cycle system of Km Kn which covers each 2-path in K(m;n) exactly once. An m-cycle system of a graph G is said to be k-perfect if replacing each m-cycle c by the graph formed by replacing the edges in c with the edges joining vertices distance k apart in c produces another cycle system of G. Necessary and su cient conditions for obtaining 2-perfect 6-cycle systems of Ks for all possible values of s was solved in [67]. The problem of nding non-isomorphic 2-perfect 6-cycle systems of Ks was solved for the case 10 s = 13 in [38]. This problem was taken further in [9], where the authors solved the problem of obtaining 2-perfect 6-cycle systems of Ks for all > 1. For all , those authors later also solved the spectrum problem of 6-cycle systems of 2 Ks for which the collection of distance 3 graphs obtained from each 6-cycle covers Ks (see [10]). The problem of nding a metamorphosis of -fold K3;3 designs into -fold 6-cycle systems was solved in [11]. The idea of metamorphosis was taken further in [91], where the problem of metamorphosis of 2-fold 4-cycle system into the maximum packing of 2-fold 6-cycle system was solved. Anm-cycle system of a graphGis said to be resolvable ifm-cycles can be partitioned into classes such that each vertex in V(G) occurs exactly once in each class. Kobayashi and Nakamura proved that there exists a resolvable covering of 2-paths by 4-cycles in Kn when n 0 (mod 4) and a nearly resolvable covering when n 2 (mod 4) in [60]. Later, in 2002, the authors [61] also constructed a resolvable covering of 2-paths by m-cycles in Kn where, n = pe + 1, p is a prime number, e 1 and m is a divisor of n, k6= 1;2. In 2009, Danziger, Mendelson and Quattrocchi [23] proved that there exists a resolvable decomposition of Kn into the union of 2-paths. Until now, we have considered the history of covering problems related to the com- plete graph and the complete multipartite graph. Now, we will turn our focus on coverings of the cartesian product of complete graphs. The Cartesian product of two graphs G1 and G2 is denoted by G1 G2 where (u;v) 2 V(G1 G2) if and only if u 2 V(G1) and v 2 V(G2), and f(u;v);(x;y)g 2 E(G1 G2) if and only if u = x and fv;yg2E(G2) or v = y and fu;xg2E(G1). One of the earliest results on the decompositions of the cartesian product of two complete graphs was by Myers [73] in 1972. He proved that product Kn Kn, is the sum of n 1 spanning cycles. In 1978, Foregger [36] proved another useful result regarding the 11 hamilton cycle systems of the cartesian product of two complete graphs. K otzig [64] proved that if G is the cartesian product of any regular graphs and one of the following conditions is true; at least one of the regular graphs has a 1-factorization or there exists at least two regular graphs containing a 1-factor then the graph G has a 1-factorization, in 1979. Wallis [90] proved that there exists a 1-factorization of the cartesian product of the Petersen graph with K3. In 1991, Stong [87] proved that the if G1 and G2 be graphs that are decompos- able into n and m Hamilton cycles, respectively, with n m. Then G1 G2 is Hamilton decomposable if one of the following holds: (1) m 3n, (2) n 3, (3) jG1j is even, or (4) jG2j 6dm=ne 3, where dxe is the least integer greater than or equal to x. Ho man and Pike [46] gave necessary and su cient conditions on n and m such that there exists a 4-cycle system of Kn Kn in 1998. Chen [18] gave the formula for obtaining the number of spanning trees in the cartesian product graph of paths (or cycles) in 2003. Farrell and Pike [29] carried forward the research of Ho man and Pike on cycle systems of the cartesian product of two complete graphs. In 2003, they gave necessary and su cient conditions for constructing a 6-cycle system of Kn Km. In Chapter 4, we give di erent and innovative constructions for the same result. In the following year Pike and Swain gave necessary and su cient condi- tions for constructing an 8-cycle system of Kn Km. Finally, Graham and Pike gave results about the maximum packings (minimum coverings) of Kn Km with 4-cycles in 2005 [39]. Fu and Huang [35] gave the conditions to nd a maximum packing of Km Kn with hexagons in 2005. In Chapter 3, we give necessary and su cient conditions for constructing the maximal fair 6-cycle system of Km Kn. We now, summarize the results mentioned in each of the following chapters to give the reader a avor of the work done by the author in this dissertation. 12 Chapter 2: In this chapter we give necessary and su cient conditions for obtaining a 6-cycle system of Km Kn which yields a 2-path covering of K(m;n). In other words, we construct a (C6;P2) 1-covering of Km Kn which leads us to a (C6;P3) 1-covering of K(m;n). We de ne the concept of fairness in order to do so. Constructing the fair 6-cycle system of Km Kn aids in the development of a 2-path covering of K(m;n). Chapter 3: After constructing a fair 6-cycle system of Km Kn in Chapter 2, we then focused our attention on the next best possible result regarding fair 6-cycle systems. So in this chapter, we give necessary and su cient conditions to construct a maximum fair 6-cycle system of Km Kn. Chapter 4: In Chapter 4, we revisited the problem of nding the 6-cycle system of Km Kn. We give necessary and su cient conditions to solve this problem using unique and innovative constructions. Chapter 5: In Chapter 5, we continued the work done by Fu and Rodger on 4-cycle systems of Kn F, where F is any 2-regular leave. Taking this result further in literature, we found necessary and su cient conditions for obtaining the 4-cycle system of Kn F , where F is any nearly 2-regular leave. This result required several constructions for small values of n, which have been explained in detail in this chapter. Chapter 6: Here we continued the work done for the author?s Masters Thesis. We continued to solve the problem of obtaining the 4-cycle system of L(K(a1;a2;:::;ap)). Some new results about this problem are given here. For the background work on this problem the readers are re ered to [76]. 13 Chapter 2 6-cycle system of the Cartesian Product of Kx Ky covering 2-paths in Kx;y 2.1 Introduction In this chapter, the bipartite graph B with the bipartition fS;Tg of V(B) is denoted by K(S;T). Let L(B) denote the line graph of B. The Cartesian product of two graphs G1 and G2 is denoted by G1 G2. The vertices of Ki Kj will be considered as an array with i rows and j columns unless otherwise stated. We can also view the line graph of B as the Cartesian product of two complete graphs Ks and Kt. A k-path is a path having k edges and is traditionally denoted by Pk+1. An m-cycle is a cycle having m edges and is denoted by Cm. Recall that (H;J) -covering of G is de ned to be a set U of copies of the subgraph H in G such that each copy of J in G is contained in exactly copies of H in the set U. The problem of nding (H;J) -coverings of G for the case when G = Kn, = 1 and J is a 2-path have been solved for the following graphs H. 1. H is a 3-path [42, 69]. 2. H is a 4-cycle [43]. 3. H is a 4-path [55, 70]. The case where G = Kn E(P) for some P wherejE(P)jis as small as possible (this is known as the packing problem) has been solved for these values of H and J in [44]. 4. H is a 5-path [58], and the case where G = K2n for these graphs H and J was solved in [57]. 5. H is a 6-path [1]. 14 6. H is a 6-cycle [59]. The problem of nding a (Cn;P3) 1-covering of Kn is equivalent to solving the Dudeney problem. In 1905, Dudeney posed the problem [26] which asks for a seating ar- rangement of n people on (n 1)(n 2)=2 days such that no person can have the same two neighbors in more than one seating arrangement. This problem was solved for the case when n is even in [53]. In this case the set U of the copies of Cn in Kn is known as the Dudeney set. It is di cult to solve this problem for the case when n is odd. Hence, the problem of obtaining a double Dudeney set, D0 was considered. A double Dudeney set is a set of hamilton cycles, Cn such that each P3 lies in exactly two hamilton cycles in D0. In other words this problem asks for a (Cn;P3) 2-covering of Kn. This problem was solved in [56]. The problem of nding a (Cn;P3) 1-covering of K2n was solved in [52]. Some embedding results have also been obtained. An (H;J) -covering, U1 of a graph G1 is said to be embedded in an (H;J) -covering, U2 of a graph G2 if the set U1 of copies of the graph H in G1 is a subset of the set U2 of the copies of the graph H in G2. The problem of embedding a (P4;P3) 1-covering of Kn or Kn p into a (P4;P3) 1-covering of Kn+m or Kn+m p, where p is a path of length 2 has been solved in [71]. There has also been some progress with respect to nding resolvable (Cm; P3) - coverings of Kn. A resolvable (H; J) -covering of G is an (H; J) -covering of G with the added condition that the set U of the copies of H can be partitioned into classes such that each vertex of G occurs in exactly one graph in each class. In [43], the authors found the necessary and su cient conditions for obtaining a resolvable (C4;P3) -covering of Kn for all . In [60], the problem of nding a resolvable (C4;P3) 1-covering of Kn was solved. This question was taken further in [61], where the authors solved the problem of obtaining a resolvable (Ck;P3) 1-covering of Kn where n = pe + 1, p is an odd prime and k is a divisor of n. A cycle in G1 G2 is said to be fair if it has at most two vertices in each row and in each column. Notions of fairness in graph decompositions have arisen in various forms, 15 such as equitable [13] and gregarious [8] decompositions. A fair 6-cycle system of a graph G is de ned to be a 6-cycle system of G in which each 6-cycle is fair. Here an added incentive is that a fair k-cycle in Ks Kt = L(K(S;T)) naturally corresponds to a cycle of length k in K(S;T) as the following shows (see Lemma 7). In this chapter, we nd necessary and su cient conditions and give the required constructions to obtain a fair (C6;P2) 1-covering of Ks Kt which yields a (C6;P3) 1-covering of K(S;T). So, the motivation behind this result was our observation that a fair 6-cycle in Ks Kt corresponds to a 6-cycle in K(S;T) which covers six 2-paths in K(S;T) corresponding to the 6 edges of the fair 6-cycle in Ks Kt, thus leading eventually to a construction of a (C6;P3) 1-covering of K(S;T). 2.2 Notation Let Ni = f1;2;:::;ig. The number of 2-paths in the graph G is denoted by P3(G). In a 2-path, say (a;b;c), the vertex, b, in the middle of the path is called the middle vertex. The number of 2-paths having their middle vertex in a set T is denoted by m(T). It will help the reader to picture the graph Ks Kt as a Zs Zt array. An edgef(u1;v1);(u2;v2)g2 E(Ks Kt) is called a horizontal edge if u1 = u2 andfv1;v2g2 E(Kt). Similarly, an edge is called a vertical edge if v1 = v2 andfu1;u2g2 E(Ks). De ne di pfi;jg = minfji jj;jp i jjg. 2.3 Preliminary Results In this section we show that there exists a fair 6-cycle system of Ks Kt for some small values of s and t. Lemma 1. There are 6-cycles in a 6-cycle system of Ks Kt Proof Lemma 2. There exists a fair 6-cycle system of K4 K4 Proof Let V(K4 K4) = Z4 Z4. There are eight 6-cycles in every 6-cycle system of K4 K4. De ne the following sets of 6-cycles, 16 C0 = f((0;j);(0;j + 1);(1;j + 1);(1;j + 2);(i;j + 2);(i;j)) j i = 2 and j2Z2 or i = 3 and j2Z4nZ2g C1 = f((3;j);(3;j + 1);(2;j + 1);(2;j + 2);(i;j + 2);(i;j)) j i = 0 and j2Z2 or i = 1 and j2Z4nZ2g Note that each 6-cycle in C0 and C1 is fair. It is easy to check that each edge of K4 K4 occurs in a 6-cycle. Thus, (V(K4 K4);[i2Z2Ci) is a fair 6-cycle system of K4 K4. Lemma 3. There exists a fair 6-cycle system of K6 K6 Proof Let V(K6 K6) = Z6 Z6. There are thirty 6-cycles in every 6-cycle system of K6 K6. To obtain the required 6-cycle system, we make use of the di erence edges in K6. We rst construct three 6-cycles using the vertical and horizontal di erence two edges only. We denote that set of 6-cycles by C0. C0 = f((i;j);(i;j + 2);(i+ 2;j + 2);(i+ 2;j + 4);(i+ 4;j + 4); (i+ 4;j)) j i = 0 andj 2f0;2;4gg Next, we construct nine 6-cycles using vertical and horizontal di erence one and two edges. We denote these by C8; C10 and C12. For each i 2f0;2;4g let Ci+8 = f((i;j);(i;j + 1);(i+ 4;j + 1);(i+ 4;j + 5);(i+ 5;j + 5); (i+ 5;j)) j j 2f0;2;4gg Now, we construct eighteen 6-cycles using the vertical and horizontal di erence one, two and three edges. Thus, we get the following sets of three cycles of length 6 each. For each i 2 Z6 let Ci+1 = f((i;j);(i;j + 1);(i+ 1;j + 1);(i+ 1;j + 3);(i+ 3;j + 3); (i+ 3;j)) j j 2f1;3;5gg Thus, we have obtained thirty 6-cycles in K6 K6. All the 6-cycles given above are fair. One can easily check that each edge of K6 K6 occurs in a 6-cycle. Hence, (V(K6 K6);[i2fZ7[f8;10;12ggCi) is a fair 6-cycle system of K6 K6. 17 Lemma 4. There exists a fair 6-cycle system of K3 K3 Proof Let V(K3 K3) = Z3 Z3. (V(K3 K3);f((0;0);(0;1);(2;1);(2;2);(1;2);(1;0)); ((0;0);(0;2);(1;2);(1;1);(2;1);(2;0));((0;1);(0;2);(2;2);(2;0);(1;0);(1;1))g) is a fair 6-cycle system of K3 K3. Lemma 5. There exists a fair 6-cycle system of K7 K7 Proof Let V(K7 K7) = Z7 Z7. There are forty-nine 6-cycles in every 6-cycle system of K7 K7. The construction for this Lemma makes use of the method of di erences. Consider the following sets of ordered triples given in Table 2.1. As unordered sets these triples would form a Steiner Triple System on seven points, so we refer to this as an ordered STS(7). These ordered triples are chosen so that they satisfy the properties P1 : For each x;y 2Z7;x6= y there is exactly one ordered triple containing x and y P2 : For each i2Z7 and for each j2Z3 there is exactly one triple containing i in position j Table 2.1: An ordered STS(7) (0,1,3) (4,5,0) (1,2,4) (5,6,1) (2,3,5) (6,0,2) (3,4,6) Making use of the ordered STS(7), we construct a 6-cycle system of K7 K7, as follows. For each ordered triple (x;y;z) in Table 2.1 we construct the following set of 6-cycles: Cx;y;z = f((0 +i;x);(0 +i;y);(1 +i;y);(1 +i;z);(3 +i;z); (3 +i;x)) j i 2 Z7g 18 Any edge in Ks Kt is of the formf(i1;x);(i2;x)gorf(i;x);(i;y)g. First consider an edge of the formf(i1;x);(i2;x)g. If di p(i1;i2) = 1;2;3, then this edge occurs in a cycle in the set Ca;b;c where x = b;c and a respectively. Such an ordered triple exists by P2. Now, consider an edge of the form f(i;x);(i;y)g. By P1 there exists exactly one ordered triple (a;b;c) such thatfx;yg fa;b;cg. Thenf(i;x);(i;y)gis in a cycle in Ca;b;c. We know that in the STS(7) each di erence edge appears exactly once and by ordering the STS(7), we ensure that each di erence edge is used once to construct a 6-cycle (this follows from the above discussion). Hence, the 6-cycles in Cx;y;z are all edge disjoint. Thus, we have obtained forty-nine 6-cycles and the reader can check that each of them is fair. Clearly, one can see that each edge of K7 K7 occurs in a 6-cycle. So, (V(K7 K7);[(x;y;z)2STS(7)Cx;y;z) is a fair 6-cycle system of K7 K7. Lemma 6. There exists a fair 6-cycle system of K9 K9 Proof Let V(K9 K9) = Z9 Z9. In every 6-cycle system of K9 K9 there are 108 6-cycles. Now, consider the following ordered Steiner Triple System on nine points, ordered STS(9) denoted in Table 2.2. These ordered triples are chosen so that they satisfy the properties P1 : For each x;y 2Z9;x6= y there is exactly one ordered triple containing x and y P2 : For each x2Z9 and for each k2f1;2;3;4g there is exactly one ordered triple (a0;a1;a2) containing x, say x = ai; such that k = di 9fai ai 1g reducing the subscript mod 3 Making use of this ordered STS(9), we obtain a 6-cycle system of K9 K9, as shown below. For each ordered triple (x;y;z) in Table 2.2, we construct the following set of 6-cycles where the calculations in the rst co-ordinate are done (mod 9). Cx;y;z = f((0 +i;x);(0 +i;y);((y x) +i;y);((y x) +i;z); ((z x) +i;z);((z x) +i;x)) j i 2 Z9g 19 Table 2.2: An ordered STS(9) (0,1,2) (0,3,6) (0,4,8) (2,6,4) (3,4,5) (1,4,7) (3,7,2) (3,1,8) (6,7,8) (2,5,8) (6,1,5) (0,7,5) Any edge in Ks Kt is of the formf(i1;x);(i2;x)gorf(i;x);(i;y)g. First consider an edge of the formf(i1;x);(i2;x)g. If di 9(i1;i2) = 1;2;3;4, then by the property P2 this edge occurs in exactly one cycle in the set Ca0;a1;a2, where x = ai such that k = di 9fai ai 1g, reducing the subscript (mod 3) respectively. Now, consider an edge of the formf(i;x);(i;y)g. By P1 there exists exactly one ordered triple (a;b;c) such that fx;yg fa;b;cg. Then f(i;x);(i;y)g is in a cycle in Ca;b;c. As seen before, each di erence edge in the STS(9) appears exactly once and by ordering the STS(9), we can ensure that each di erence edge is used once to construct a 6-cycle (follows from the construction). Hence, the 6-cycles in Cx;y;z are all edge disjoint. Thus, we get 108 6-cycles and each of these 6-cycles is fair. It is easy to check that each edge of K9 K9 occurs in a 6-cycle. Hence, (V(K9 K9);[(x;y;z)2STS(7)Cx;y;z) is a fair 6-cycle system of K9 K9. Lemma 7. There exists a fair 6-cycle system of Ks Kt if and only if there exists a (C6; P3) 1-covering of K(s; t) Proof. De ne V(Ks Kt) = Zs Zt. Now, let us we assume that there exists a fair 6-cycle system of Ks Kt, (Zs Zt; C). Any 6-cycle, c 2 C is of the form c = ((x0;y0);(x0;y1);(x1;y1);(x1;y2);(x2;y2);(x2;y0)) where xi 2 Zs; yi 2 Zt fori 2 Z3: Let c0 = (x0;y0;x1;y1;x2;y2) be the cycle in K(S;T) that corresponds to c in Ks Kt. De ne C0 = fc0 j c 2 Cg. Let (x1;x2;x3) be a P3 in K(S;T); without loss of generality we can assume that fx1;x3g Zs and x2 2 Zt. Let ci be the cycle in C containing the edge f(x1;x2);(x3;x2)g. Then since ci is fair, 20 ci = ((x1;x2);(x3;x2);(x3;x4);(x5;x4);(x5;x6);(x1;x6)) for some x5 2 V(S); and fx4;x6g V(T) Corresponding to this c, there exists c0 = (x1;x2;x3;x4;x5;x6) 2 C0. Since, each 2-path occurs in at least one 6-cycle in C0, and since each c0 covers 6 paths of length 2, it su ces to prove that 6jC0j = 6jCj = m(K(S;T)) = s t2 + t s2 So, let us count the number of fair 6-cycles in Ks Kt. jCj = st(s+t 2)=12 = s t2 +t s2 =6 Hence, proved. Now, suppose that there exists a (C6; P3) 1-covering of K(s;t). Then we will show that there exists a fair 6-cycle system of Ks Kt. By the reasoning given above each P3 in K(s;t) corresponds to an edge in Ks Kt (no two paths of length 2 correspond to the same edge in Ks Kt). Clearly, a 6-cycle in K(s;t) corresponds to a 6-cycle in Ks Kt as shown earlier and by de nition each vertex in the 6-cycle is distinct. Thus, each 6-cycle in K(s;t) corresponds to a fair 6-cycle in Ks Kt and a 1-covering of K(x;y) implies that each edge in Ks Kt is covered exactly once. Hence, if there exists a (C6; P3) 1-covering of K(s;t) then there exists a fair 6-cycle system of Ks Kt. Corollary 1. There exists a (C6;P3) 1-covering of K(4;4). Proof The proof of this Corollary follows directly by applying Lemma 2 and Lemma 7. Corollary 2. There exists a (C6;P3) 1-covering of K(6;6). Proof The proof of this Corollary follows directly by applying Lemma 3 and Lemma 7. Corollary 3. There exists a (C6;P3) 1-covering of K(7;7). 21 Proof The proof of this Corollary follows directly by applying Lemma 5 and Lemma 7. Corollary 4. There exists a (C6;P3) 1-covering of K(9;9). Proof The proof of this Corollary follows directly by applying Lemma 6 and Lemma 7. 2.4 Propositions In this section we give the generalized constructions for the results obtained in the previous section. These constructions are then used to prove our main results. Proposition 1. There exists a fair 6-cycle system of K6x K6x Proof This result will be completed in the future work. Corollary 5. There exists a (C6;P3) 1-covering of K(6x;6x) Proof The proof of this Corollary follows by using Lemma 7 and Proposition 1. Proposition 2. There exists a fair 6-cycle system of K6x+4 K6x+4 Proof This result will be completed in the future work. Corollary 6. There exists a (C6;P3) 1-covering of K(6x+ 4;6x+ 4) Proof The proof of this Corollary follows by using Lemma 7 and Proposition 2. Proposition 3. There exists a fair 6-cycle system of K6x+1 K6x+1 Proof Let V(K6x+1 K6x+1) = Z6x+1 Z6x+1. There are x(6x + 1), 6-cycles in every 6-cycle system of K6x+1 K6x+1. We know that there exists a Steiner Triple System on 6x + 1 1 (mod6) points. Now consider STS(Z6x+1). The total number of triples in this STS(6x+1) is given by = ((6x+1)(6x+1 1))=23 = (6x+1)(3x)3 = (6x+ 1)(x) 22 Using each triple in STS(Z6x+1), we construct a 6-cycle system of K6x+1 K6x+1 as follows. Let (a;b;c) be any triple in the STS(Z6x+1), then construct the following 6-cycles using it. Ca;b;c = f(i;a);(i;a+b);(i+b;a+b);(i+b;a+b+c); (i+b+c;a+b+c);(i+b+c;a)gjfori2Z6x+1g Thus, we get (6x+ 1)2(x) cycles of length 6 in K6x+1 K6x+1 by this construction. Clearly, each 6-cycle in the above given cycle system is fair. Thus, there exists a fair 6-cycle system of K6x+1 K6x+1. Corollary 7. There exists a (C6;P3) 1-covering of K(6x+ 1;6x+ 1) Proof The proof of this Corollary follows by using Lemma 7 and Proposition 3. Proposition 4. There exists a fair 6-cycle system of K6x+3 K6x+3 Proof This result will be completed in the future work. Corollary 8. There exists a (C6;P3) 1-covering of K(6x+ 3;6x+ 3) Proof The proof of this Corollary follows by using Lemma 7 and Proposition 4. 2.5 Main Results Theorem 2.1. There exists a fair 6-cycle system of Kx Ky if and only if 1. x = y 2. If x is even then, (a) x 0 (mod6) or (b) x 4 (mod6) 3. If x is odd then, (a) x 1 (mod6) or 23 (b) x 3 (mod6) Proof To prove the necessity of these conditions, we rst count the total number of 2-paths in K(X;Y). Let V(X) = f1;2:::xg and V(Y) = f1;2:::yg. Clearly, each 2-path has the middle vertex in set X or in set Y. In order to count the number of 2-paths with the middle vertex in set X, rst choose the middle vertex. Then, we have to choose two vertices from set Y to complete our path of length 2. Thus, jP3(X)j is given by = x y2 Similarly, jP3(Y)j is = y x2 So, jP3(K(X;Y))j = jP3(X)j + jP3(Y)j Thus, jP3(K(X;Y))j = (y x2 ) + (x y2 ) = xy2 (x 1 +y 1) = xy2 (x+y 2) The number of 6-cycles in a 6-cycle system of KX KY is given by = (x(y(y 1)2 ) +y(x(x 1)2 ))=6 = (xy(x+y 2))=12 Suppose, that each 6-cycle lies on the same row or column of the graph KX KY . Such a 6-cycle covers fteen 2-paths in K(X;Y). So, the total number of 2-paths covered in K(X;Y) by these types of 6-cycles is (15[(xy)(x+y 2)2 ])=66= xy(x+y 2)2 24 Hence, it is not possible, to construct the required 6-cycle system using cycles of this type. Suppose, each 6-cycle in our 6-cycle system covers 2-paths exactly once, then clearly, f(xy(x+y 2)2 )=6g = xy(x+y 2)2 So, clearly, = 6 Thus, each 6-cycle should cover exactly six distinct 2-paths. The only way to do that is if each 6-cycle is a fair 6-cycle as shown below. insert pic Such a 6-cycle covers three 2-paths with the middle vertex in set X =f1;2;:::;xgand three 2-paths with the middle vertex in set Y =f1;2;:::;yg in KX;Y . So, Number of 2-paths covered with the middle vertex in setX = Number of 2-paths covered with the middle vertex in setY Thus, jP3(X)j = jP3(Y) So, (y x2 ) = [x y2 ] ) y((x)(x 1)2 ) = x((y)(y 1)2 ) ) x 1 = y 1 ) x = y Thus, x = y, which proves the necessity of condition 1. Now, suppose that x is even, then x 0;2 or 4 (mod6). First consider the case, where x 2 (mod6), say x = 6a + 2. Then the number of cycles of length 6 in K6a+2 K6a+2 is 25 = (2(6a+ 2) (6a+2)(6a+2 1)2 )=6 = (6a+2)(6a+2)(6a+1)6 = 2(3a+1)2(3a+1)(6a+1)6 However, this is NOT an integer. So, x6= 6a + 2. Now suppose, x 0 (mod6). Say, x = 6a. Then the number of 6-cycles in K6a K6a will be given by = (2(6a) (6a)(6a 1)2 )=6 = (6a)(6a)(6a 1)6 = (a)(6a)(6a 1) Thus, it is possible for x 0 (mod6). x 4 (mod6) is also possible by a similar reasoning. This proves the necessity of condition 2. Now, suppose that x is odd, then x 1; 3 or 5 (mod6). First consider the case, where x 5 (mod6), say x = 6a+5. Then the number of cycles of length 6 in K6a+5 K6a+5 is = (2(6a+ 5) (6a+5)(6a+5 1)2 )=6 = (6a+5)(6a+5)(6a+4)6 = (6a+5)(6a+5)2(3a+2)6 However, this is NOT an integer. So, x 6= 6a + 5. But, x 1 or 3 (mod6) by similar calculations. This proves the necessity of condition 3. Now, to prove the su ciency of these conditions, we make use of the earlier results in this chapter. Suppose, that x is even, clearly x = y by condition 1. Then by condition 1, 1. x 0 (mod 6) or 2. x 4 (mod 6) Case 1 Let x 0 (mod 6), say x = 6a. Then using Proposition 1, there exists a fair 6-cycle system of K6a K6a. Case 2 Let x 4 (mod 6), say x = 6a + 4. Then using Proposition 2, there exists a fair 6-cycle system of K6a+4 K6a+4. 26 Now suppose, that x is odd and x = y (by condition 1) and by condition 3, 1. x 1 (mod 6) or 2. x 3 (mod 6) Case 1 Let x 1 (mod 6), say x = 6a + 1. Then using Proposition 3, there exists a fair 6-cycle system of K6a+1 K6a+1. Case 2 Let x 3 (mod 6), say x = 6a + 3. Then using Proposition 4, there exists a fair 6-cycle system of K6a+3 K6a+3. This proves our Theorem. Theorem 2.2. There exists a (C6;P3) 1-covering of K(x;y) if and only if 1. x = y 2. If x is even then, (a) x 0 (mod6) or (b) x 4 (mod6) 3. If x is odd then, (a) x 1 (mod6) or (b) x 3 (mod6) Proof The proof of this Theorem follows from Lemma 7, Theorem 2.1 and Corollaries 5, 6, 7, and 8. 27 Chapter 3 Maximum fair 6-cycle system of the Cartesian Product of two Complete Graphs Kx Ky 3.1 Introduction In this chapter, we nd necessary and su cient conditions for obtaining a maximal fair 6-cycle system of Ks Kt. An m-cycle is a cycle having m edges. An m-cycle system of a graph G is denoted by the ordered set (V(G);C), where V(G) is the vertex set of G and C is a set of cycles of length m that partition the edge set of G, E(G). A complete graph on s vertices is denoted by Ks. The cartesian product of two complete graphs Ks and Kt is denoted by Ks Kt. The problem of nding m-cycle systems of Ks has been solved for many values of m. For a survey of these results, we refer the reader to [79] (we will focus on the results involving 6-cycle systems in particular). D. Sotteau [84] proved a prominent result regarding m-cycle systems of K(s;t), where K(s;t) is the complete bipartite graph. A lot of work has been done on the problem for nding m-cycle systems of Ks minus some edges, called the leave. In [5], the authors found necessary and su cient conditions for obtaining a 6-cycle system of Ks E(F), where F, the leave, is any spanning forest of Ks. The problem of nding a 6-cycle system of Ks E(L), where the leave L is any 2-regular (not necessarily spanning) subgraph of Ks was solved in [6]. The spectrum problem for nding a 6-cycle system of L(Ks) was solved in [22]. An m-cycle system of a graph G, say C, is said to be maximal if E(G) E(C) does not contain an m-cycle. There have some results regarding a maximal set of m-cycle systems too. In 2000, the authors [14] found necessary and su cient conditions for obtain- ing a maximal set of hamilton cycles in K(s;s). In 2003, this problem was extended by 28 nding the maximal set of hamilton cycles in the complete multipartite graph, Kps (p parts of size s), [24]. The authors published the next part of this paper in 2007, [49]. In 2008 [33] the problem of obtaining the maximal set of hamilton cycles in K2p F was solved. The latest result with respect to maximal m-cycle systems is [74], where the problem of nding the maximal set of hamilton cycles in the directed complete graph, Ds is solved. In 2006 [37], the authors solved the problem of nding the maximal cyclic 4-cycle packings and the minimal cyclic 4-cycle coverings of Kn. The de nitions of a fair m-cycle and a fair m-cycle system of a graph G can be found in the previous chapter. A maximum fair 6-cycle system of Ks Kt, C is de ned to be a 6-cycle system of Ks Kt containing the most number of fair 6-cycles among all 6-cycle systems of Ks Kt. A 6-cycle system (V;C1) is said to be a maximum fair 6-cycle system if for each of the 6-cycle systems (V;C2) of Ks Kt, (V;C1) has at least as many fair 6-cycles as (V;C2). In the previous chapter we found the necessary and su cient conditions for obtaining a fair 6-cycle system of Ks Kt (which then gave us a (C6;P3) 1-covering of K(S;T)). So, the next natural problem to consider was to maximize the number of fair 6-cycles among the 6-cycle systems of Ks Kt. Thus, the results obtained in the previous chapter were a motivation for this chapter. In the next section of this chapter, we give the reader some useful notation. Then we give some preliminary results. Later, we give constructions for some propositions which will be used to prove our main results. Finally, we use all the tools constructed in the previous sections to prove our main Theorem. 3.2 Notation The reader should refer to the notation section of the previous chapter for the notations used in this chapter. MF(s;t) denotes the maximum number of disjoint fair 6-cycles in a 6-cycle system of Ks Kt. It will help the reader to picture the vertices of Ks Kt in an s t array in which if the vertex set M(ijNj) is used then the vertex in position (i;j) of 29 the array is x(i 1) +j. All the edges in a graph, G expect vertical and horizontal are said to be the diagonal edges. We have stated an important theorem by Sotteau that is used in our constructions below. Theorem 3.1. [84] There exists a 4-cycle system of Ka;b and of 2Ka;b if and only if each vertex has even degree, the number of edges is divisible by 4, and a;b 2. 3.3 Preliminary Results In this section we construct maximum fair 6-cycle systems of Ks Kt for some small values of s and t. Before we proceed to those constructions, we will show the method for calculating the maximum number of fair 6-cycles in a 6-cycle system of Ks Kt. Since, the case where s t is solved in the previous chapter, here we can assume that s>>> >>> >>>< >>> >>>> >>> : ((0;1);(1;1);(1;4);(2;4);(2;7);(0;7)) for i = 1 ((0;2);(1;2);(1;5);(2;5);(2;8);(0;8)) for i = 2 ((0;0);(2;0);(2;1);(4;1);(4;2);(0;2)) for i = 3 ((0;2);(2;2);(2;3);(4;3);(4;4);(0;4)) for i = 4 ((0;6);(2;6);(2;7);(4;7);(4;8);(0;8)) for i = 5 On vertical rotation each Bi gives rise to a set of corresponding fair 6-cycles Ci (say), given below: 32 Ci = 8> >>> >>>> >>> >>> >>>> >>> >>>> >>> >>>> >>< >>>> >>> >>> >>>> >>> >>>> >>> >>>> >>> >>> : S i2Z5((0 +i;0);(1 +i;0);(1 +i;3);(2 +i;3);(2 +i;6);(0 +i;6)) for i = 0 S i2Z5((0 +i;1);(1 +i;1);(1 +i;4);(2 +i;4);(2 +i;7);(0 +i;7)) for i = 1 S i2Z5((0 +i;2);(1 +i;2);(1 +i;5);(2 +i;5);(2 +i;8);(0 +i;8)) for i = 2 S i2Z5((0 +i;0);(2 +i;0);(2 +i;1);(4 +i;1);(4 +i;2);(0 +i;2)) for i = 3 S i2Z5((0 +i;2);(2 +i;2);(2 +i;3);(4 +i;3);(4 +i;4);(0 +i;4)) for i = 4 S i2Z5((0 +i;6);(2 +i;6);(2 +i;7);(4 +i;7);(4 +i;8);(0 +i;8)) for i = 5 To form the triples, we had used all the horizontal edges in K5 K9. Now, to obtain the remaining 6-cycles, we go back to the structure of M(3jZ9) and make use of the diagonal edges in that graph. And, we get 15 6-cycles, three on each of the ve rows in K5 K9 from the following cycle system. C6 = f(i;j + 6;i+ 3;j;i+ 6;j + 3) j for all (i;j) 2f(0 +k;1); (0 +k;2);(1 +k;2)g;k2Z5g Thus, (V(K5 K9);[i2Z7Ci) is a maximal fair 6-cycle system of K5 K9. Lemma 12. There exists a maximal fair 6-cycle system of K5 K21 that contains MF(5;21) fair 6-cycles Proof There are 210 6-cycles in every 6-cycle system of K5 K21. By applying Lemma 8, there are at most 70 fair 6-cycles in any maximum fair 6-cycle system of K5 K21. To construct a system with 70 fair 6-cycles, consider two parallel classes of triples on V(KZ21) = M(7jZ21). 33 1 = (Si2Z5(i;i+ 8;i+ 16) S (5;13;14) S (6;7;15)) 2 = (Si2Z8nZ3(j;j + 6;j + 12) S (10;13;19) S (1;7;20)) We use each of these triples to induce 14 base cycles ( 1 induces B0;:::;B7. And 2 induces the other seven) in K5 K21. There are 1050 horizontal edges and 210 vertical edges in K5 K21. Then we will rotate these base cycles cyclically, to get 70 fair 6-cycles in K5 K21. First, we assign subscripts to these triples to form our base cycles. These subscripts help us use the vertical edges in K5 K21. For this, let V(K5 K21) = G(Z5 Z21). 01 = (Si2Z5(i1;i+ 81;i+ 162) S (51;131;142) S (61;71;152)) 02 = (Sj2Z8nZ3(j2;j + 62;j + 121) S (102;132;191) S (12;72;201)) Now, for example, the base cycle B0 is formed from the triple (01;81;162) follows: B0 = ((0;0);(0 + 1;0);(1;0 + 8);(1 + 1;8);(2;8 + 8);(2 2;16)) The other base blocks formed similarly are listed below: Bi = 8 >>> >>>> >>> >>> >>>> >>> >>>> >>> >>>> >>> >>> < >>> >>> >>>> >>> >>>> >>> >>>> >>> >>> >>>> >>> : ((0;1);(1;1);(1;9);(2;9);(2;17);(0;17)) for i = 1 ((0;2);(1;2);(1;10);(2;10);(2;18);(0;18)) for i = 2 ((0;3);(1;3);(1;11);(2;11);(2;19);(0;19)) for i = 3 ((0;4);(1;4);(1;12);(2;12);(2;20);(0;20)) for i = 4 ((0;5);(1;5);(1;13);(2;13);(2;14);(0;14)) for i = 5 ((0;6);(1;6);(1;7);(2;7);(2;15);(0;15)) for i = 6 ((0;2);(2;2);(2;8);(4;8);(4;14);(0;14)) for i = 7 ((0;3);(2;3);(2;9);(4;9);(4;15);(0;15)) for i = 8 ((0;4);(2;4);(2;10);(4;10);(4;16);(0;16)) for i = 9 ((0;5);(2;5);(2;11);(4;11);(4;17);(0;17)) for i = 10 ((0;6);(2;6);(2;12);(4;12);(4;18);(0;18)) for i = 11 ((0;0);(2;0);(2;13);(4;13);(4;19);(0;19)) for i = 12 ((0;1);(2;1);(2;7);(4;7);(4;20);(0;20)) for i = 13 34 After vertical rotation each Bi gives rise to a set of corresponding fair 6-cycles Cj (say), given as below: Cj = 8 >>> >>>> >>> >>>> >>> >>>> >>> >>> >>>> >>> < >>> >>> >>>> >>> >>>> >>> >>> >>>> >>> >>>> : S i2Z5 ((0 +i;j);(1 +i;j);(1 +i;j + 8);(2 +i;j + 8); (2 +i;j + 16);(0 +i;j + 16)) for j 2 Z5 S i2Z5 ((0 +i;5);(1 +i;5);(1 +i;13);(2 +i;13);(2 +i;14); (0 +i;14));j = 5 S i2Z5 ((0 +i;6);(1 +i;6);(1 +i;7);(2 +i;7);(2 +i;15); (0 +i;15));j = 6 S i2Z5 ((0 +i;j 5);(2 +i;j 5);(2 +i;j + 1);(4 +i;j + 1); (4 +i;j + 7);(0 +i;j + 7)) for j 2 Z12nZ7 S i2Z5 ((0 +i;0);(2 +i;0);(2 +i;13);(4 +i;13);(4 +i;19); (0 +i;19));j = 12 S i2Z5 ((0 +i;1);(2 +i;1);(2 +i;7);(4 +i;7);(4 +i;20); (0 +i;20));j = 13 At this point, we have used up all the vertical edges in K5 K21. Now, to obtain the remaining 6-cycles, we go back to the structure of M(7 j Z21). And embed one copy of the 6-cycle system of K3 K7 corresponding to M(7 jZ21) on each of the ve rows of of K5 K21. There are 14, 6-cycles in K3 K7. Thus, we get 14 5 = 70, 6-cycles by this embedding for i2Z5. Ci+14 = 6-cycle system ofK3 K7 corresponding toM(7jZ21) on (Zi+1nZi) Z21 Then we consider the unused edges in M(7jZ21) as shown below to nish this proof. C = ((i;j + 14;i+ 7;j;i+ 14;j + 7) j ((i;j) = (m;m+ 3); m 2 Z4) S((i;j) = (m+ 4;m); m 2 Z3) C gives us 7, 6-cycles. Now, place a copy of this set of 6-cycles on each of the ve rows in K5 K21. So, let 35 C19 = 6-cycle obtained by embedding a copy of C on each of the 5 rows in K5 K21 There are, 7 5 = 35, 6-cycles in C19. C = ((i;j + 14;i+ 6;j;i+ 14;j + 8) j (i;j) = (m;m+ 1); m 2 Z6nZ1)S(0;15;13;1;14;9) S(6;14;12;0;20;8) Now, embed a copy of C in each of the ve rows in K5 K21, and call the new set of 6-cycles obtained, C20. So, C20 = 6-cycle obtained by embedding a copy of C on each of the 5 rows in K5 K21 C20 also gives us 7 5 = 35 6-cycles. So, now we have 210 6-cycles. And thus, (V(K5 K21);[i2Z21Ci) is a maximum fair 6-cycle system of K5 K21. Lemma 13. There exists a maximum fair 6-cycle system of K5 K33 that contains MF(5;33) fair 6-cycles Proof There are 495 6-cycles in every 6-cycle system of K5 K33. The maximum number of fair 6-cycles in a maximum fair 6-cycle system of K5 K33 is 330=3 = 110, using Lemma 8. To construct this maximum fair 6-cycle system, consider two parallel classes of triples on V(KZ33) = M(11jZ33). 1 = (Si2Z8(i;i+ 12;i+ 24) S (9;21;22) S (10;11;23)) 2 = (Si2Z10nZ2(j;j + 10;j + 20) S (0;21;31) S (1;11;32)) We use each of these triples to induce 22 base cycles ( 1 induces B0;:::;B11. And 2 induces the other eleven) in K5 K33. There are 2640 horizontal edges and 330 vertical edges in K5 K33. And these base fair 6-cycles are rotated cyclically, which give rise to 110 fair 6-cycles in K5 K33. First, we assign subscripts to these triples to form our base cycles, which help us use the vertical edges in K5 K33. For this, let V(K5 K33) = G(Z5 Z33). 01 = (Si2Z8(i1;i+ 121;i+ 242) S (91;211;222) S (101;111;232)) 02 = (Sj2Z10nZ2(j2;j + 102;j + 201) S (02;212;311) S (12;112;321)) Now, for example, the base cycle B0 is formed from the triple (01;121;242) follows: 36 B0 = ((0;0);(0 + 1;0);(1;0 + 12);(1 + 1;12);(2;12 + 12);(2 2;24)) The other base blocks formed similarly are listed below: Bi = 8> >>> >>>> >>> >>> >>>> >>> >>>> >>> >>>> >>> >>> >>>> >>> >>>> >>> >>>> >>> >>> >>< >>> >>> >>> >>>> >>> >>>> >>> >>>> >>> >>> >>>> >>> >>>> >>> >>>> >>> >>> >>>> >>> : ((0;1);(1;1);(1;13);(2;13);(2;25);(0;25)) for i = 1 ((0;2);(1;2);(1;14);(2;14);(2;26);(0;26)) for i = 2 ((0;3);(1;3);(1;15);(2;15);(2;27);(0;27)) for i = 3 ((0;4);(1;4);(1;16);(2;16);(2;28);(0;28)) for i = 4 ((0;5);(1;5);(1;17);(2;17);(2;29);(0;29)) for i = 5 ((0;6);(1;6);(1;18);(2;18);(2;30);(0;30)) for i = 6 ((0;7);(1;7);(1;19);(2;19);(2;31);(0;31)) for i = 7 ((0;8);(1;8);(1;20);(2;20);(2;32);(0;32)) for i = 8 ((0;9);(1;9);(1;21);(2;21);(2;22);(0;22)) for i = 9 ((0;10);(1;10);(1;11);(2;11);(2;23);(0;23)) for i = 10 ((0;2);(2;2);(2;12);(4;12);(4;22);(0;22)) for i = 11 ((0;3);(2;3);(2;13);(4;13);(4;23);(0;23)) for i = 12 ((0;4);(2;4);(2;14);(4;14);(4;24);(0;24)) for i = 13 ((0;5);(2;5);(2;15);(4;15);(4;25);(0;25)) for i = 14 ((0;6);(2;6);(2;16);(4;16);(4;26);(0;26)) for i = 15 ((0;7);(2;7);(2;17);(4;17);(4;27);(0;27)) for i = 16 ((0;8);(2;8);(2;18);(4;18);(4;28);(0;28)) for i = 17 ((0;9);(2;9);(2;19);(4;19);(4;29);(0;29)) for i = 18 ((0;10);(2;10);(2;20);(4;20);(4;30);(0;30)) for i = 19 ((0;0);(2;0);(2;21);(4;21);(4;31);(0;31)) for i = 20 ((0;1);(2;1);(2;11);(4;11);(4;32);(0;32)) for i = 21 After rotation each Bi gives rise to a set of fair 6-cycles Cj (say), given as below: 37 Cj = 8 >>> >>>> >>> >>>> >>> >>> >>>> >>> >>>> >>> >>>> >>> >>> >>>> >>> >>>> >>> >>>> >>> >>< >>> >>> >>> >>>> >>> >>> >>>> >>> >>>> >>> >>>> >>> >>> >>>> >>> >>>> >>> >>>> >>> >>> : S i2Z5((0 +i;0);(1 +i;0);(1 +i;12);(2 +i;12);(2 +i;24);(0 +i;24)); j = 0 S i2Z5((0 +i;1);(1 +i;1);(1 +i;13);(2 +i;13);(2 +i;25);(0 +i;25)); j = 1 S i2Z5((0 +i;2);(1 +i;2);(1 +i;14);(2 +i;14);(2 +i;26);(0 +i;26)); j = 2 S i2Z5((0 +i;3);(1 +i;3);(1 +i;15);(2 +i;15);(2 +i;27);(0 +i;27)); j = 3 S i2Z5((0 +i;4);(1 +i;4);(1 +i;16);(2 +i;16);(2 +i;28);(0 +i;28)); j = 4 S i2Z5((0 +i;5);(1 +i;5);(1 +i;17);(2 +i;17);(2 +i;29);(0 +i;29)); j = 5 S i2Z5((0 +i;6);(1 +i;6);(1 +i;18);(2 +i;18);(2 +i;30);(0 +i;30)); j = 6 S i2Z5((0 +i;7);(1 +i;7);(1 +i;19);(2 +i;19);(2 +i;31);(0 +i;31)); j = 7 S i2Z5((0 +i;8);(1 +i;8);(1 +i;20);(2 +i;20);(2 +i;32);(0 +i;32)); j = 8 S i2Z5((0 +i;9);(1 +i;9);(1 +i;21);(2 +i;21);(2 +i;22);(0 +i;22)); j = 9 S i2Z5((0 +i;10);(1 +i;10);(1 +i;11);(2 +i;11);(2 +i;23);(0 +i;23)); j = 10 S i2Z5((0 +i;2);(2 +i;2);(2 +i;12);(4 +i;12);(4 +i;22);(0 +i;22)); j = 11 S i2Z5((0 +i;3);(2 +i;3);(2 +i;13);(4 +i;13);(4 +i;23);(0 +i;23)); j = 12 S i2Z5((0 +i;4);(2 +i;4);(2 +i;14);(4 +i;14);(4 +i;24);(0 +i;24)); j = 13 S i2Z5((0 +i;5);(2 +i;5);(2 +i;15);(4 +i;15);(4 +i;25);(0 +i;25)); j = 14 S i2Z5((0 +i;6);(2 +i;6);(2 +i;16);(4 +i;16);(4 +i;26);(0 +i;26)); j = 15 S i2Z5((0 +i;7);(2 +i;7);(2 +i;17);(4 +i;17);(4 +i;27);(0 +i;27)); j = 16 S i2Z5((0 +i;8);(2 +i;8);(2 +i;18);(4 +i;18);(4 +i;28);(0 +i;28)); j = 17 S i2Z5((0 +i;9);(2 +i;9);(2 +i;19);(4 +i;19);(4 +i;29);(0 +i;29)); j = 18 S i2Z5((0 +i;10);(2 +i;10);(2 +i;20);(4 +i;20);(4 +i;30);(0 +i;30)); j = 19 S i2Z5((0 +i;0);(2 +i;0);(2 +i;21);(4 +i;21);(4 +i;31);(0 +i;31)); j = 20 S i2Z5((0 +i;1);(2 +i;1);(2 +i;11);(4 +i;11);(4 +i;32);(0 +i;32)); j = 21 At this point, we have used up all the vertical edges in K5 K33. Now, to obtain the remaining 6-cycles, we go back to the structure of M(11 j Z33). And embed the 6-cycle system of K3 K11 corresponding to (M(11 j Z33);[i2Z27nZ22Ci) on each of the ve rows 38 of K5 K33. There are 33 6-cycles in every 6-cycle system of K3 K11. Thus, we get 33 5 = 165 6-cycles by this embedding. For i 2 Z5 Ci+22 = 6-cycle system ofK3 K11 corresponding toM(11jZ33) on Zi+1nZi Z33 Now, we consider the unused edges in M(11jZ33) as shown below to nish this proof. C = ((i;j + 11;i+ 22;j;i+ 11;j + 22) jf((i;j) = (m;m+ 5); m 2 Z6) S((i;j) = (m;m+ 6); m 2 Z5g)) There are 11 6-cycles in C . Now we, embed one copy of C in each of the ve rows in K5 K33. C27 = 6-cycle obtained by embedding one copy of C on each of the 5 rows in K5 K33 Thus, C27 gives us 11 5 = 55 6-cycles. C = ((i;j + 22;i+ 10;j;i+ 22;j + 12) j ((i;j) = (m;m+ 1); m 2 Z10nZ1) S(0;23;21;1;22;13) S(10;22;20;0;32;12)) Now, embed one copy of C in each of the ve rows of K5 K33, to get C28. C28 = 6-cycle obtained by embedding one copy of C on each of the 5 rows in K5 K33 And, we get 11 5 = 55 6-cycles from C28. C = ((i;j + 22;i+ 10;j;i+ 22;j + 11) jf((i;j) = (m;m+ 3); m 2 Z8nZ1) S((i;j) = (m+ 8;m); m 2 Z2))g On embedding C into the ve rows in K5 K33, we get another 11 5 = 55 6-cycles, say C29. C29 = 6-cycle obtained by embedding one copy of C on each of the 5 rows in K5 K33 C = ((i;j + 22;i+ 10;j;i+ 22;j + 11) jf((i;j) = (m;m+ 3); m 2 Z8nZ1) S((i;j) = (m+ 8;m); m 2 Z2))g 39 And, nally we get, 11 5 = 55 6-cycles by embedding C in each of the ve rows in K5 K33, C30. C30 = 6-cycle obtained by embedding a copy of C on each of the 5 rows in K5 K33 Thus, we have 495 6-cycles now. Thus, (V(K5 K33);[i2Z30Ci) a maximum fair 6-cycle system of K5 K33. Lemma 14. There exists a maximum fair 6-cycle system of K3 K7 Proof There are 14, 6-cycles in every 6-cycle system of K3 K7. Let V(K3 K7) = Z3 Z7. In this case, the number of fair 6-cycles is 21=3 = 7, using Lemma 8. But, it is not possible to pull out seven fair 6-cycles in the -cycle systm of K3 K7. Thus, the maximum number of fair 6-cycles possible in the maximum fair 6-cycle system of K3 K7 is ve. Let V(K3 K7) = G(Z3 Z7). C0 =[i2Z5((0;i);(0;i+ 1);(1;i+ 1);(1;i+ 2);(2;i+ 2);(2;i)) The remaining 6-cycles in the maximum fair 6-cycle system of K3 K7 are obtained as follows: C1 = f((0;0);(0;5);(0;6);(1;6);(1;1);(1;0)); ((1;0);(1;3);(1;1);(2;1);(2;6);(2;0))g C2 = f((0;0);(0;4);(0;1);(0;5);(0;2);(0;6)); ((0;0);(0;3);(0;1);(0;6);(0;4);(0;2))g C3 = f((1;0);(1;4);(1;1);(1;5);(1;2);(1;6)); ((1;0);(1;5);(1;3);(1;6);(1;4);(1;2))g C4 = f((2;0);(2;1);(2;2);(2;3);(2;4);(2;5)); ((2;0);(2;3);(2;6);(2;5);(2;1);(2;4))g And so, (V(K3 K7);[i2Z5Ci) is a maximum fair 6-cycle system of K3 K7. 40 3.4 Proposition In this section, we give constructions for maximum fair 6-cycle systems of Ks Kt for some generalized values of s and t. Proposition 5. There exists a maximum fair 6-cycle system of K6x+1 K6x+1 Proof To nd the total number of 6-cycles in every 6-cycle system of K6x+1 K6x+1, note that there is one copy of K6x+1 on each row in K6x+1 K6x+1. And, there is one copy of K6x+1 on each column in K6x+1 K6x+1. Thus, we have 2(6x+ 1) copies of K6x+1 in our graph. So, the total number of 6-cycles in every K6x+1 K6x+1 is = 2(6x+1)(6x+1)(6x+1 1)=26 = (6x+1)(6x+1)(6x)6 = (x)(6x+ 3)(6x+ 1) Thus, there are (x)(6x+3)(6x+1) 6-cycles in K6x+1 K6x+1. And using Lemma 8, there are (x)(6x+ 3)(6x+ 1) fair 6-cycles in every maximum fair 6-cycle system of K6x+1 K6x+1. Thus, a fair 6-cycle system of K6x+1 K6x+1 is the same as the maximal fair 6-cycle system of K6x+1 K6x+1. For the construction of a maximum fair 6-cycle system of K6x+1 K6x+1, we refer the reader to the previous chapter. Proposition 6. There exists a maximum fair 6-cycle system of K6x+3 K6x+3 Proof We rst calculate the total number of 6-cycles in every 6-cycle system of K6x+1 K6x+1. There is one copy of K6x+1 on each row in K6x+3 K6x+3. And, there is one copy of K6x+1 on each column in K6x+3 K6x+3. Thus, we have 2(6x+ 3) copies of K6x+3 in our graph. So, the total number of 6-cycles in every K6x+3 K6x+3 is = 2(6x+3)(6x+3)(6x+3 1)=26 = (3)(2x+1)(6x+3)(6x+2)6 = (2x+ 1)(6x+ 3)(3x+ 1) 41 Thus, there are (2x+ 1)(6x+ 3)(3x+ 1) 6-cycles in K6x+3 K6x+3. And using Lemma 8, there are (2x + 1)(6x + 3)(3x + 1) fair 6-cycles in every maximum fair 6-cycle system of K6x+3 K6x+3. Thus, a fair 6-cycle system of K6x+3 K6x+3 is the same as the maximal fair 6-cycle system of K6x+3 K6x+3. For this construction, we refer the reader to the previous chapter. 42 Chapter 4 6-cycle system of the Cartesian Product of two Complete Graphs 4.1 Introduction All graphs considered in this chapter are simple (no loops or multiple edges) and nite. An m-cycle is de ned as a cycle on m edges. An m-cycle system of G is a set of cycles of length m, such that each edge in G is contained in exactly one cycle. Considerable amount of research has been done in nding m-cycle systems of a graph G. Initially graph theorists were interested in the case when G was the complete graph on n vertices, denoted by Kn. Alspach and Gavalas found a pivotal result on m-cycle systems of Kn and Kn I, [82]. Work has also been done in the case when the graph under consideration is the cartesian product of two graphs. In the cartesian product G1 G2, of two graphs G1 and G2, (v1;v2) is adjacent to (u1;u2) i v1 = u1 and v2 is adjacent to u2 in G2 or v2 = u2 and v1 is adjacent to u1 in G1. There are several results for the problem of nding n-cycle system of Kn Kn by [73, 36, 87]. The problem of nding a 1-factorization of Km Kn was solved by Ktzig [63] and Wallis [90]. Chen [18] solved the problem of nding the number of spanning trees in Km Kn. The problems for obtaining k-cycle systems of Km Kn has been solved for the cases when k = 4 [46],5 [72], 6 [29] and 8 [77]. Ho man et. al. solved the problem of nding the 4-cycle system of the Cartesian product of two complete graphs, [46]. The problem of packing Km Kn with k-cycles has been been solved for the cases when k = 4 [39] and 6 [35]. 43 In this chapter we nd necessary and su cient conditions for obtaining a 6-cycle system of Km Kn. Let Nx denote the rst x natural numbers. For the rest of the notations used in this chapter the reader should refer to the notation section of Chapter 2. And by de nition, a cycle system decomposes the edge set of a graph into cycles, such that each edge is contained in exactly one cycle. Here we mention some important results used in this chapter. Theorem 4.1. [84] There exists a 4-cycle system of Ka;b and of 2Ka;b if and only if each vertex has even degree, the number of edges is divisible by 4, and a;b 2. Theorem 4.2. [17] Billington?s theorem Theorem 4.3. Sajna?s theorem 4.2 Preliminary Results In this section we solve the problem for obtaining a 6-cycle system of Ks Kt for some small values of s and t. Remark 1. The number of 6-cycles in a 6-cycle system of Ks Kt is calculated as follows: jE(Ks Kt)j=6 = (t[jE(Ks)j] +s[jE(Kt)j])=6 = (t[s(s 1)2 ] +s[t(t 1)2 ])=6 Lemma 15. There exists a 6-cycle system of K2 K6 Proof Let V(K2 K6) = N12. Using Remark 1, there are 6 6-cycles in K2 K6. (V(K2 K6);f(1;3;2;4;10;7);(3;5;4;6;12;9);(1;2;8;11;5;6); (1;4;3;6;2;5);(7;11;10;9;8;12);(7;9;11;12;10;8)g) is a 6-cycle system of K2 K6. Lemma 16. There exists a 6-cycle system of K4 K6 44 Proof Let V(K4 K6) = Z4 Z6. There are 16 6-cycles in K4 K6 using Remark 1. The reader should refer to Chapter 3 for the proof of this Lemma. Lemma 17. There exists a 6-cycle system of K6 K6 Proof There are 30 6-cycles in every 6-cycle system of K6 K6. The reader should refer to the proof given in Chapter 2 for this Lemma. Lemma 18. There exists a 6-cycle system of K4 K4 Proof There are 8 6-cycles in every 6-cycle system of K4 K4. The reader should refer to the proof of this Lemma given in Chapter 2. Lemma 19. There exists a 6-cycle system of K4 K10 Proof There are 40 6-cycles in the 6-cycle system of K4 K10. The reader should refer to Chapter 3 for the proof of this Lemma. Lemma 20. There exists a 6-cycle system of K13 K13 Proof There are 338 6-cycles in the 6-cycle system of K13 K13. The proof of this Lemma is given in Chapter 2. Lemma 21. There exists a 6-cycle system of K7 K7 Proof There are 49 6-cycles in this 6-cycle system. The detailed construction for this proof is given in Chapter 2. Lemma 22. There exists a 6-cycle system of K3 K3 Proof There are 3 6-cycles in this 6-cycle system. The reader should refer to Chapter 2 for the detailed construction of this proof. Lemma 23. There exists a 6-cycle system of K3 K7 Proof Let V(K7 K7) = Z3 Z7. There are 14 6-cycles in the 6-cycle system of K3 K7, using Remark 1. In order, to obtain this cycle system, we embed one copy of K2 K6 in K3 K7. Let V(K2 K6) = Z2 Z6. The 6-cycle system of K2 K6 exists using Lemma 45 15. So, de ne C0 = 6-cycle system of Z2 Z6 as a set of 6-cycles. C0 gives rise to six cycles. Now, construct the following set of 6-cycles in K3 K7. C1 = ((0;i);(0;6);(0;i+ 1);(2;i+ 1);(2;6);(2;i)) for i2f1;3g C2 = ((0;6);(1;6);(1;1);(2;1);(2;0);(0;0)) C3 = ((0;5);(0;6);(2;6);(1;6);(1;5);(2;5)) C4 = ((1;0);(1;6);(1;2);(2;2);(2;3);(2;0)) C5 = ((1;3);(1;6);(1;4);(2;4);(2;5);(2;3)) C6 = ((2;0);(2;4);(2;1);(2;2);(2;5);(2;6)) C7 = ((2;0);(2;2);(2;4);(2;3);(2;1);(2;5)) ([i2N7Ci) gives rise to eight 6-cycles. Thus (V(K3 K7);[i2Z8Ci) is a 6-cycle system of K3 K7. Lemma 24. There exists a 6-cycle system of K3 K11. Proof Let V(K3 K11) = Z3 Z11. Using Remark 1 there are 33 6-cycles in the 6-cycle system of K3 K11. In this case, we rst embed one copy of K1 K9 in K3 K11. Let V(K1 K9) = Z1 Z9. The 6-cycle system of K1 K9 exists by Lemma 25. And using that we construct our rst set of 6-cycles, C0 = 6-cycle system of G(Z1 Z9). C0 contains 6 6-cycles. Similarly, we embed two more copies of K1 K9. First, let V(K1 K9) = (Z1nZ0) Z9. And based on this we construct a set of 6-cycles, C1 = 6-cycle system of G((Z1nZ0) Z9). Finally, we embed another copy of K1 K9 in K3 K11. And, let, V(K1 K9) = (Z2nZ1) Z9. Let the set of 6-cycles obtained from this be C2 = 6-cycle system of G((Z2nZ1) Z9). Thus, so far, we have constructed 18 6-cycles, six from each copy of K1 K9 embedded in to K3 K11. Now, we embed one copy of K3 K3 in K3 K11. The 6-cycle system of K3 K3 exists, using Lemma 22. Let V(K3 K3) = Z3 (Z11nZ8). We obtain 3 more 6-cycles from this 46 embedding, denoted by C3 = 6-cycle system of G(Z3 (Z11nZ8)). At this stage, we have 21 6-cycles. We, construct the remaining 6-cycles as shown below. C4 =f((0;i);(0;9);(0;i+ 1);(1;i+ 1);(1;9);(1;i)) j for i2f0;2;4;6gg C5 =f((1;i);(1;10);(1;i+ 1);(2;i+ 1);(2;10);(2;i)) j for i2f0;2;4;6gg C6 =f((0;i);(0;10);(0;i+ 1);(2;j + 1);(2;9);(2;j)) j for i2f0;2;4;6gg ([i2Z7nZ4Ci) contains 12 6-cycles. Thus, (V(K3 K11);[i2Z7Ci) is a 6-cycle system of K3 K11. Lemma 25. There exists a 6-cycle system of K1 K9 Proof Let (K1 K9) = Z9. There are 6 6-cycles in the 6-cycle system of K1 K9 by Re- mark 1. Thus, (Z9;f(1;8;6;0;5;2);(0;2;1;5;6;7);(0;1;3;5;7;4);(0;3;2;6;4;8);(1;6;3;8;2;7); (1;4;3;7;8;5)g) is 6-cycle system of K1 K9. Lemma 26. There exists a 6-cycle system of K5 K9 Proof There are 45 6-cycles in the 6-cycle system of K5 K9 using Remark 1. The reader should refer to Chapter 2 for the detailed construction for this Lemma. Lemma 27. There exists a 6-cycle system of K5 K21 Proof There are 210 6-cycles in the 6-cycle system of K5 K21 by Remark 1. The reader should refer to Chapter 2 for this proof. Lemma 28. There exists a 6-cycle system of K5 K33 Proof There are 495 6-cycles in the 6-cycle system of K5 K33 by Remark 1. The reader should refer to Chapter 2 for this construction. 47 4.3 Propositions In this section we give generalized constructions for obtaining 6-cycle systems of Ks Kt for some general values of s and t. Proposition 7. There exists a 6-cycle system of K6x+2 K6y Proof The number of 6-cycles in the 6-cycle system of K6x+2 K6y is given by, jE(K6x+2 K6y)j = (6x+ 2)[jE(K6y)j] + (6y)[jE(K6x+2)j] = (6x+ 2)[6y(6y 1)2 ] + (6y)[6x+2(6x+2 1)2 ] = (6x+ 2)[(3y)(6y 1)] + (6y)[(3x+ 1)(6x+ 1)] = 6(3x+ 1)(y)[(6y 1) + (6x+ 1)] = 6(3x+ 1)(y)[6y + 6x] = 36(3x+ 1)(y)[x+y] So, there are 6j36(3x + 1)(y)[x + y] = 6(3x + 1)(y)[x + y], 6-cycles in the 6-cycle system of K6x+2 K6y. Now, let V(K6x+2 K6y) = G(3x + 1;y), where each vi;j 2G(3x + 1;y) is de ned as follows: vi;j = fK2 K6 jfor all 1 i 3x+ 1; 1 j yg Using Lemma 15, there exists a 6-cycle system of K2 K6. The 6-cycle system of K2 K6 contains six 6-cycles. Thus, we get a set of 6-cycles given below. C0 = 6-cycle system of vi;j for all f1 i 3x+ 1; 1 j yg We get, 6(y)(3x + 1), 6-cycles from C0. Now, to obtain the remaining 6-cycles we observe that the following edges do not appear in any 6-cycle yet. 1. There are y2 copies of K(6;6), on each of the 6x+ 2 rows in K6x+2 K6y 2. There is one copy of K(6x+ 2) F for each of the 6y columns in K6x+2 K6y 48 Using Sotteau?s result, Theorem 4.1 there exists a 6-cycle system of K(6;6). There are six cycles of length 6, in the 6-cycle system of K(6;6). This gives us another set of 6-cycles, say C1. C1 = 6-cycle system of the y2 copies of K(6;6), on each of the 6x+ 2 rows in K6x+2 K6y There are 3y(y 1)(6x+2), 6-cycles in C1. And, there exists a 6-cycle system of K(6x+2) F, where F is a one factor of K6x+2 using Sajna?s result, Theorem 4.3. There are (x)(3x + 1), 6-cycles in the 6-cycle system of K(6x+ 2) F. Let us denote this set of 6-cycles by C2. C2 = 6-cycle system of K(6x+ 2) F one on each of the 6y columns in K6x+2 K6y We get, 6y(x)(3x+ 1) cycles of length 6, from C2. Thus, we have 6y(3x+ 1)(x+y), 6-cycles now. And, thus (G(3x+ 1;y);[i2Z3Ci) is a 6-cycle system of K6x+2 K6y. Proposition 8. There exists a 6-cycle system of K6x+4 K6y Proof Let V(K6x+4 K6y) = G(x + 2;y), where each vi;j 2G(x + 2;y) is de ned as follows: vi;j = 8 >< >: K4 K6 for (i;j) 2G(1,y);8y K6 K6 for (i;j) 2G(m,y);1 < m x+ 2 And, there exists a 6-cycle system of K4 K6 using Lemma 16. Also, there exists a 6-cycle system of K6 K6, using Lemma 17. Now, to obtain the remaining 6-cycles, we observe that the following edges do not appear in any 6-cycle yet. 1. There are y2 copies of K(6;6) on each of the 6x+ 4 rows in K6x+4 K6y 2. There are x copies of K(4;6) and x2 copies of K(6;6) on each of the 6y columns in K6x+4 K6y And using Sotteau?s result, Theorem 4.1 we know that, there exist 6-cycle systems of K(4;6) and K(6;6). Thus, there exists a 6-cycle system of K6x+4 K6y. 49 Proposition 9. There exists a 6-cycle system of K6x K6y Proof The number of 6-cycles in the 6-cycle system of K6x K6y is given by, jE(K6x K6y)j = (6x)[jE(K6y)j] + (6y)[jE(K6x)j] = (6x)[6y(6y 1)2 ] + (6y)[6x(6x 1)2 ] = (6x)[(3y)(6y 1)] + (6y)[(3x)(6x 1)] = 18xy[(6y 1) + (6x 1)] = 36xy[3y + 3x 1] So, there are 6j36xy[3y + 3x 1] = 6xy[3y + 3x 1], 6-cycles in the 6-cycle system of K6x K6y. Let V(K6x+4 K6y) = G(x;y), where each vi;j2G(x;y) is de ned as follows: vi;j = fK6 K6 jfor all 1 i x; 1 j yg Using Lemma 17 there exists a 6-cycle system of K6 K6. And, there are 30, 6-cycles in K6 K6. Let, C0 be the set of 6-cycles obtained from this. C0 = 6-cycle system of vi;j for all f1 i 3x+ 1; 1 j yg To obtain the remaining 6-cycles, we observe that the following edges do not appear in any 6-cycle yet. 1. There are y2 copies of K(6;6) on each of the 6x rows in K6x K6y 2. There are x2 copies of K(6;6) on each of the 6y columns in K6x K6y Using Sotteau?s result, Theorem 4.1 we know that there exists 6-cycle systems of K(6;6). There are 6 cycles of length 6 in the 6-cycle system of K(6;6). C1 = 6-cycle system of the y2 copies of K(6;6) on each of the 6x rows in K6x K6y Clearly, there are 18xy(y 1), 6-cycles in this set. Finally,we form our last set of 6-cycles, C2, as given below: C2 = 6-cycle system of the x2 copies of K(6;6) on each of the 6y columns in K6x K6y 50 So, we have 6xy[3x+ 3y 1], 6-cycles now. And hence, (G(x;y);[i2Z3Ci) is a 6-cycle system of K6x K6y. Proposition 10. There exists a 6-cycle system of K6x+4 K6y+4 Proof Let V(K6x+4 K6y+4) = G(x + 1;y + 1), where each vi;j 2G(x + 1;y + 1) is de ned as follows: vi;j = 8 >>> >>> >>>> < >>> >>> >>> >: K4 K6 for (i;j) 2G(m;y + 2 m), 1 m x;8y K4 K4 for (i;j) = (x+ 1;1) if x6= y K6 K4 for (i;j) = (x+ 1;1) if x = y K6 K4 for (i;j) = (x+ 1;m), 2 m y + 1 K6 K6 otherwise And, there exists 6-cycle systems of K4 K4 (using Lemma 18), K4 K6 (using Lemma 16) and K6 K6 (using Lemma 17). To obtain the remaining 6-cycles, we observe that the following edges do not appear in any 6-cycle yet. 1. There are y2 copies of K(6;6) and y copies of K(4;6) on each of the 6x + 4 rows in K6x+4 K6y+4 2. There are x2 copies of K(6;6) and x copies of K(4;6) on each of the 6y + 4 columns in K6x+4 K6y+4 And using Sotteau?s result, Theorem 4.1 we know that, there exist 6-cycle systems of K(4;6) and K(6;6). Hence, there exists a 6-cycle system of K6x+4 K6y+4. Proposition 11. There exists a 6-cycle system of K12x+1 K12y+1 Proof The number of 6-cycles in the 6-cycle system of K12x+1 K12y+1 is given by, 51 jE(K12x+1 K12y+1)j = (12x+ 1)[jE(K12y+1)j]+ (12y + 1)[jE(K12x+1)j] = (12x+ 1)[(12y+1)(12y)2 ]+ (12y + 1)[(12x+1)(12x)2 ] = (12x+ 1)[(6y)(12y + 1)]+ (12y + 1)[(6x)(12x+ 1)] = 6(12x+ 1)(12y + 1)(x+y) So, there are 6j6(12x+ 1)(12y+ 1)(x+y) = (12x+ 1)(12y+ 1)(x+y), 6-cycles in the 6-cycle system of K12x+1 K12y+1. There are 12x + 1 copies of K(12y + 1) on each of the 12x + 1 rows in K12x+1 K12y+1. The 6-cycle system of K(12yx+1) exists by Lemma 20. And there are (12y+ 1)(y), 6-cycles in the 6-cycle system of K(12y+ 1). We denote this set of 6-cycles by C0, as given below. C0 = 6-cycle system of the 12x + 1 copies of K(12y + 1) on each of the 12x + 1 rows in K12x+1 K12y+1 So, we get y(12y + 1)(12x + 1), 6-cycles in this set. Similarly, there are 12y + 1 copies of K(12x+ 1) on each of the 12y + 1 columns in K12x+1 K12y+1. And, there exists a 6-cycle system of K(12x+1) using Lemma 20. There are (12x+1)(x), 6-cycles in the 6-cycle system of K(12x+ 1). Let this set of 6-cycles be C1. C1 = 6-cycle system of the 12y+1 copies of K(12x+1) on each of the 12y+1 columns in K12x+1 K12y+1 So, we have (12x+ 1)(12y+ 1)[x+y], 6-cycles now. And so, there exists a 6-cycle system of K12x+1 K12y+1. Proposition 12. There exists a 6-cycle system of K12x+7 K12y+7 Proof The number of 6-cycles in the 6-cycle system of K12x+7 K12y+7 is given by, 52 jE(K12x+7 K12y+7)j = (12x+ 7)[jE(K12y+7)j]+ (12y + 7)[jE(K12x+7)j] = (12x+ 7)[(12y+7)(12y+7 1)2 ]+ (12y + 7)[(12x+7)(12x+7 1)2 ] = (12x+ 7)[(12y + 7)(6y + 3)]+ (12y + 1)[(12x+ 7)(6x+ 3)] = 3(12x+ 7)(12y + 7)[2x+ 2y + 2] = 6(12x+ 7)(12y + 7)[x+y + 1] So, there are 6j6(12x+7)(12y+7)[x+y+1] = (12x+7)(12y+7)[x+y+1], 6-cycles in the 6- cycle system of K12x+7 K12y+7. Let V(K12x+7 K12y+7) = G(4x+7;4y+7), where each vi;j2 G(4x+7;4y+7) is de ned as follows: vi;j = 8 >>> >>> >< >>>> >>> : K7 K7 for (i;j) = (1,1) K7 K3 for (i;j) = (1,m), 1 m 4y K3 K7 for (i;j) = (m,1), 1 m 4x K3 K3 otherwise And, there exists 6-cycle systems of K3 K3 (using Lemma 22), K3 K7 (using Lemma 23) and K7 K7 (using Lemma 21). We denote the set of 6-cycles obtained from this by C0. C0 = 6-cycle system of vi;j2G(4x+ 7;4y + 7) There are 49 + 14(4y) + 14(4x) + 3(4x)(4y), 6-cycles in C0. Now, to obtain the remaining 6-cycles, we observe that the following edges do not appear in any 6-cycle yet. 1. There is a copy of K(7;3:::3) on each of the 12x+ 7 rows in K12x+7 K12y+7 2. There is a copy of K(7;3:::3) on each of the 12y + 7 columns in K12x+7 K12y+7 And using the Billington et. al. result, Theorem 4.2 we know that, there exists 6-cycle systems of K(7;3:::;3). Also, there are (12x+ 7)[14y + 3y(4y 1)], 6-cycles in the 6-cycle system of and K(7;3:::;3). 53 C1 = 6-cycle system of K(7;3:::3) on each of the 12x+ 7 rows in K12x+7 K12y+7 Finally, C2 = 6-cycle system of K(7;3:::3) on each of the 12y+ 7 columns in K12x+7 K12y+7 There are (12y+7)[14x+3x(4x 1)], 6-cycles in C2. And so, we have (12x+7)(12y+7)[x+y+ 1], 6-cycles in all. Hence, (G(4x+ 7;4y+ 7);[i2Z3Ci) is a 6-cycle system of K12x+7 K12y+7. Proposition 13. There exists a 6-cycle system of K12x+3 K12y+3 Proof The number of 6-cycles in the 6-cycle system of K12x+3 K12y+3 is given by, jE(K12x+3 K12y+3)j = (12x+ 3)[jE(K12y+3)j]+ (12y + 3)[jE(K12x+3)j] = (12x+ 3)[(12y+3)(12y+3 1)2 ]+ (12y + 3)[(12x+3)(12x+3 1)2 ] = (12x+ 3)[(12y + 3)(6y + 1)]+ (12y + 3)[(12x+ 3)(6x+ 1)] = (12x+ 3)(12y + 3)[6x+ 6y + 2] = 18(4x+ 1)(4y + 1)[3x+ 3y + 1] So, there are 6j18(4x+ 1)(4y + 1)[3x+ 3y + 1] = 3(4x+ 1)(4y + 1)[3x+ 3y + 1], 6-cycles in the 6-cycle system of K12x+3 K12y+3. Let V(K12x+3 K12y+3) = G(4x+ 1;4y + 1), where each vi;j 2 G(4x+ 1;4y + 1) is de ned as follows: vi;j =fK3 K3 j 1 i 4x+ 1, 1 j 4y + 1g And, there exists a 6-cycle system of K3 K3, using Lemma 22. There are 3, 6-cycles in the 6-cycle system of K3 K3. Let this set of 6-cycles be C0. C0 = 6-cycle system of vi;j for f1 i 4x+ 1, 1 j 4y + 1g There are 3(4x+1)(4y+1), 6-cycles in C0. To obtain the remaining 6-cycles, we observe that, the following edges do not appear in any 6-cycle yet. 54 1. There are 12x+ 3 copies of K(3;3;:::;3), one for each of the 12x+ 3 rows in K12x+3 K12y+3 2. There are 12y + 3 copies of K(3;3;:::;3), one for each of the 12y + 3 columns in K12x+3 K12y+3 Also, there exists a 6-cycle system of K(3;3;:::;3) and K(3;3;:::;3), using the result by Billington et. al., Theorem 4.2. So, we get, C1 and C2, two sets of 6-cycles from the two corresponding types of edges given above respectively. C1 = 6-cycle system of 12x + 3 copies of K(3;3;:::;3), one for each of the 12x + 3 rows in K12x+3 K12y+3 There are (3y)(4y + 1)(12x+ 3), 6-cycles in C1. C2 = 6-cycle system of 12y + 3 copies of K(3;3;:::;3), one for each of the 12y + 3 columns in K12x+3 K12y+3 Finally, we get (3x)(4x+1)(12y+3), 6-cycles in C2. Thus we have 3(4x+1)(4y+1)[3x+3y+1], 6-cycles in all. And so, (G(4x+ 1;4y + 1);[i2Z3Ci) a 6-cycle system of K12x+3 K12y+3. Proposition 14. There exists a 6-cycle system of K12x+3 K12y+7 Proof The number of 6-cycles in the 6-cycle system of K12x+3 K12y+7 is given by, jE(K12x+3 K12y+7)j = (12x+ 3)[jE(K12y+7)j]+ (12y + 7)[jE(K12x+3)j] = (12x+ 3)[(12y+7)(12y+7 1)2 ]+ (12y + 7)[(12x+3)(12x+3 1)2 ] = (12x+ 3)[(12y + 7)(6y + 3)]+ (12y + 7)[(12x+ 3)(6x+ 1)] = (12x+ 3)(12y + 7)[6x+ 6y + 4] = 6(4x+ 1)(12y + 7)[3x+ 3y + 2] 55 So, there are 6j6(4x+ 1)(12y + 7)[3x+ 3y + 2] = (4x+ 1)(12y + 7)[3x+ 3y + 2], 6-cycles in the 6-cycle system of K12x+3 K12y+7. Now, let V(K12x+3 K12y+7) = G(4x + 1;4y + 1), where each vi;j 2 G(4x+ 1;4y + 1) is de ned as follows: vi;j = 8 >< >: K3 K7 for (i;j) = (m;1), 1 m 4x+ 1 K3 K3 otherwise And, there exists a 6-cycle system of K3 K3, using Lemma 22 and a 6-cycle system of K3 K7, using Lemma 23. There are 6, 6-cycles and 14, 6-cycles in the 6-cycle systems of K3 K3 and K3 K7 respectively. We denote this set of 6-cycles as C0. C0 = 6-cycle system of vi;j 2 G(4x+ 1;4y + 1) We get, 14(4x+1) + 3(4x+1)(4y), 6-cycles from C0. Now, to obtain the remaining 6-cycles, observe that, the following edges do not appear in any 6-cycle yet. 1. There are 12x+ 3 copies of K(7;3;:::;3), one for each of the 12x+ 3 rows in K12x+3 K12y+7 2. There are 12y + 7 copies of K(3;3;:::;3), one for each of the 12y + 7 columns in K12x+3 K12y+7 We know that, there exists a 6-cycle system of K(7;3;:::;3) using the result by Billington et. al., Theorem 4.2. Let this set of 6-cycles be C1. C1 = 6-cycle system of 12x + 3 copies of K(7;3;:::;3), one for each of the 12x + 3 rows in K12x+3 K12y+7 There are (12x+ 3)[14y+ 3y(4y 1)], 6-cycles in C1. Similarly, there exists a 6-cycle system of K(3;3;:::;3), using the result by Billington et. al., Theorem 4.2. And so, we get another set of 6-cycles, C2, given below. C2 = 6-cycle system of 12y + 3 copies of K(3;3;:::;3), one for each of the 12y + 3 columns in K12x+3 K12y+3 56 And, we get (12y+7)[(3x)(4x+1)], 6-cycles inC2. At this point, we have (4x+1)(12y+7)(3x+ 3y+ 2), 6-cycles. And so, (G(4x+ 1;4y+ 1);[i2Z3Ci) is a 6-cycle system of K12x+3 K12y+7. Proposition 15. There exists 6-cycle system of K12x+3 K12y+11 Proof The number of 6-cycles in the 6-cycle system of K12x+3 K12y+11 is given by, jE(K12x+3 K12y+11)j = (12x+ 3)[jE(K12y+11)j]+ (12y + 11)[jE(K12x+3)j] = (12x+ 3)[(12y+11)(12y+11 1)2 ]+ (12y + 11)[(12x+3)(12x+3 1)2 ] = (12x+ 3)[(12y + 11)(6y + 5)]+ (12y + 11)[(12x+ 3)(6x+ 1)] = (12x+ 3)(12y + 11)[6x+ 6y + 6] = 6(12x+ 3)(12y + 11)[x+y + 1] So, there are 6j6(12x+ 3)(12y + 11)[x+y + 1] = (12x+ 3)(12y + 11)[x+y + 1], 6-cycles in the 6-cycle system of K12x+3 K12y+11. First let V(K12x+3 K12y+11) = G(4x + 1;4y + 1), where each vi;j 2 G(4x+ 1;4y + 1) is de ned as follows: vi;j = 8> < >: K3 K11 for (i;j) = (m;1), 1 m 4x+ 1 K3 K3 otherwise And, there exists a 6-cycle system of K3 K3, using Lemma 22 containing 3, 6-cycles. And there exists a 6-cycle system of K3 K11, using Lemma 24, containing 33, 6-cycles. Let C0 be the set of 6-cycles obtained from this embedding. C0 = 6-cycle system of vi;j 2 G(4x+ 1;4y + 1) There are 33(4x + 1) + 3(4x + 1)(4y), 6-cycles in C0. In order to obtain the remaining 6-cycles, observe that, the following edges do not appear in any 6-cycle yet. 57 1. There are 12x+3 copies of K(11;3;:::;3), one for each of the 12x+3 rows in K12x+3 K12y+11 2. There are 12y + 11 copies of K(3;3;:::;3), one for each of the 12y + 11 columns in K12x+3 K12y+11 And, there exists a 6-cycle system of K(11;3;:::;3) using the result by Billington et. al., Theorem 4.2. Denote the 6-cycles obtained from this by C1. C1 = 6-cycle system of 12x + 3 copies of K(11;3;:::;3), one for each of the 12x + 3 rows in K12x+3 K12y+11 There are (12x+ 3)[22y+ 3y(4y 1)], 6-cycles in C1. Similarly, there exists a 6-cycle system of K(3;3;:::;3), using the result by Billington et. al., Theorem 4.2. Using this fact, we get another set of 6-cycles, C2, given below. C2 = 6-cycle system of 12y + 11 copies of K(3;3;:::;3), one for each of the 12y + 11 columns in K12x+3 K12y+11 Hence, we get another (12y+ 11)[(3x)(4x+ 1)], 6-cycles from C2. Now, we have the required total number of 6-cycles, (12x+ 3)(12y + 11)[x+y + 1]. Thus, (G(4x+ 1;4y + 1);[i2Z3Ci) is a 6-cycle system of K12x+3 K12y+11. Proposition 16. There exists a 6-cycle system of K12x+9 K12y+1 Proof The number of 6-cycles in the 6-cycle system of K12x+9 K12y+1 is given by, jE(K12x+9 K12y+1)j = (12x+ 9)[jE(K12y+1)j]+ (12y + 1)[jE(K12x+9)j] = (12x+ 9)[(12y+1)(12y+1 1)2 ]+ (12y + 1)[(12x+9)(12x+9 1)2 ] = (12x+ 9)[(12y + 1)(6y)]+ (12y + 1)[(12x+ 9)(6x+ 4)] = (12x+ 9)(12y + 1)[6x+ 6y + 4] = 6(4x+ 3)(12y + 1)[3x+ 3y + 2] 58 So, there are 6j6(4x+3)(12y+1)[3x+3y+2] = (4x+3)(12y+1)[3x+3y+2], 6-cycles in the 6-cycle system of K12x+9 K12y+1. There are 12x + 9 copies of K12y+1, one on each of the 12x+9 rows in K12x+9 K12y+1. We know that there exists a 6-cycle system of K12y+1, using the result by Sajna, Theorem 4.3. We denote the 6-cycles obtained from this embedding by C0. C0 = 6-cycle system of 12x + 9 copies of K12y+1, one on each of the 12x + 9 rows in K12x+9 K12y+1 And, there are y(12y + 1)(12x+ 9), 6-cycles in C0. Next, note that there are 12y + 1 copies of K12x+9, one on each of the 12y+ 1 columns in K12x+9 K12y+1. And we know that, there exist 6-cycle system K12x+9, using the result by Sajna, Theorem 4.3. Using, this fact, we get another set of 6-cycles, C1 given below. C1 = 6-cycle system of 12y + 1 copies of K12x+9, one on each of the 12y + 1 columns in K12x+9 K12y+1 We get, (12y+ 1)(4x+ 3)(3x+ 2), 6-cycles from C1. So, now we have (4x+ 3)(12y+ 1)[3x+ 3y+2], 6-cycles. Thus, by this construction there exists a 6-cycle system of K12x+9 K12y+1. Proposition 17. There exists a 6-cycle system of K12x+5 K12y+9, and 1. y 0 (mod 3) 2. y 1 (mod 3) 3. y 2 (mod 3) Proof We shall prove each of these three cases in turn. Case 1. Suppose y = 3 . First let V(K12x+5 K12y+9) = G(12x+1;4 +1), where each vi;j 2 G(12x+1;4 +1) is de ned as follows: 59 vi;j = 8> < >: K5 K9 for (i;j) = (1;m), 1 m 4 + 1 K1 K9 otherwise And, there exists a 6-cycle system of K1 K9, using Lemma 25. Also, there exists a 6-cycle system of K5 K9, using Lemma 26. Now, to obtain the remaining 6-cycles, we observe that the following edges do not appear in any 6-cycle yet. 1. There is one copy of K(9;:::;9), for each of the 12x+ 5 rows in K12x+5 K12y+9 2. There is one copy of K(5;1;:::;1) for each of the 12y+ 9 columns in K12x+5 K12y+9 And, there exists 6-cycle systems of K(9;:::;9) and K(5;1;:::;1), using the result by Billington et. al., Theorem 4.2. Hence, there exists a 6-cycle system of K12x+5 K12y+9. Case 2. For this case, let y = 3 + 1 (when y = 1, refer to Lemma 27). And let V(K12x+5 K12y+9) = (G(12x 3;4 + 1) [ G0(2;4) [ G00(3;12y + 9)), as depicted in the gure. And let each vi;j 2 G(12x 3;4 + 1) be de ned as follows: vi;j = 8 >< >: K5 K9 for (i;j) = (1;m), 1 m 4 + 1 K1 K9 for (i;j) = (p;q), 1 p 12x 3, 1 q 4 + 1 And each v0i;j 2G0(2;4) be de ned as follows: v0i;j = 8 >< >: K11 K3 for (i;j) = (1;m), 1 m 4 K3 K3 for (i;j) = (2;m), 1 m 4 Finally, each v00i;j 2G00(3;12y + 9) is de ned as follows: v00i;j =fK12y+9 j8 1 i 3, 1 j 12y + 9g 60 And, there exists 6-cycle systems of K5 K9 (using Lemma 23), K1 K9 (using Lemma 25), K3 K11 (using Lemma 24), K3 K3 (using Lemma 22) and K12y+9 (using Lemma 25). Now to obtain the remaining 6-cycles, we observe that the following edges do not appear in any 6-cycle yet. 1. There are 12x 2 copies of K(9;:::;9;3;3;3;3), one for each of the rst 12x 2 rows in K12x+5 K12y+9 2. There are 12y 3 copies of K(5;1;:::;1), one for each of the rst 12y 3 columns in K12x+5 K12y+9 3. There are 12 copies of K(11;3;1;1;1), one for each of the last 12 columns in K12x+5 K12y+9 We know that, there exists a 6-cycle systems of K(9;:::;9;3;3;3;3), K(5;1;:::;1) and K(11;3;1;1;1), using the result by Billington et. al., Theorem 4.2. Thus, there exists a 6-cycle system of K12x+5 K12y+9. Case 3. For this case, let y = 3 + 2(when y = 2, refer to Lemma 28). And let V(K12x+5 K12y+9) = (G(12x 3;4 + 1) [ G0(2;8) [ G00(3;12y + 9)), as depicted in the gure. And let each vi;j 2 G(12x 2;4 + 1) be de ned as follows: vi;j = 8 >< >: K5 K9 for (i;j) = (1;m), 1 m 4 + 1 K1 K9 otherwise And each v0i;j 2G0(2;8) be de ned as follows: v0i;j = 8 >< >: K11 K3 for (i;j) = (1;m), 1 m 8 K3 K3 for (i;j) = (a;b), a = 2, 1 b 8 61 Finally, each v00i;j 2G00(3;12y + 9) is de ned as follows: v00i;j =fK12y+9 j8 1 i 3, 1 j 12y + 9g And, there exists 6-cycle systems of K5 K9 (using Lemma 23), K1 K9 (using Lemma 25), K3 K11 (using Lemma 24), K3 K3 (using Lemma 22) and K12y+9 (using Lemma 25). Now to obtain the remaining 6-cycles, we observe that the following edges do not appear in any 6-cycle yet. 1. There are 12x+2 copies of K(9;:::;9;3;3;3;3;3;3;3;3), one for each of the rst 12x+2 rows in K12x+5 K12y+9 2. There are 4 + 1 copies of K(5;1;:::;1), one for each of the rst 4 + 1 columns in K12x+5 K12y+9 3. There are 24 copies of K(11;3;1;1;1), one for each of the last 24 columns in K12x+5 K12y+9 There exists 6-cycle systems ofK(9;:::;9;3;3;3;3;3;3;3;3), K(5;1;:::;1) andK(11;3;11;1), using the result by Billington et. al., Theorem 4.2. Hence, there exists a 6-cycle system of K12x+5 K12y+9. Proposition 18. There exists a 6-cycle system of K12x+9 K12y+9 Proof The number of 6-cycles in the 6-cycle system of K12x+9 K12y+9 is given by, jE(K12x+9 K12y+9)j = (12x+ 9)[jE(K12y+9)j]+ (12y + 9)[jE(K12x+9)j] = (12x+ 9)[(12y+9)(12y+9 1)2 ]+ (12y + 9)[(12x+9)(12x+9 1)2 ] = (12x+ 9)[(12y + 9)(6y + 4)]+ (12y + 9)[(12x+ 9)(6x+ 4)] = (12x+ 9)(12y + 9)[6x+ 6y + 8] = 18(4x+ 3)(4y + 3)[3x+ 3y + 4] 62 So, there are 6j18(4x + 3)(4y + 3)[3x + 3y + 4] = 3(4x + 3)(4y + 3)[3x + 3y + 4], 6-cycles in the 6-cycle system of K12x+9 K12y+9. There are 12x + 9 copies of K12y+9, one for each row in K12x+9 K12y+9. And there are 12y + 9 copies of K12x+9, one for each column in K12x+9 K12y+9. Also, there exist 6-cycle systems of K12x+9 and K12y+9, using Lemma 25. Based on this, we construct the following sets of 6-cycles, C0 and C1 respectively. C0 = 6-cycle system of 12x + 9 copies of K12y+9, one on each of the 12x + 9 rows in K12x+9 K12y+9 We get (12x+ 9)(4y + 3)(3y + 2), 6-cycles from C0: C1 = 6-cycle system of 12y + 9 copies of K12x+9, one on each of the 12y + 9 columns in K12x+9 K12y+9 As seen in the previous case, we get, (12y+9)(4x+3)(3x+2), 6-cycles from C1. Thus, there exists a 6-cycle system of K12x+9 K12y+9 using this embedding of K12x+9 and K12y+9. Now, we prove the main result of this chapter. Theorem 4.4. There exists a 6-cycle system of Km Kn i 1. m, n are even (a) 6 j m or 6 j n OR (b) m + n 2 (mod 3) 2. m, n are odd (a) m , n 6 0 (mod 3) then (m + n) 2 (mod 12) OR (b) m &=or n 0 (mod 3) then m + n 2 (mod 4) 63 Proof To prove the necessity of these conditions we will rst prove that either m and n are both even, or, m and n are both odd. Suppose that m and n are even and odd respectively. Say m = 2x and n = 2y + 1. Then for any v 2 V(Km Kn), deg(v) = [(2y+1-1) + (2x-1)] So, the deg(v2(Km Kn)) is odd. And, clearly to nd an m-cycle system of any graph G, all vertices in G should have even degree. So it is not possible for m and n to be even and odd respectively. Hence, either both m and n are both even or both odd. Now suppose that m and n are both even. Then, jE(Km Kn)j = m[(n)(n 1)2 ] +n[(m)(m 1)2 ] = mn(m+n 2)2 And, to obtain a 6-cycle system of Km Kn, 6jjE(Km Kn)j ) 6 j mn(m+n 2)2 So, either 1. 6jm or 6jn OR 2. m+n 2(mod3) This proves the necessity of condition 1. Now, suppose that m and n are both odd, then if 1. m;n6 0(mod3) then m+n 2(mod12) OR 2. m&=orn 0(mod3) then m+n 2(mod4) And, this proves the necessity of condition 2. To prove the su ciency, we rst consider the case when m and n are both even. Then either 64 1. 6 j m or 6 j n OR 2. m+n 2(mod3) Case 1. Suppose 6jm or 6jn then there exists a 6-cycle system of Km Kn using Propositions 7 or 8 or 9. Case 2. Suppose m + n 2(mod3) then there exists a 6-cycle system of Km Kn using Proposition 10. Now, consider the case when both m and n are odd. Then either 1. m;n6 0(mod3) then (m+n) 2(mod12) OR 2. m&=orn 0(mod3) then m+n 2(mod4) Case 1. Suppose m;n6 0(mod3) then, there exists a 6-cycle system of Km Kn using Propositions 11 or 12. Case 2. If m&=orn 0(mod3) then, there exists a 6-cycle system of Km Kn using Propositions 13, 14, 15, 16, 17 and 18. This proves our Theorem. 65 Chapter 5 Nearly 4-regular Leave of the Complete Graph on n vertices, Kn 5.1 Introduction An m-cycle system of a graph G with vertex set V(G) is an ordered pair (V(G);S), where S is a set of edge-disjoint cycles of length m, such that each edge in G is contained in exactly one cycle in S. Clearly, necessary conditions for an m-cycle system of G to exist are: m must divide jE(G) j; each vertex in G must have even degree; and if jV(G) j> 1 then jV(G) j m. The existence problem of whether these conditions are su cient was initially considered for the case where G = Kn. After many papers it was nally settled in [2, 45, 83], showing that these obvious necessary conditions are su cient. Along the way, Sotteau [84] provided necessary and su cient conditions for the case when G = K(m;n). Let xG denote the graph with vertex set V(G) in which, for all u; v 2V(G), u and v are joined by xy edges i they are joined by y edges in G. Theorem 5.1. [84] There exists a 4-cycle system of Ka;b and of 2Ka;b if and only if each vertex has even degree, the number of edges is divisible by 4, and a;b 2. To denote a 4-cycle system of Km;n with bipartitionfA;Bgwe write (K(A;B);S). Let K(a1;a2;:::;ap) denote a complete multipartite graph with p parts in which the ith part has size ai for 1 i p. The line graph of a graph G, L(G) is de ned as follows. Every edge uv 2 E(G) is a vertex in L(G) and two vertices are adjacent in L(G) if the corresponding edges in G are adjacent. The existence of m-cycle systems of L(Kn) was settled when m 2 f4;6g in [16, 19, 20]. Also, there have been some results for obtaining m-cycle systems of K(a1;a2;:::;ap), for example being settled when all parts have the same 66 size in [17] where m is even and when p is small and then: There is a companion result obtaining 4-cycle systems [78] of L(K(a1;a2:::;an)), but much remains to be done in this area. When n is even, vertices in Kn have odd degree, so a natural companion of nding m-cycle systems of G = Kn was to solve the case where G is the complete graph on n vertices with a one factor removed: Kn I, [2]. (More generally, in this context the graph induced by edges removed from Kn is called a leave). These results led to further questions, asking for which small graphs H does Kn H have an m-cycle system. Buchanan [15] solved the case where H is a 2-regular graph and m = n (i.e. hamilton cycle). A new proof of this case was provided in [12, 68]. The case when H is 2-regular and m = 3;4 and 6 were solved in [19], [32] and [6] respectively. The case where H has maximum degree 3 and m = 4 was solved in [34]. In this chapter we extend these results in literature by completely solving the case when G = Kn E(F ) where F is a nearly 2-regular leave. A graph is said to be nearly 2-regular if all vertices have degree 2 except for one which has degree k > 2 (note that F need not be a spanning subgraph). Not only is this result of interest in it?s own right in the context of the history of this problem, but, it also arose as a useful tool in studying the cycle systems of the line graphs of complete multipartite graphs. 5.2 Applications This result has direct applications to neighbor designs [75]. Consider an experiment in serology in which we arrange the antigens in a petri dish and place the antiserum in the center of that dish. Then the results of this paper can be applied to the case when we are interested in observing reactions between most pairs of antigen-antigen reactions, the omitted pairs being speci ed by the leave H. If S is a set of cycles then let E(S) denote the set of edges in the cycles in S. 67 Section 2 of this chapter deals with constructions for some small values of n and cases where F contains cycles of lengths 4 and 5. These constructions are used to obtain 4-cycle systems for the larger values of n in Section 3. Finally, in Section 4 we combine the earlier results, proving the main result of this paper, Theorem 5.2. Lemma 29. There exists a 4-cycle system of K7 - E(f(0;1;2;3;4)g) Proof. (Z7;f(0;2;4;6);(0;3;1;5);(1;4;5;6);(6;2;5;3)g) is a 4-cycle system of K7 - E(f(0,1,2,3,4)g). Lemma 30. There exists a 4-cycle system of K9 - E(f(0;1;2;3);(0;4;5;6)g) Proof. (Z9;f(0;2;4;7);(0;8;2;5);(1;3;4;6);(1;7;6;8);(1;4;8;5);(2;6;3;7);(3;5;7;8)g) is a 4-cycle system of K9 E(f(0,1,2,3),(0,4,5,6)g). Lemma 31. There exists a 4-cycle system of K9 - E(f(0;1;2;3);(4;5;6;7)g) Proof. (Z9;f(0;2;5;7);(0;4;1;6);(0;5;1;8);(1;3;8;7);(2;4;3;1);(2;6;4;8);(3;5;8;6)g) is a 4-cycle system of K9 E(f(0,1,2,3),(4,5,6,7)g). Lemma 32. There exists a 4-cycle system of K9 - E(f(0;1;2;3;4);(0;5;6;7);(0;3;6)g) Proof. (Z9;f(1;5;2;8);(1;6;2;7);(1;3;7;4);(2;0;8;4);(3;5;7;8);(4;5;8;6)g) is a 4- cycle system of K9 - E(f(0,1,2,3,4),(0,5,6,7),(0,3,6)g). Lemma 33. There exists a 4-cycle system of K9 - E(f(0;1;2;3;4);(0;5;6;7;8);(0;3;7); (0;2;6)g) Proof. (Z9;f(1;4;2;5);(1;3;6;8);(1;7;4;6);(2;7;5;8);(3;5;4;8)g) is a 4-cycle system of K9 - E(f(0,1,2,3,4),(0,5,6,7,8),(0,3,7),(0,2,6)g). Lemma 34. There exists a 4-cycle system of K11 - E(f(0;1;2;3);(0;4;5;6);(0;7;8;9); (0;2;5)g) 68 Proof. (Z11;f(1;3;9;4);(1;5;7;9);(1;7;2;6);(1;8;0;10);(2;4;3;8);(2;9;5;10); (3;5;8;6);(3;7;4;10);(4;6;10;8);(6;7;10;9))g) is a 4-cycle system of K11 - E(f(0,1,2,3),(0,4,5,6),(0,7,8,9),(0,2,5)g). Lemma 35. There exists a 4-cycle system of K13 - E(f(0;1;2;3);(0;4;5;6);(0;7;8;9); (0;10;11;12);(0;2;5);(0;8;11)g) Proof. (Z13;f(1;3;4;6);(1;4;7;5);(1;7;2;8);(1;10;2;9);(1;11;2;12);(2;4;6;8); (3;5;9;7);(3;6;10;8);(3;9;4;10);(3;11;4;12);(5;8;12;10);(5;11;6;12);(6;9;10;7); (9;11;7;12)g) is a 4-cycle system of K13 E(f(0;1;2;3);(0;4;5;6);(0;7;8;9); (0;10;11;12);(0;2;5);(0;8;11)g). We now focus on some special cases in which the nearly 2-regular leave only contains 4-cycles. Lemma 36. There exists a 4-cycle system of Kn - E(F ) where F is nearly 2-regular, n and F are chosen to be any of the following. 1. n = 9 and F consists of two 4-cycles, all of which intersect precisely in the vertex 1. 2. n = 17 and F consists of ve 4-cycles, all of which intersect precisely in the vertex 1. 3. n = 25 and F consists of seven 4-cycles, all of which intersect precisely in the vertex 1. 4. n = 25 and F consists of eight 4-cycles, all of which intersect precisely in the vertex 1. Proof. We will consider these four cases in turn. 1. Let V(Kn) = Z8Sf1g. De ne F i = (1, 3i, 3i + 1, 3i +2) for each i Z2 69 and F = ([i Z2F i ) Let (Z8[f1g;C0) be a 4-cycle system of K9 E(F ) (see Lemma 30). 2. Let V(Kn) = Z16Sf1g. De ne F i = (1, 3i, 3i + 1, 3i +2) for each i Z5 and F = ([i Z5F i ) Let (Z6 [f1;7;10g;C0) be a 4-cycle system of K9 E(F 0 [F 1 ) (see Lemma 30). Similarly, let (((Z16nZ6)[f1g), C1) be a 4-cycle system ofK11 E(F 2[F 3[f1;7;10g) (see Lemma 34). Now, let (K(Z6, ([x fZ5nZ2g[f15gf3x;3x+2g)), C2) be a 4-cycle system of K(6, 8), using Theorem 5.1. Then ([i Z3Ci) is a 4-cycle system of K17 E(F ). 3. Let V(Kn) = Z24Sf1g. De ne F i = (1, 3i, 3i + 1, 3i +2) for each i Z7 and F = ([i Z7F i ) Let (Z15[f1;21g;C0) be a 4-cycle system of K17 E([i Z5F i ) (see Lemma 36(2)). Similarly, let (((Z24[f1g)n(Z15[f21g)), C1) be a 4-cycle system ofK9 E([i Z7nZ5F i ) (see Lemma 30). Now, let (K((Z24n(Z15[f21g)),(Z15[f21g)), C2) be a 4-cycle system of K(8, 16), using Theorem 5.1. Then ([i Z3;Ci) is a 4-cycle system of K25 E(F ). 4. Let V(Kn) = Z24Sf1g. De ne 70 Fi = (1, 3i, 3i + 1, 3i +2) for each i Z8 and F = ([i Z8F i ) Let (Z6[f1;13;16g;C0) be a 4-cycle system of K9 E(F 0 [F 1 ) (see Lemma 30). Similarly, let (((Z12nZ6) [f1;19;22g);C1) be a 4-cycle system of K9 E(F 2 [F 3 ) (see Lemma 30). Let ((Z24nZ12[f1g);C2) be a 4-cycle system of K13 E([i Z8nZ4 (F i ) [j f4;6g(1, 3j + 1, 3(j +1) +1)) (see Lemma 35). Using Theorem 5.1, (K(([x Z8nZ4f3x;3x+ 2g);(Z12));C3) be a 4-cycle system ofK(8, 12). Similarly, (K(Z6[f13;16g;[x Z4nZ2f3x;3x+ 1;3x+ 2g);C4 ) be a 4-cycle system of K(6, 8). Finally, let (K(f19, 22g, Z6), C5) is a 4-cycle system of K(2, 6). Then ([i Z6Ci) is a 4-cycle system of K25 - E(F ). Lemma 37. There exists a 4-cycle system of Kn E(F ) where F is nearly 2-regular, n and F are chosen to be any of the following. 1. n = 9 and F consists of two vertex disjoint 4-cycles, one of which contains the vertex 1. 2. n = 17 and F consists of four 4-cycles, three of which intersect precisely in the vertex 1 and the other cycle does not contain 1. 3. n = 17 and F consists of ve 4-cycles, four of which intersect precisely in the vertex 1 and the other cycle does not contain 1. 4. n = 25 and F consists of seven 4-cycles, six of which intersect precisely in the vertex 1 and the other cycle does not contain 1. Proof. We will consider these four cases in turn. 1. Let V(Kn) = Z8Sf1g. De ne 71 F i = 8 >< >: (1;0;1;2) for i = 0; (3;4;5;6) for i = 1 and F = ([i Z2F i ) Let (Z8[f1g;C0) be a 4-cycle system of K9 E(F ) (see Lemma 31). 2. Let V(Kn) = Z16Sf1g. De ne Fi = (1, 3i, 3i + 1, 3i +2) for each i Z3 and F = (([i Z3(F i ))[(9;10;11;12)) Let (Z14nZ6[f1g;C0) be a 4-cycle system of K9 E(F2 [(9;10;11;12)) (see Lemma 31). Similarly, let ((Z6[f1;14;15g), C1) be a 4-cycle system of K9 E([i Z2F i ) (see Lemma 30). Now, let (K((Z14nZ6), (Z6[f14;15g)), C2) be a 4-cycle system of K(8, 8), using Theorem 5.1. Then ([i Z3Ci) is a 4-cycle system of K17 E(F ). 3. Let V(Kn) = Z16Sf1g. De ne F i = (1, 3i, 3i + 1, 3i +2) for each i Z4 and F = (([i Z4(F i ))[(12;13;14;15)) Let (Z6[f1;12;14g;C0) be a 4-cycle system of K9 E(F 0[F 1 ) (see Lemma 30). Sim- ilarly, let (((Z12nZ6)[f1;13;15g);C1) be a 4-cycle system of K9 E([i Z4nZ2F i ) (see Lemma 30). Using Theorem 5.1, let (K(f12;14g;(Z12nZ6));C2) be a 4-cycle system 72 of K(2, 6). Similarly, (K(f13;15g;Z6);C3) be a 4-cycle system of K(2, 6). Also, let (K(Z6;Z12nZ6);C4) be a 4-cycle system of K(6,6). Then ([i Z5Ci) is a 4-cycle system of K17 E(F ). 4. Let V(Kn) = Z24Sf1g. De ne F i = (1, 3i, 3i + 1, 3i +2) for each i Z6 and F = (([i Z6(F i ))[ (18, 19, 20, 21)) Let (Z6[f1;18;20g;C0) be a 4-cycle system of K9 E(F 0[F 1 ) (see Lemma 30). Sim- ilarly, let (((Z12nZ6)[f1;19;21g);C1) be a 4-cycle system of K9 E([i Z4nZ2F i ) (see Lemma 30). Let ((Z18nZ12)[f1;22;23g;C2) be a 4-cycle system of K9 E([i Z6nZ4F i ) (see Lemma 30). Now, let (K(f18;20g;(Z12nZ6)),C3) be a 4-cycle system of K(2, 6), using Theorem 5.1. Similarly, (K(f19, 21g, Z6);C4) be a 4-cycle system of K(2, 6). And, let (K((Z18nZ12[f22;23g);(Z12[f18;19;20;21g));C5) be a 4-cycle system of K(8, 16). Finally, let (K(Z6;Z12nZ6);C6) be a 4-cycle system of K(6,6). Then ([i Z7;Ci) is a 4-cycle system of K25 E(F ). Now we turn to the cases in which all cycles in the nearly 2-regular leave have size 5. Lemma 38. There exists a 4-cycle system of Kn E(F ) where F is a nearly 2-regular leave, n and F are chosen to be any of the following. 1. n = 7 and F consists of one 5-cycle which contains the vertex 1. 2. n = 17 and F consists of four 5-cycles, all of which intersect precisely in the vertex 1. Proof. We will consider these two cases in turn. 73 1. Let V(Kn) = Z6Sf1g. De ne F 0 = (1, 0, 1, 2) and F = (F 0 ) Let (Z6[f1g;C0) be a 4-cycle system of K7 E(F ) (see Lemma 29). 2. Let V(Kn) = Z16Sf1g. De ne F i = (1, 4i, 4i + 1, 4i +2, 4i + 3) for each i Z4 and F = ([i Z4F i ) Let (Z4[f1;9;13g;C0) be a 4-cycle system of K7 E(F 0 ) (see Lemma 29). Similarly, let (((Z8nZ4)[f1;10;14g);C1) be a 4-cycle system of K7 E(F 1 ) (see Lemma 29). Let ((Z16nZ8)[f1g;C2) be a 4-cycle system of K9 E([i Z4nZ2F i[(1, 9, 13)[(1, 10, 14)) (see Lemma 33). Now, let (K((Z8nZ4);(Z4[f9;13g));C3) be a 4-cycle system of K(4, 6), using Theorem 5.1. Similarly, let (K(f14, 10g, Z4);C4) be a 4-cycle system of K(2, 4). Finally, let (K((f8;11;12;15g);Z8);C5) be a 4-cycle system of K(4, 8). Then ([i Z6;Ci) is a 4-cycle system of K17 E(F ). Lemma 39. There exists a 4-cycle system of Kn E(F ) where F is a nearly 2-regular leave, n and F are chosen to be any of the following. 1. n = 29 and F consists of six 5-cycles, two of which intersect precisely in the vertex 1 and the other cycles do not contain 1. 2. n = 35 and F consists of seven 5-cycles, two of which intersect precisely in the vertex 1 and the other cycles do not contain 1. 74 3. n = 41 and F consists of eight 5-cycles, two of which intersect precisely in the vertex 1 and the other cycles do not contain 1. 4. n = 47 and F consists of nine 5-cycles, two of which intersect precisely in the vertex 1 and the other cycles do not contain 1. Proof. We will consider these four cases in turn. 1. Let V(Kn) = Z28Sf1g. De ne F i = 8 >< >: (1;4i;4i+ 1;4i+ 2;4i+ 3) for each i Z2; (i;i+ 1;i+ 2;i+ 3;i+ 4) for each i f8;13;18;23g; G i = (8;i;i+ 1;i+ 2;i+ 3) for each i f9;14;19;24g, and F = (([i Z2[f8;13;18;23g(F i )) Let (Z28n(Z8[f13;18;23g);C0) be a 4-cycle system of K17 E([i f9;14;19;24gG i) (see Lemma 38(2)). Let ((Z9[f13;18;23;1g);C1) be a 4-cycle system of K13 E([i Z2F i[ f1;13;18;23g) (see Lemma 13(5)). And, let (K(Z9[f13;18;23g); (Z28n(Z8[f8;13;18;23g)));C2) be a 4-cycle system of K(12, 16), using Theorem 5.1. Then (([i Z3Ci)[(8;13;18;23)[f(14;8;17;0);(19;8;22;0);(24;8;27;0)gnf(14;13;17;0); (19;18;22;0);(24;23;27;0)g be a 4-cycle system of K29 E(F ). 2. Let V(Kn) = Z34Sf1g. De ne F i = 8> < >: (5i;5i+ 1;5i+ 2;5i+ 3;5i+ 4) for each i Z5 (1;4i+ 1;4i+ 2;4i+ 3;4i+ 4) for each i Z8nZ6 and F = ([i Z7nf5g(F i )) 75 Let (Z20[(Z33nZ25)[f1g;C0) be a 4-cycle system ofK29 E([i Z8nf4;5gF i ) (see Lemma 39(1)). Similarly, let (((Z25nZ20)[f1;33g);C1) be a 4-cycle system of K7 E(F 4 ) (see Lemma 29). Now, let (K(((Z25nZ20)[f33g);(Z20[(Z33nZ25)));C2) be a 4-cycle system of K(6, 28), using Theorem 5.1. Then ([i Z3;Ci) is a 4-cycle system of K35 E(F ). 3. Let V(Kn) = Z40Sf1g. De ne F i = 8> < >: (5i;5i+ 1;5i+ 2;5i+ 3;5i+ 4) for each i Z6 (1;4i 2;4i 1;4i;4i+ 1) for each i Z10nZ8 and F = ([i Z10nf6;7g(F i )) Let (Z25[(Z39nZ30)[f1g;C0) be a 4-cycle system of K35 E([i Z10nf5;6;7gF i ) (see Lemma 39(2)). Similarly, let (((Z30nZ25)[f1;39g);C1) be a 4-cycle system of K7 E(F 5 ) (see Lemma 29). Now, let (K(((Z30nZ25)[f39g); (Z25[(Z39nZ30)));C2) be a 4-cycle system of K(6, 34), using Theorem 5.1. Then ([i Z3Ci) is a 4-cycle system of K41 E(F ). 4. Let V(Kn) = Z46Sf1g. De ne F i = 8 >< >: (5i;5i+ 1;5i+ 2;5i+ 3;5i+ 4) for each i Z7 (1;4i 1;4i;4i+ 1;4i+ 2) for each i Z11nZ9 and F = ([i Z11nf7;8g(F i )) Let (Z30[(Z45nZ35)[f1g;C0) be a 4-cycle system of K41 E([i Z11nf6;7;8gF i ) (see Lemma 39(3)). Similarly, let (((Z35nZ30)[f1;45g);C1) be a 4-cycle system of K7 E(F 6 ) (see Lemma 29). Now, let (K(((Z35nZ30)[f45g);(Z30[(Z45nZ35)));C2) be a 4-cycle system of K(6, 40), using Theorem 5.1. Then ([i Z3Ci) is a 4-cycle system of K47 E(F ). 76 Lemma 40. There exists a 4-cycle system of Kn E(F ) where F is a nearly 2-regular leave, n and F are chosen to be any of the following. 1. n = 23 and F consists of ve 5-cycles, three of which intersect precisely in the vertex 1 and the other cycles do not contain 1. 2. n = 29 and F consists of six 5-cycles, three of which intersect precisely in the vertex 1 and the other cycles do not contain 1. 3. n = 35 and F consists of seven 5-cycles, three of which intersect precisely in the vertex 1 and the other cycles do not contain 1. 4. n = 41 and F consists of eight 5-cycles, three of which intersect precisely in the vertex 1 and the other cycles do not contain 1. Proof. We will consider these four cases in turn. 1. Let V(Kn) = Z22Sf1g. De ne F i = 8 >< >: (5i;5i+ 1;5i+ 2;5i+ 3;5i+ 4) for each i Z2; (1;4i 2;4i 1;4i;4i+ 1) for each i Z6nZ3, G i = (1;i;i+ 1;i+ 2;i+ 3) for each i f1;6;10;14g, and F = ([i Z6nf2gF i ) Let (((Z18 [f1g)nf0;5g);C0) be a 4-cycle system of K17 E([i f1;6;10;14gG i) (see Lemma 38(2)). And, ((Z22nZ18)[f1;0;5g);C1) be a 4-cycle system of K7 E(F 5 ) (see Lemma 29). (K(((Z22nZ18)[f0;5g);Z18nf0;5g);C2) be a 4-cycle system of K(6, 16), using Theorem 5.1. Then, (([i Z3Ci)[f(1;5;4;1);(6;0;9;1)gnf(1;5;4;0);(6;0;9;5)g is a 4-cycle system of K23 E(F ). 2. Let V(Kn) = Z28Sf1g. De ne 77 F i = 8 >< >: (5i;5i+ 1;5i+ 2;5i+ 3;5i+ 4) for each i Z3, (1;4i 1;4i;4i+ 1;4i+ 2) for each i Z7nZ4, and F = ([i Z7nf3g(F i )) Let (Z10[(Z27nZ15)f1g;C0) be a 4-cycle system of K23 E([i Z7nf2;3gF i ) (see Lemma 40(1)). Similarly, let (((Z15nZ10)[1;27g);C1) be a 4-cycle system of K7 E(F 2 ) (see Lemma 29). Now, let (K(((Z15nZ10)[f27g); (Z10[(Z27nZ15)));C2) be a 4-cycle system of K(6, 22), using Theorem 5.1. Then ([i Z3Ci) is a 4-cycle system of K29 E(F ). 3. Let V(Kn) = Z34Sf1g. De ne F i = 8> < >: (5i;5i+ 1;5i+ 2;5i+ 3;5i+ 4) for each i Z4, (1;4i;4i+ 1;4i+ 2;4i+ 3) for each i Z8nZ5, and F = ([i Z8nf4g(F i )) Let (Z15[(Z33nZ20)f1g;C0) be a 4-cycle system of K29 E([i Z8nf3;4gF i ) (see Lemma 40(2)). Similarly, let (((Z20nZ15)[f1;33g);C1) be a 4-cycle system of K7 E(F 3 ) (see Lemma 29). Now, let (K(((Z20nZ15)[f33g); (Z15[(Z33nZ20)));C2) be a 4-cycle system of K(6, 28), using Theorem 5.1. Then ([i Z3;Ci) is a 4-cycle system of K35 E(F ). 4. Let V(Kn) = Z40Sf1g. De ne F i = 8> < >: (5i;5i+ 1;5i+ 2;5i+ 3;5i+ 4) for each i Z5, (1;4i 3;4i 2;4i 1;4i) for each i Z10nZ7, and F = ([i Z10nf5;6g(F i )) 78 Let (Z20[(Z39nZ25)[f1g;C0) be a 4-cycle system of K35 E([i Z10nf4;5;6gF i ) (see Lemma 39(3)). Similarly, let (((Z25nZ20)[f1;39g);C1) be a 4-cycle system of K7 E(F 4 ) (see Lemma 29). Now, let (K(((Z25nZ20)[f39g);(Z20[(Z39nZ25)));C2) be a 4-cycle system of K(6, 34), using Theorem 5.1. Then ([i Z3Ci) is a 4-cycle system of K41 E(F ). Finally, we turn to some small cases where the nearly 2-regular leave contains both 4-cycles and 5-cycles. Lemma 41. There exists a 4-cycle system of Kn E(F ) where F is a nearly 2-regular leave which consists of x 4-cycles and y5-cycles each intersecting in precisely the vertex 1 where n, x 8 and y 4 can be chosen to be any of the following. 1. n = 23, x = 6 and y = 1. 2. n = 21, x = 4 and y = 2. 3. n = 19, x = 2 and y = 3. 4. n = 15, x = 3 and y = 1. 5. n = 13, x = 1 and y = 2. 6. n = 35, x = 7 and y = 3. 7. n = 29, x = 6 and y = 2. 8. n = 27, x = 4 and y = 3. 9. n = 23, x = 5 and y = 1. 10. n = 21, x = 3 and y = 2. 11. n = 19, x = 1 and y = 3. Proof. We will consider these eleven cases in turn. 79 1. Let V(Kn) = Z22Sf1g. De ne F i = 8 >< >: (1;3i;3i+ 1;3i+ 2) for each i Z6 (1;18;19;20;21) for i = 6 and F = ([i Z7 (F i )) Let (Z6 [f1;7;10g;C0) be a 4-cycle system of K9 E([i Z2F i ) (see Lemma 30). Similarly, let (((Z22nZ18)[f1;13;16g);C1) be a 4-cycle system of K7 E(F6 ) (see Lemma 29). And (((Z18nZ6)[f1g);C2) be a 4-cycle system of K13 E([i Z6nZ2(F i )[ (1;7;10)[(1;13;16)) (see Lemma 35). Now, let (K(f18, 19, 20, 21g, Z18nf13;16g);C3) be the 4-cycle system of K(4, 16), using Theorem 5.1. Similarly, (K(Z6;Z18n(Z6 [ f7;10g));C4) be a 4-cycle system of K(6, 10). Then ([i Z5Ci) is a 4-cycle system of K23 E(F ). 2. Let V(Kn) = Z20Sf1g. De ne F i = 8 >>> >< >>> >: (1;3i;3i+ 1;3i+ 2) for each i Z4 (1;12;13;14;15) for i = 4 (1;16;17;18;19) for i = 5 and F = ([i Z6 (F i )) Let (Z16nZ12 [f1;1;4g;C0) be a 4-cycle system of K7 E(F 4 ) (see Lemma 29). Similarly, let (((Z20nZ16)[f1;7;10g);C1) be a 4-cycle system of K7 E(F 5 ) (see Lemma 29). And (((Z12 [f1g);C2) be a 4-cycle system of K13 E([i Z4 (F i )[ (1;1;4)[(1;7;10)) (see Lemma 35). Now, let (K(f16, 17, 18, 19g, Z16nf7;10g);C3) be a 4-cycle system of K(4, 14), using Theorem 5.1. Similarly, (K(f12, 13, 14, 15g, 80 Z12nf1;4g);C4) be a 4-cycle system of K(4, 10). Then ([i Z5Ci) is a 4-cycle system of K21 E(F ). 3. Let V(Kn) = Z18Sf1g. De ne F i = 8> >>> >>>< >>> >>>> : (1;3i;3i+ 1;3i+ 2) for each i Z2 (1;6;7;8;9) for i = 2 (1;10;11;12;13) for i = 3 (1;14;15;16;17) for i = 4 and F = ([i Z5;(F i )) Let (Z6 [f1;11;16g;C0) be a 4-cycle system of K9 E([i Z2F i ) (see Lemma 30). Similarly, let (((Z10nZ6)[f1;12;15g);C1) be a 4-cycle system of K7 E(F 2 ) (see Lemma 29). And (((Z18nZ10)[f1g);C2) be a 4-cycle system of K9 E(F 3 [F 4 [ (1;10;15)[(1;11;16)) (see Lemma 33). Now, let(K(Z6;Z18n(Z6[f11;16g));C3) be a 4-cycle system of K(6, 10), using Theorem 5.1. Similarly, (K(f6, 7, 8, 9g, Z18n(Z10[ f12;15g));C4) be a 4-cycle system of K(4, 6). Then ([i Z5;Ci) is a 4-cycle system of K19 E(F ). 4. Let V(Kn) = Z14Sf1g. De ne F i = 8 >< >: (1;3i;3i+ 1;3i+ 2) for each i Z3 (1;9;10;11;12) for i = 3 and F = ([i Z4 (F i )) Let (Z6 [f1;7;10g;C0) be a 4-cycle system of K9 E([i Z2F i ) (see Lemma 30). Similarly, let (((Z14nZ6)[f1g);C1) be a 4-cycle system of K9 E(F 2[F 3[(1;7;10)) 81 (see Lemma 32). Now, let (K(Z6;Z14n(Z6[f7;10g));C2) be a 4-cycle system of K(6, 6), using Theorem 5.1. Then ([i Z3;Ci) is a 4-cycle system of K15 E(F ). 5. Let V(Kn) = Z12Sf1g. De ne F i = 8> < >: (1;4i;4i+ 1;4i+ 2;4i+ 3) for each i Z2 (1;8;9;10) for i = 2 and F = ([i Z3 (F i )) Let (Z4[f1;6;9g;C0) be a 4-cycle system of K7 E(F 0 ) (see Lemma 29). Similarly, let (((Z12nZ4)[f1g);C1) be a 4-cycle system of K9 E((F 1 [F 2 )[(1;6;10)) (see Lemma 32). Now, let (K(Z4;Z12n(Z4[f6;9g));C2) be a 4-cycle system of K(4, 6), using Theorem 5.1. Then ([i Z3;Ci) is a 4-cycle system of K13 E(F ). 6. Let V(Kn) = Z34Sf1g. De ne F i = (1;3i;3i+ 1;3i+ 2) for each i Z7 G i = (1;4i+ 1;4i+ 2;4i+ 3;4i+ 4) for each i Z8nZ5 and F = (([i Z7 (F i )) [ ([i Z8nZ5(G i))) Let (Z6 [f1;19;22g;C0) be a 4-cycle system of K9 E([i Z2F i ) (see Lemma 30). Similarly, let (((Z25nZ18)[f1;33g);C1) be a 4-cycle system of K9 E(F 6 [G 5 [ f1;19;22g) (see Lemma 32). And (((Z29nZ25)[f1;7;13g);C2) be a 4-cycle system of K7 E(G 6) (see Lemma 29). Also, let (((Z33nZ29)[f1;10;16g);C3) be a 4-cycle system of K7 E(G 7) (see Lemma 29). Let (((Z18nZ6) [f1g);C4) be a 4-cycle system of K13 E(([i Z6nZ2F i )[f1;7;13g[f1;10;16g) (see Lemma 35). Now, let (K(Z6;Z34n(Z6[f19;22g));C5) be a 4-cycle system of K(6, 26), using Theorem 5.1. 82 Similarly, (K((Z25nZ18)[f33g;Z33n(Z6[(Z25nZ18)));C6) be a 4-cycle system of K(8, 20). And (K((Z29nZ25);((Z18nZ6)[(Z33nZ29)));C7) be a 4-cycle system of K(4, 16). Finally, let (K((Z33nZ29);(Z18n(Z6[f7;10;13;16g)));C8) be a 4-cycle system of K(4, 8). Then ([i Z9;Ci) is a 4-cycle system of K35 E(F ). 7. Let V(Kn) = Z28Sf1g. De ne F i = (1;3i;3i+ 1;3i+ 2) for each i Z6 G i = (1;4i 2;4i 1;4i;4i+ 1) for each i Z7nZ5 and F = (([i Z6 (F i )) [ ([i Z7nZ5 (G i))) Let (Z22nZ18 [f1;1;7g;C0) be a 4-cycle system of K7 E(G 5) (see Lemma 29). (Z26nZ22[f1;4;10g;C1) be a 4-cycle system of K7 E(G 6) (see Lemma 29). Similarly, let (((Z18nZ12)[f1;26;27g);C2) be a 4-cycle system of K9 E([i Z6nZ4F i ) (see Lemma 30). (Z12[f1g;C3) be a 4-cycle system of K13 E([i Z4F i[(1;4;10)[(1;1;7)) (see Lemma 35). Using Theorem 5.1, let (K((Z22nZ18);(Z28n((Z22nZ18)[f1;7g)));C4) be a 4-cycle system of K(4, 22). And, (K((Z26nZ22);((Z18nf10;14g)[f26;27g));C5) be a 4-cycle system of K(4, 16). Similarly, (K((Z18nZ12)[f26;27g;Z12);C6) be a 4-cycle system of K(8, 12). Then ([i Z7Ci) is a 4-cycle system of K29 E(F ): 8. Let V(Kn) = Z26Sf1g. De ne F i = (1;3i;3i+ 1;3i+ 2) for each i Z4 G i = (1;4i;4i+ 1;4i+ 2;4i+ 3) for each i Z6nZ3 and F = (([i Z4 (F i )) [ ([i Z6nZ3 (G i))) 83 Let (Z16nZ12 [f1;1;7g;C0) be a 4-cycle system of K7 E(G 3) (see Lemma 29). (Z20nZ16[f1;4;10g;C1) be a 4-cycle system of K7 E(G 4) (see Lemma 29). Similarly, let (((Z24nZ20)[f1;24;25g);C2) is a 4-cycle system of K7 E(G 5) (see Lemma 29). (Z12[f1g;C3) be a 4-cycle system of K13 E([i Z4F i [(1;1;7)[(1;4;10)) (see Lemma 35). Using Theorem 5.1, let (K((Z16nZ12);(Z26n((Z16nZ12)[f1;7g)));C4) be a 4-cycle system of K(4, 20). And, (K((Z20nZ16);Z26n((Z20nZ12)[f4;10g));C5) be a 4-cycle system of K(4, 16). Similarly, (K((Z26nZ20);Z12);C6) is a 4-cycle system of K(6, 12). Then ([i Z7;Ci) is a 4-cycle system of K27 E(F ). 9. Let V(Kn) = Z22Sf1g. De ne F i = 8 >< >: (1;3i;3i+ 1;3i+ 2) for each i Z5 (1;15;16;17;18) for i = 5 and F = ([i Z6 (F i )) Let (Z6 [f1;13;16g;C0) be a 4-cycle system of K9 E([i Z2F i ) (see Lemma 30). (Z20nZ12 [f1g;C1) be a 4-cycle system of K9 E([i Z6nZ4F i [ (1;13;16)) (see Lemma 32). Similarly, let (((Z12nZ6)[f1;20;21g);C2) be a 4-cycle system of K9 E([i Z4nZ2F i ) (see Lemma 30). Using Theorem 5.1, let (K(Z6;(Z22n(Z6[f13;16g)));C3) be a 4-cycle system of K(6, 14). By Theorem 5.1 let, (K((Z20nZ12);(Z22n(Z6 [ (Z20nZ12))));C4) be a 4-cycle system of K(8, 8). Then ([i Z5;Ci) is a 4-cycle sys- tem of K23 E(F ). 10. Let V(Kn) = Z20Sf1g. De ne F i = (1;3i;3i+ 1;3i+ 2) for each i Z3 G i = (1;4i 3;4i 2;4i 1;4i) for each i Z5nZ3 and 84 F = (([i Z3 (F i )) [ ([i Z5nZ3 (G i))) Let (Z6 [f1;7;10g;C0) be a 4-cycle system of K9 E([i Z2F i ) (see Lemma 30). ((Z13nZ6)[f1;19g;C1) be a 4-cycle system of K9 E(F 2 [G 3 [(1;7;10)) (see Lemma 32). Similarly, let (((Z19nZ13)[f1g);C2) be a 4-cycle system of K7 E(G 4) (see Lemma 29). Now, using Theorem 5.1, let (K(Z6;(Z20n(Z6[f7;10g)));C3) be a 4-cycle system of K(6, 12). Similarly, (K((Z19nZ13);(Z13nZ6)[f19g);C4) be a 4-cycle system of K(6, 8). Then ([i Z5;Ci) is a 4-cycle system of K21 E(F ). 11. Let V(Kn) = Z18Sf1g. De ne F i = (1;3i;3i+ 1;3i+ 2) for i = 0 G i = (1;4i 1;4i;4i+ 1;4i+ 2) for each i Z4nZ1 and F = ((F 0 ) [([i Z4nZ1 (G i))) Let ((Z11nZ7)[f1;1;4g;C0) be a 4-cycle system of K7 E(G 2) (see Lemma 29). ((Z17nZ11)[f1g;C1) be a 4-cycle system of K7 E(G 3) (see Lemma 29). Similarly, let ((Z7[f1;17g);C2) be a 4-cycle system of K9 E(F 0[G 1[f1;1;4g) (see Lemma 32). Now, using Theorem 5.1 let, (K((Z11nZ7);(Z18n((Z11nZ7)[f1;4g)));C3) be a 4-cycle system of K(4, 12). Similarly, (K((Z17nZ11);(Z7 [f17g));C4) be a 4-cycle system of K(6, 8). Then ([i Z5;Ci) is a 4-cycle system of K19 E(F ). 5.3 Proposition In this section we give constructions for obtaining 4-cycle systems of Kn E(F ) for some general values of n. Proposition 19. Suppose n = 24x + y, x;y Z+ and F consists of 4 cycles, all of which are incident with the vertex1where y f1;9;17gfor some x N. Then there exists a 4-cycle system of Kn E(F ) 85 Proof. We know that y f1, 9, 17g for some x N. When y f9;17g the required 4- cycle system exists by Lemma 36. And the remaining 4-cycle systems exist by the following construction. Let V(Kn) = ff1gSfZ24 Zxg[fZy 1gg. For each z Zx let, (f1g[(Z24 fzg);Cz) be a 4-cycle system of order 25 which exists, by Lemma 36. (f1g[Zy 1;Cy) be a 4-cycle system of order y which exists, by Lemma 36. By Theorem ??, for 0 i < j < x let, (fZ24 figg[fZ24 fjgg;C(i;j)) be a 4-cycle system of (K24;K24) and for all i Zx, (fZ24 figg[fZy 1g;C(i;x)) be a 4-cycle system of (K24;Ky 1). Then (([z Zx+1Cz)[([0 i