3-Cycle Systems and Structure within Graph Decompositions by Joe Cha ee 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 August 2, 2014 Keywords: graph decomposition, neighborhood graph, quadratic leave, quadratic excess Copyright 2014 by Joe Cha ee Approved by Chris Rodger, Chair, Don Logan Endowed Chair of Mathematics, Department of Mathematics and Statistics; Associate Dean for Research and Graduate Studies, COSAM Curt Lindner, Distinguished University Professor, Department of Mathematics and Statistics Peter Johnson, Professor, Department of Mathematics and Statistics Abstract An H-decomposition of a graph G is a partition of the edge set E(G) such that each element of the partition induces a subgraph isomorphic to H. A packing or cover of Kn (with triples) is an ordered pair (V;B) where V is an n-element set and B is a set of 3-element subsets of V called blocks such that each 2-element subset of V appears in at most blocks or at least blocks respectively. De ne E(B) =ffx;yg;fx;zg;fy;zgjfx;y;zg2Bg. The leave of a packing is de ned to be the multiset of edges L = E( Kn) E(B) and the excess or padding of a cover is de ned to be the multiset of edges P = E(B) E( Kn). In this dissertation, necessary and su cient conditions for the existence of K3- decompositions of K = 1Km_ 2 1Kn are found when 1 2, vastly generalizing the results in the literature on K3-decompositions of K. In a speci c case of this problem (namely when n = 2), it is useful to know for which simple quadratic subgraphs Q of Kn (so Q cannot have 2-cycles) do there exist a K3-decomposition of Kn E(Q) (that is, a packing of Kn with leave equal to E(Q)). A complete solution to this question is provided; in addition to being useful in proving the rst result, it is also signi cant in that it extends a classic result of Colbourn and Rosa who answered the same question when = 1. In terms of the quadratic leave problem, the previous result, while short and simple, has a gap in that it does not allow Q to have 2-cycles; the next result resolves this issue. In a packing of 2Kn, the neighborhood graph of a vertex v is de ned to be the graph induced by the multiset of edges ffa;bgjfa;b;vg2Bg. In a maximum packing of 2Kn, the neighborhood graph of a vertex is a 2-regular graph on either n 1 or n 2 vertices. Colbourn and Rosa provided a chararterization of which 2-regular graphs on n 1 or n 2 vertices can be the neighborhood graph of a vertex in some maximum packing of 2Kn when n 0 or 1 (mod 3); this dissertation provides such a characterization in the case where ii n 2 (mod 3). This result along with the Colbourn and Rosa result (n 0 or 1 (mod 3)) is used to nd necessary and su cient conditions for a K3-decomposition of Kn E(Q) where Q is any 2-regular graph on at most n vertices (so Q can have 2-cycles). Finally, having already found necessary and su cient conditions for Q to be a 2-regular leave of Kn, the problem of when a quadratic graph Q has edge set equal to the excess of a cover of Kn is considered, and necessary and su cient conditions for a K3-decomposition of Kn +E(Q) appear in the dissertation. iii Acknowledgments I would like to thank Chris Rodger for his guidance, advice, and patience in working with me. iv Table of Contents Abstract . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ii Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iv List of Figures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . vii 1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.1 De nitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.2 History . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 2 Group Divisible Designs with Two Associate Classes and Quadratic Leaves of Triple Systems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 2.2 Terminology . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 2.3 The Case where K has no parts of size 2 . . . . . . . . . . . . . . . . . . . . 9 2.4 Quadratic Leaves . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 2.5 The case where m = 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 3 Neighborhoods in Maximum Packings of 2Kn and Quadratic Leaves of Triple Systems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34 3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34 3.2 Preliminary Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35 3.3 Neighborhoods for 2K3x+2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39 3.4 Quadratic Leaves . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44 4 Neighborhoods in Maximum Packings of 2Kn- A Second Version . . . . . . . . . 48 4.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48 4.2 Preliminary Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48 4.3 Main Result . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51 v 5 Quadratic Excesses or Paddings of Covers with Triples of Kn . . . . . . . . . . 60 5.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60 5.2 Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60 6 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65 Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67 vi List of Figures 1.1 2K9 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 1.2 1Km_ 2 1Kn . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 1.3 C8 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 vii Chapter 1 Introduction This dissertation will focus on two main problems. First, it will look at nding K3- decompositions of a speci c family of graphs. Second, it will look at structure within packings and covers of Kn. This introduction will rst give a number of very general de nitions in Section 1.1, and then discuss some previously solved problems related to the results in this dissertation in Section 1.2. The remaining chapters of this dissertation will be devoted to proving the results I have obtained over the past ve years. 1.1 De nitions A graph G is an ordered pair (V(G);E(G)) where V(G) is a set of elements called vertices and E(G) is a multiset of unordered pair of vertices; the elements of E(G) are called edges. WhenjV(G)j= n, for notational purposes, it is often convenient to let V(G) = Zn = f0;1;:::;n 1g. A graph H is said to be a subgraph of a graph G if V(H) V(G) and E(H) E(G). Two particular graphs that appear extensively in this dissertation are Kn, which is the graph with n vertices in which every pair of vertices is joined by edges, and 1Kn_ 2 1Km, which is the graph in which the vertex set is partitioned into two parts M and N wherejMj= m,jNj= n, and each pair of vertices is joined by 1 edges if they are in the same part and is joined by 2 edges if they are in di erent parts. Two vertices u and v are said to be adjacent if fu;vg2E(G). If u and v are adjacent, we write u v. The edge fu;vgis said to be incident with the vertices u and v. The degree of a vertex v, denoted by degG(v) = deg(v), is the number of edges incident with v. A k-cycle is a graph on k vertices in which every vertex has degree 2. When a cycle C is considered as a subgraph of Kn, C is said to be a Hamilton cycle ifjV(C)j=jV(Kn)j= n and C is said to be a near-Hamilton 1 cycle if jV(C)j= n 1. Figures 1.1,1.2, and 1.3 show the graphs 2K9, 1Km_ 2 1Kn; and C8 respectively. Figure 1.1: 2K9 ?1 ?2 ?1 Figure 1.2: 1Km_ 2 1Kn Figure 1.3: C8 1.2 History An H-decomposition of a graph G is a partition of the edge set E(G) such that each element of the partition induces a subgraph isomorphic to H. In this dissertation, K3- decompositions of graphs will be studied. Perhaps the most famous problem related to this topic is nding necessary and su cient conditions for the existence of a K3-decomposition of Kn. This problem was solved by Kirkman who showed in [19] that there exists a K3- decomposition of Kn if and only if n 1 or 3 (mod 6). A natural extension of this problem is to nd necessary and su cient conditions for the existence of a K3-decomposition of Kn. This was solved by Hanani in [17] where it was shown that there exists a K3-decomposition of Kn if and only if (n 1) is even, (n)(n 1) is divisible by 3, and n6= 2. A -fold triple system is an ordered pair (V;B) where V is a n-element set and B is a set of 3-element subsets of V called blocks such that each 2-element subset of V appears in blocks of B. The blocks of B are also called triples. It is straightforward to see that a -fold triple system is equivalent to a K3-decomposition of Kn. 2 With the necessary and su cient conditions for aK3-decomposition of Kn well-established, there are a few natural directions to go, three of which are as follows: 1. What are necessary and su cient conditions for K3-decompositions of more general graphs G? 2. What type of structure is present in K3-decompositions of Kn? 3. What are some natural notions of closeness to K3-decompositions of Kn, and when can they be achieved? These three questions are the main focus of the work in this dissertation. The rst ques- tion is studied almost exclusively in Chapter 2; hence terminology speci c to that question will appear in Chapter 2. The other questions are studied throughout the dissertation, and hence the rest of this introduction will provide some de nitions and history related to the last two questions. The two most natural notions of closeness to a K3-decomposition of a graph G are packings and coverings. For the purposes of this dissertation, a packing of a graph G is a K3-decomposition of a subgraph H of G. In the case where G = Kn, a packing is sometimes referred to as a partial ( -fold) triple system. If (V;B) is a (partial) triple system, de ne the set of edges E(B) =ffx;yg;fx;zg;fy;zgjfx;y;zg2Bg. If (V;B) is a packing of Kn, then the leave of the packing is de ned to be the multiset of edgesL = E( Kn)nE(B). It will cause no confusion to also refer to the leave as being the subgraph induced by E( Kn)nE(B). In particular, in the special case where L =ffa;bg;fa;bgg, L is expressed as the 2-cycle (a;b). A vertex v is said to be in the leave if there is some edge in the leave that is incident with v. A maximum packing is a packing such that among all packings the number of edges in its leave is as small as possible (with respect to the graph G). On the other hand, a cover of a graph G is a K3-decomposition of E(G) +P where P is a multiset of edges with underlying vertex set V(G); in this dissertation, the topic of covers will only appear when G = Kn. If (V;B) is a cover of Kn, de ne the set of edges E(B) =ffx;yg;fx;zg;fy;zgjfx;y;zg2Bg; the 3 excess or padding of the cover is de ned to be E(B)nE( Kn). Much like with leaves, it is commonplace to look at the subgraph induced by the excess as opposed to the excess itself. A minimum cover is a cover such that among all covers the number of edges in its excess is as small as possible (with respect to the graph G). Maximum packings and minimum covers have also been well studied, and the leaves of all maximum packings of Kn and the excesses of all minimum covers of Kn have been found; for instance, see [23]. In this dissertation, quadratic leaves and excesses will be studied, but before getting to this problem, a related problem is considered. In any partial triple system (V;B) of 2Kn, the neighborhood of a vertex v2V is the graph induced by ffx;ygjfv;x;yg2Bg. If (V;B) is a maximum packing of 2Kn then the neighborhood of each vertex is a 2-regular graph, also called a quadratic graph. It will cause no confusion to also refer to the neighborhood as a set of cycles, each being a component of the neighborhood. It is natural to ask for which quadratic graphs Q does there exist a maximum packing (V;B) of 2Kn in which there exists a vertex v 2 V for which the neighborhood of v is Q? Colbourn and Rosa came up with a large part of the answer in [9]. Theorem 1.1. [9] Suppose n 0 or 1 (mod 3). A 2-regular graph Q on n 1 vertices is the neighborhood of a vertex in a 2-fold triple system on n vertices if and only if (n;Q) =2 f(6;C2[C3);(7;C3[C3)g. One purpose of looking at this structure within 2-fold triple systems is that it helps determine when 2-fold triple systems are not isomorphic. The dissertation extends this result by proving an analogous result for n 2 (mod 3); this result appears in Chapter 3. A simpler proof of this result that also subsumes the Colbourn and Rosa result appears in Chapter 4. This structure problem seems unrelated to the earlier topic of quadratic leaves and excesses, but in fact, the topic of quadratic leaves is related to this structure problem. In most cases, deleting a vertex in a maximum packing of 2Kn induces a packing of 2Kn 1 where the leave induces a quadratic graph. For quadratic excesses, there is perhaps not as 4 clear a motivation for studying them, but they do form a natural complement to quadratic leaves and are hence discussed. In terms of quadratic leaves and excesses, the only explicit results prior to this dissertation are for = 1 and are as follows: Theorem 1.2. [11] Let Q be a 2-regular (quadratic) simple graph. There exists a K3- decomposition of Kn E(Q) if and only if 1. n is odd, 2. jE(Kn)j jE(Q)j is divisible by 3, and 3. (n;Q) =2f(7;C3[C3);(9;C4[C5)g. Theorem 1.3. [10] Let Q be a quadratic graph on n vertices. Then Q is the excess of a cover of Kn if and only if 1. n is odd, and 2. jE(Q)j+jE(Kn)j 0 (mod 3). In this dissertation, both of these results are extended to the case where > 1, although it should be mentioned that part of the the quadratic leave result for when = 2 is a direct consequence of Theorem 1.1. The result for quadratic leaves appears in Chapter 3 although a partial result is mentioned in Chapter 2, while the result for quadratic excesses appears in Chapter 5. More speci c terminology will be introduced in the chapters as it is needed and the dissertation now goes into the speci c results obtained over the last ve years. 5 Chapter 2 Group Divisible Designs with Two Associate Classes and Quadratic Leaves of Triple Systems 2.1 Introduction A group divisible design with two associate classes GDD(v;fg1;:::;gng;k; 1; 2) is an ordered triple (V;G;B) where V is a v-set of symbols, G is a partition of V into n sets (called groups) of sizes g1;:::;gn (possibly gi = gj for some i6= j so fg1;:::;gng is regarded as a multiset), and B is a set of k-element subsets of V known as blocks, such that any two distinct elements of V appear together in 1 blocks if they are in the same group and 2 blocks otherwise. In the special case where 1 = 0, 2 = 1, and k = 3, it is common to use GDD(v;fg1;:::;gng) instead of GDD(v;fg1;:::;gng;3;0;1), and the design is called a group divisible design. Bose and Shimamoto were among the rst to classify such designs [2]. Fu, Rodger, and Sarvate solved the existence of these designs for k = 3 when all groups have the same size [15; 16]. A more general problem is to settle the existence question for k = 3 when the groups have di erent sizes. In general this is a di cult problem, perhaps the most di cult case being when there are exactly two groups. Pabhapote and Punnim solved the existence in this case under the assumptions that 2 = 1 and that neither m nor n is 2 [25]. In this chapter, their result is generalized with a di erent proof, completely solving the interesting case where one of the two groups has size 2 (see Section 2:5) and also solving the case where 2 1 (see Section 2:3). These results are stated in the major theorem of the chapter (see Theorem 2:2). The problem can be approached in terms of an equivalent graph decomposition problem. Let K = K(M;N; 1; 2) = 1Km_ 2 1Kn where jMj= m and jNj= n be a graph on the 6 vertex set M[N (M and N are called the parts) in which for each x;y2M[N with x6= y, there exist 1 edges between x and y if x and y are in the same part and 2 edges between x and y otherwise. An edge e =fx;ygis said to be pure if x and y lie in the same part and is said to be mixed otherwise. A K3-decomposition of a graph G is an ordered pair (V(G);B) where B is a partition of E(G) into sets, each of which induces a K3; in this chapter focus will be placed on the case where G = K. Sometimes the copies of K3 are called triples and the K3-decomposition of K is called a triple system of K. It is straightforward to see that such a graph decomposition is equivalent to a GDD(v = m+n;fm;ng;3; 1; 2). To begin, some obvious necessary conditions for the existence of this K3-decomposition of K are given. Some of these conditions appear in other papers (such as [13]), but the proof is included here for completeness. Lemma 2.1. Let K = 1Km_ 2 1Kn with jMj= m and jNj= n. Assume that n = 2 only if m = 2. The following conditions are necessary for the existence of a K3-decomposition of K. 1. 3 divides 1( m2 + n2 ) + 2mn, 2. 2 divides 1(m 1) + 2n and 2 divides 1(n 1) + 2m, 3. 2 1( m2 + n2 ) 2mn, 4. if m = 2 then 1 2n, and 5. if m = 2 and n 2 then 1 = 2. Proof. The rst and second conditions are necessary since the total number of edges must be divisible by 3 and the degree of each vertex must be divisible by 2 respectively. The last three conditions come from looking at the types of triples that can be chosen. Note that every triple that contains a mixed edge must use precisely two mixed edges and a pure edge; thus, the third condition is necessary. If m = 2 then each triple that uses a pure edge in M, 7 must also use two mixed edges; thus, the fourth condition is necessary. Finally, if m = 2 and n is less than or equal to 2 then every triple must use a pure edge and two mixed edges, so the fth condition is necessary. Note that under the assumption that 1 2, the third necessary condition simpli es to requiring that either m> 1 or n> 1. It seems reasonable to conjecture that the conditions of Lemma 2.1 are su cient as well. As noted earlier, this conjecture is proved in the case where m = 2 (see Section 2:5: Theorem 2.14) and where 1 2 (see Section 2:3: Theorem 2:11). These proofs culminate in the following result. Theorem 2.2. Let K = 1Km_ 2 1Kn with m = 2 if n = 2. Let 1 2 if m6= 2. There exists a K3-decomposition of K if and only if 1. 3 divides 1( m2 + n2 ) + 2mn, 2. 2 divides 1(m 1) + 2n and 2 divides 1(n 1) + 2m, 3. 2 1( m2 + n2 ) 2mn, 4. if m = 2 then 1 2n, and 5. if m = 2 and n 2 then 1 = 2. Another valuable result in this chapter is the generalization of the classic result by Colbourn and Rosa establishing necessary and su cient conditions for the existence of a K3-decomposition of Kn E(Q) where Q is a 2-regular subgraph of Kn (see Theorem 2:12). In Section 2:4, the generalization of this problem to Kn E(Q) is completely solved as long as Q is simple, the necessary and su cient conditions depending on n;Q; and (see Theorem 2.13). This result is then used in the proof of Lemma 2.18, thus helping to settle the m = 2 case (see Theorem 2.14). 8 2.2 Terminology The following terminology will be used throughout the chapter so it is de ned here and complements the terminology given in Chapter 1. In Kv with vertex set Zv, de ne the di erence of an edge joining two vertices i and j as d(i;j) = minfji jj;v j(i j)jg. For each D f1;:::;v 1g, let Gv(D) be the graph with vertex set Zv and edge set consisting of all edges of di erences in D. A di erence d is said to be good if vgcd(v;d) is even. A di erence triple is a triple (a;b;c) of unique integers from the set f1;:::;v 1g, such that a+b = c or a+b+c = v. For i2f1;3;5g, let Fi(V(G)) be a graph with vertex set V(G) in which one vertex has degree i and the rest have degree 1; these graphs are known as 1-factors, 3-poles (tripoles), and 5-poles when i = 1;3; and 5 respectively. A graph G is said to be evenly equitable if each vertex of G has even degree and for all u;v2V(G), jd(u) d(v)j 2. 2.3 The Case where K has no parts of size 2 In this section, Theorem 2.2 is proved in the case where neither part has size 2 (see Theorem 2.11). First some lemmas that are used in the proof of the theorem are given. The rst addresses the well-known existence of maximum packings and minimum covers of Kv with triples. Theorem 2.3. [17, 23] Let 1 and v 3. Let P (or L) be any multigraph with the least number of edges in which all vertices have degree congruent to (v 1) (mod 2) and with jE(P)j+ v(v 1)2 0 (mod 3) (or v(v 1)2 jE(L)j 0 (mod 3) respectively). Then there exists a K3-decomposition of Kv[E(P) (or Kv E(L) respectively). A latin square L of order n is an n n array containing the symbols 0;1;:::;n 1 such that each symbol appears exactly once in each row and each column. If L is a latin square, 9 we refer to the symbol in cell (a;b) as being a b. With the operation , the latin square is referred to as a quasigroup; the quasigroup is denoted by (L; ). A quasigroup is said to be idempotent if i i = i for every i2f0;1;:::;n 1g. The next lemma shows that quasigroups can be constructed so that they are not commutative; this result will be used later to build a triple system with a desired property. Lemma 2.4. For all n 4, there exists an idempotent quasigroup of order n that is not commutative. That is, for all n 4, there exists an idempotent quasigroup of order n in which there exist a and b such that a b6= b a. Proof. If n is even, then the result follows since in every idempotent quasigroup, each symbol appears once on the main diagonal and hence appears o the main diagonal an odd number of times. If n is odd, then de ne i i = i and (i+1) (j+2) = i j for 0 i;j 2 and let Q be a quadratic simple graph on at most n vertices. Then Q is the leave of a packing of Kn if and only if: 1. Either is even or n is odd, 17 2. 3 divides jE( Kn)j jE(Q)j, and 3. (a) if = 1 and n = 7, then Q6= C3[C3, (b) if = 1 and n = 9, then Q6= C4[C5, and (c) if = 2 and n = 6, then Q6= C3[C3. Proof. Suppose there exists a packing of Kn E(Q). Since each vertex of Q has even degree and each vertex of Kn E(Q) must have even degree, each vertex of Kn must have even degree so Condition 1 is necessary. Since the edges of Kn E(Q) are partitioned into sets of size 3, Condition 2 is necessary. Conditions 3(a) and 3(b) follow from Theorem 2:12. Condition 3(c) follows from the fact that the only K3-decomposition of 2K6 (up to isomorphism) does not contain two disjoint triples. Thus Condition 3 is necessary. The proof of the su ciency is broken into several cases, based on the congruence classes (mod 6) of n. Let n; ; and Q satisfy Conditions (1 3). Theorem 2:12 handles the case where = 1, so assume > 1, Also, if jE(Q)j = 0, then by Theorem 2:3, there exists a K3-decomposition of Kn, which proves the result. Hence, assume jE(Q)j 3. (Note that no simple quadratic graph has 1 or 2 edges.) If n 1 (mod 6) or n 3 (mod 6), Condition 2 is satis ed if and only if jQj 0 (mod 3). So, unless > 1 and (n;Q)2f(7;C3[C3);(9;C4[C5)g, the result follows by taking a triple system of Kn E(Q) (see Theorem 2:12) together with a triple system of ( 1)Kn. If > 1 and (n;Q) = (7;C3 [C3), then by Theorem 2:3, the vertices of two triple systems of K7 with vertex set V can be named to contain the triples T1 = fa1;b1;c1g and T2 =fa2;b2;c2grespectively, with T1\T2 =;; let B1 be the union of the triples of these triple systems with Q = T1[T2 removed. If > 1 and (n;Q) = (9;C4[C5), then by Theorem 2:12, let (V;B01) be a triple system of K9 L1 where L1 is the nine-cycle (0;1;2;3;4;5;6;7;8) and let (V;B001) be a triple system of K9 L2 where L2 is the six-cycle (0;3;6;4;8;7). Let 18 B1 = B01[B001[ff3;4;6g;f0;7;8gg. In either case, let (V;B2) be a triple system of ( 2)Kn. Then (V;B1[B2) is the required decomposition. Suppose n 5 (mod 6). Let 2f1;2;3g with (mod 3). By Theorem 2:3, let (V;B1) be a K3-decomposition of ( )Kn. The three values are now considered separately. Suppose = 1. By Theorem 2:12, let (V;B2) be a K3-decomposition of Kn E(Q). Suppose = 2. Let Q0 be formed from Q by replacing one cycle, c = (0;1;:::;x), of length x+ 1 4 in Q with the cycle (1;:::;x) (by Condition 2,jE(Q)j jE(2Kn)j 2 (mod 3) and hence there must be a cycle of length at least 4). By Theorem 2:12, let (V;B02) be a K3-decomposition of Kn E(Q0). Let (V;B002) be a K3-decomposition of Kn E(L) where L is the 4-cycle (0;1;2;x). Let B2 = B02[B002 [ff1;2;xgg. Finally, suppose = 3. By Condition 2, jV(G[Q])j n 2 so say 0 =2V(G[Q]). Let c = (1;2;:::;x) be any cycle in Q and set c0 = (0;1;:::;x). Form Q0 from Q by replacing c with c0. Also by Condition 2, jE(Q)j jE( Kn)j 0 (mod 3), so jE(Q0)j 1 jE(Kn)j (mod 3). So by Theorem 2:12, let (V;B02) be a K3-decomposition of Kn E(Q0). By Theorem 2:3, let (V;B002) be a K3-decomposition of 2Kn E(L) where L consists of two copies of the edge f1;xg. Let B2 = B02[B002 [ff0;1;xgg. In each case, (V;B1[B2) is the required K3-decomposition. Suppose n 4 (mod 6). First suppose (n;Q) 6= (10;C4[C5). By Condition 1, is even. By Theorem 2:3, let (V;B1) be a K3-decomposition of ( 2)Kn. By Condition 2, jV(G[Q])j n 1 so say 0 =2 V(G[Q]). Let G = G[V(Kn)nf0g]. By Theorem 2:12, let (V ;B2) be a K3-decomposition of G E(Q). Let (V;B3) be a maximum packing of Kn with leave L, a tripole, that includes the edges f0;1g;f1;2g; and f1;3g. Finally, let B4 = ffx;y;0gjfx;ygis an independent edge in Lg[ff0;1;2g;f0;1;3gg. Then (V;[4i=1Bi) is the required decomposition. Now suppose (n;Q) = (10;C4[C5). Let (Z10;B1) be a maximum packing ofK10 with leave consisting of the edgesf0;1g;f0;8g;f0;9g;f2;3g;f4;5g;andf6;7g, and let (Z10;B2) be a maximum packing with leave consisting of the edges f0;3g;f1;2g, 19 f5;6g;f4;8g;f7;8g;f8;9g. Then (V;B1[B2[ff0;8;9gg) is the required packing of 2K10 and can be combined with a K3-decomposition of ( 2)Kn to get the result for higher values of . Suppose n 2 (mod 6). Note that n6= 2. By Condition 1, is even. Let 2f2;4;6g and set (mod 6). By Theorem 2:3, let (V;B1) be a K3-decomposition of ( )Kn. Suppose = 2. First suppose that Q contains a cycle of length at least 5. Let Q0 be formed from Q by replacing a cycle, c = (0;1;:::;x), of length x + 1 5 in Q with the cycle c0 = (2;:::;x). Note that 0 =2 V(G[Q0]). Let G = G[V(Kn)nf0g]. Since 2 (mod 6) (since = 2 in this subcase), then jE(Q)j jE( Kn)j 2 (mod 3), and hence jE(Q0)j 0 (mod 3). Further, n 1 1 (mod 6) so by Theorem 2:12, let (V ;B2) be a K3-decomposition of G E(Q0). Now let (V;B3) be a maximum packing of Kn with leave L, a 1-factor, with f1;2g and f0;xg as edges in the 1-factor. Finally, let B4 consist of the following triples: ffx;y;0gjfx;yg2 (Lnff1;2g;f0;xgg)g[ff0;2;xgg. Then (V;[4i=1Bi) is the required decomposition. Now suppose Q contains only three and four cycles. There are at least two four cycles; name them (0;1;2;3) and (4;5;6;7). Let Q0 be formed from Q by removing these two four cycles and replacing them with the six-cycle (2;3;4;5;6;7). Note that 0 =2V(G[Q0]). Let G = G[V(Kn)nf0g]. By the above argument, let (V ;B2) be a K3-decomposition of G E(Q0). Now let (V;B3) be a maximum packing of Kn with leave L, a 1-factor, with f1;2g,f4;7gandf0;3gas edges in the 1-factor. Finally, let B4 consist of the following triples: ffx;y;0gjfx;yg2 (Lnff1;2g;f0;3g;f4;7gg)g[ff0;2;7g;f0;3;4gg. Then (V;[4i=1Bi) is the required decomposition. Suppose = 4. By Condition 2, jV(G[Q])j n 1 so say 0 =2 V(G[Q]). Let c = (1;2;:::;x) be any cycle in Q and set c0 = (0;1;:::;x). Form Q0 from Q by replacing c with c0. By the above case for = 2, let (V;B2) be a packing of 2Kn with leave Q0. By Theorem 20 2:3, let (V;B3) be a maximum packing of 2Kn with leave the double edge f1;xg. Then (V;[3i=1Bi[ff0;1;xgg) is the required decomposition. Suppose = 6. By Condition 2, jV(G[Q])j n 2 so say 0 =2 V(G[Q]). Let c = (1;2;:::;x) be any cycle in Q and set c0 = (0;1;:::;x). Form Q0 from Q by replacing c with c0. By the above case for = 4, let (V;B2) be a packing of 4Kn with leave Q0. By Theorem 2:3, let (V;B3) be a maximum packing of 2Kn with leave the double edge f1;xg. Then (V;[3i=1Bi[f0;1;xg) is the required decomposition. Finally, suppose n 0 (mod 6). The proof is similar to the case where n 2 (mod 6) with = 2 unless Q consists entirely of 3-cycles. It is rst assumed that Q contains a 5-cycle, then two edges are removed from a cycle of length at least 5, a vertex is deleted, and then the leave is modi ed just as in the case where n 2 (mod 6) with = 2. If there are no ve cycles, but at least one four cycle, then there are necessarily three four cycles since jE(Q)j 0 (mod 3). Take two of the four cycles and then proceed in the same manner as in the case where n 2 (mod 6) with = 2. Finally, if there are only 3-cycles, note that n 12 (by assumption) and take a K3-decomposition of Kn that contains a parallel class (n3 disjoint triples; take the Bx from Lemma 2:7 for example). 2.5 The case where m = 2 A proof of Theorem 2:2 in the case where m = 2 is given in this section. The proof relies on results which follow it, but is worth reading rst before all the details potentially cloud the idea. Theorem 2.14. Let m = 2. Let 1; 2, and n be positive integers. Then there exists a K3-decomposition of 1Kn_ 2 1K2 if and only if 1. 3 divides 1( m2 + n2 ) + 2mn, 2. 2 divides 1(m 1) + 2n and 2 divides 1(n 1) + 2m, 3. 2 1( m2 + n2 ) 2mn, 21 4. 1 2n, and 5. if n 2 then 1 = 2. Proof. The necessity of Conditions (1 5) has been shown in Lemma 2:1, so the su ciency is now proved. Let M =fm0;m1g. For both n = 1 and n = 2, Condition 5 requires 1 = 2. If n = 1, then the su ciency follows from taking 2 copies of a triple system on 3 vertices. If n = 2, then Condition 2 implies that 1 is even. Thus, the su ciency follows from taking 12 copies of a 2-fold triple system of 2K4. Suppose n 3. The following three steps are taken, although they are dependent upon lemmas provided afterwards. Step 1: Since m = 2, the number of mixed edges incident with each vertex of N is even. Together with Condition 2, this implies that each vertex in 1Kn has even degree. Let (N;B1) be a K3-decomposition of 1Kn E(L) where L is a subgraph of Kn such that: (a) jE(L)j= 2n 1, (b) the subgraph induced by E(L) is connected, and (c) each vertex of L has even degree less than or equal to 2 2. The existence of L is shown in Lemma 2:18, but at least it is noted here that 2n 1 0 by Condition 3. Step 2: Since the subgraph of K induced by E(L), G = K[E(L)], is connected (by (b)) and since all vertices in G have even degree (by (c)), there exists an Euler circuit E of G. Alternately color the edges of E with colors 0 and 1. By Condition 2, 2n 1 is even, so E has even length, so for each vertex w in G, the number of edges in G incident with w colored 0 equals the number colored 1. Let B2 = ffmi;w;ugjfw;ug2E(L) is colored i;i2Z2g. Then for each i2Z2 and each n2N, the number of triples containing the pair fmi;ng is dG(n) 2 . 22 Step 3: By (c), 2 dG(n)2 is a nonnegative integer for each n2N. So let B3 be the multiset of triples formed as follows: for each n2N, let B3 contain 2 dG(n)2 copies of the triple fm0;m1;ng. By (a), Pn2N( 2 dG(n)2 ) = n 2 jE(L)j = 1, so 1 triples in B3 contain the pair fm0;m1g. Therefore (M[N;[3i=1Bi) is the required decomposition. So the result form = 2 is proved provided that it can be shown that theK3-decomposition of 1Kn E(L) in Step 1 actually exists. Conditions 3 and 1 imply that the number of edges in 1Kn E(L) is nonnegative and divisible by 3 respectively. It is now show how the K3- decomposition from Step 1 can be achieved. However, before showing the existence of L, a powerful result due to Simpson is given along with a corollary that will frequently be used in showing the existence of L. A Langford sequence of order n and defect d with n>d is a sequence L = (l1;l2;:::;l2n) of 2n integers satisfying the conditions (a) for every k2fd;d+ 1;:::;d+n 1g, there exist exactly two elements li;lj2L such that li = lj = k, and (b) if li = lj = k, then ji jj= k. A hooked Langford sequence of order n and defect d with n > d is a sequence L = (l1;l2;:::;l2n;l2n+1) of 2n integers satisfying the conditions (a) l2n = 0 (b) for every k2fd;d + 1;:::;d + n 1g, there exist exactly two elements li;lj 2Lnfl2ng such that li = lj = k, and (c) if li = lj = k, then ji jj= k. Theorem 2.15. [29] 1. A Langford sequence of order n and defect d exists if and only if 23 (a) n 2d 1 and (b) n 0;1 (mod 4) and d is odd, or n 0;3 (mod 4) and d is even. 2. A hooked Langford sequence of order n and defect d exists if and only if (a) n(n 2d+ 1) + 2 0 and (b) n 2;3 (mod 4) and d is odd, or n 1;2 (mod 4) and d is even. Corollary 2.16. Let n 3, w d + 3n, 0 n, and D1 fd + i j i 2 Zng with jD1j= n . If there exists a Langford sequence or a hooked Langford sequence of order n and defect d, then there exists D fd+iji2Z3ng with jDj= 3 and D1\D =; such that there exists a set of triples B0 such that B =fb+jjb2B0;j2Zwg is a K3-decomposition of Gw(D). The triples in B0 are said to generate the K3-decomposition of Gw(D). Proof. Let L = (l1;:::;l2n) or (l1;:::;l2n 1;0;l2n+1). Let B0 =ff0;i+n;j+ngjli = lj;li =2D0g so that the triplef0;i+n;j +ngcontains edges of di erences n+i, j +i and d(i;j). Then (Zw;B) is the required decomposition. The following useful result will also be used in the proof of Lemma 2:18. Theorem 2.17. [27] For n6= 2 there exists an equitable partial triple system containing v triples for any 1 v (n; ) where (n; ) = 8> >>> < >>> >: bn3b (n 1)2 cc 1 if n 2 (mod 6) and = 4 (mod 6) if n 5 (mod 6) and = 1 or 4 (mod 6) bn3b (n 1)2 cc otherwise The following lemma shows the existence of the decomposition described in Step 1 of the proof of the main theorem of this section. 24 Lemma 2.18. Let m = 2 and suppose the following ve conditions hold: 1. 3 divides 1( m2 + n2 ) + 2mn, 2. 2 divides 1(m 1) + 2n and 2 divides 1(n 1) + 2m, 3. 2 1( m2 + n2 ) 2mn, 4. 1 2n, and 5. if n 2 then 1 = 2. Then there exists a subgraph L of 1Kn with 2n 1 edges which is evenly equitable and connected for which there exists a K3-decomposition of 1Kn E(L). Proof. This lemma is proved in several cases. The vertex set of Kn will be Zn. First small values of are considered before a general construction is provided. For the small cases, Corollary 2:16 is consistently used. Case 1: First, suppose 1 = 1. Note that L being evenly equitable and having 2n 1 edges is equivalent to requiring that every vertex in the leave have degree 2 2 except for a single vertex which has degree 2 2 2; the exceptional vertex in the following constructions will be vertex 0;1 or 2. Conditions 1 and 2 imply that n 1;5 (mod 6) and 2 1 (mod 6). It can be assumed that 2 > 1 since otherwise, the problem simpli es to simply looking for a K3-decomposition of K6x+3 or K6x+1 which are both known to exist. Set 2 = 6z + 1 with z 1. Suppose n 5 (mod 6). It can be assumed that n 17, since if n = 5 or 11, then Condition 3 in conjunction with the fact that 2 1 (mod 6) implies that 2 = 1. For n = 6k + 5 17, using edges of only di erences 1 and 2, let B1 = ff3i;3i + 1;3i + 2gj 0 i 2k + 1g, where addition is done (mod 6k + 5). Note that every symbol ex- cept 0 appears in exactly one triple; 0 appears in two. If n = 17;23;29; or 35, let B02 = ff0;3;8g;f0;4;10gg;ff0;3;9g;f0;4;11g;f0;5;13gg;ff0;4;14g;f0;7;16g;f0;3;8gf0;6;17gg; 25 or ff0;3;17g;f0;5;11g;f0;7;20g;f0;9;19g;f0;4;12gg respectively. Otherwise, by Corol- lary 2:16, let B02 be a set of triples that generate a K3-decomposition of Gn(D) where D =f3;4;:::;3k + 2g. First note that k 2z, since by Condition 3, 2 +n(n 1) 2 2n = (12z+ 2)n, so since n 1 is an integer and n> 2 it follows that n 1 12z + 2, so 6k+ 4 12z + 2 so k 2z. Therefore, B2 can be formed by removing 2z 2 triples from B02, one of which contains the di erence 4. So jB2j=jB02j 2z = k 2z 0. Then (Zn;B1[fb + jjj2Zn;b2B2g) is the required K3-decomposition, since if v2Znnf0g, then dL(v) = (n 1) 2 6(k 2z) = 12z + 2 = 2 2 and dL(0) = (n 1) 4 6(k 2z) = 2 2 2. So L is evenly equitable with 2n 1 edges. Since all edges of di erence 4 are in L, L is connected. Suppose n 1 (mod 6). It can be assumed that n 19, since if n = 7 or 13, then Condition 3 in conjunction with the fact that 2 1 (mod 6) implies that 2 = 1. For n = 6k + 1 19, using edges of only di erences 1, 2, and 3, form triples as follows. Let 2f1;4;7g with n (mod 9). Let n = 9j + and B01 =ff9i;9i+ 1;9i+ 3g;f9i+ 1;9i+ 2;9i+4g;f9i+2;9i+3;9i+5g;f9i+4;9i+6;9i+7g;f9i+5;9i+7;9i+8g;f9i+6;9i+8;9i+9gj 0 i j 1g. Note that symbols 0 and 9j appear in one triple; symbols 1;:::;9j 1 appear in two. If = 1, then let B001 =ff9j;0;2gg. If = 4, then let B001 =ff9j;9j + 1;9j + 3g;f9j + 1;9j + 2;0g;f9j + 2;9j + 3;1gg. If = 7, then let B001 =ff9j;9j + 1;9j + 3g;f9j + 1;9j + 2;9j + 4g;f9j + 2;9j + 3;9j + 5g;f9j + 4;9j + 6;0g;f9j + 5;9j + 6;1gg. In any case, set B1 = B01[B001. Note that every symbol except y appears in exactly two triples; y appears in three triples, where y = 2 if = 1 and y = 1 if = 4 or 7. If n 25, then there exists a set B02 of triples that generates a K3-decomposition of Gn(D =f4;5;:::;3kg). This follows from Corollary 2.16 if n 49. If n = 25;31;37; or 43, let B02 =ff0;4;13g;f0;7;15g;f0;5;11gg;ff0;5;11g;f0;4;17g;f0;9;19g;f0;7;15gg;ff0;4;17g; f0;7;18g;f0;6;14g;f0;5;15g;f0;9;21gg; or ff0;11;23g;f0;7;22g;f0;4;13g;f0;6;16g; f0;5;19g;f0;8;25gg respectively. 26 Now use B02 to de ne B2. First note that k 1 2z, since by Condition 3, 2+n(n 1) 2 2n = (12z + 2)n, so since n 1 is an integer and n> 2 it follows that n 1 12z + 2, so 6k 12z+ 2, so k 1 2z. Therefore if n 25, then B2 can be formed by removing 2z 2 triples from B02, one of which contains the di erence 4. SojB2j=jB02j 2z = (k 1) 2z 0. If n = 19, then 2 2f1;7g so it can be assumed that 2 = 7; this means that k 1 = 2z so de ne B2 = ; in this case. Then for n 19, (Zn;B1[fb + j jj 2Zn;b2B2g) is the required K3-decomposition, since if v2Znnfyg, then dL(v) = (n 1) 4 6((k 1) 2z) = 12z + 2 = 2 2 and dL(y) = (n 1) 6 6((k 1) 2z) = 2 2 2. So L is evenly equitable with 2n 1 edges. Since all edges of di erence 4 are in L, L is connected. Case 2: Now suppose 1 = 2. Then n 1;2;4; or 5 (mod 6). If 2 = 2, the result follows from Theorem 2:3, so assume 2 > 2. Note that L being evenly equitable and having 2n 1 edges is equivalent to requiring that every vertex in the leave have degree 2 2 except for two vertices each of which has degree 2 2 2. Suppose n 1 or 5 (mod 6). Conditions 1 and 2 imply that 2 2 (mod 6). It can be assumed that n 11 since if n = 5 or 7, then Condition 3 in conjunction with the fact that 2 2 (mod 6) implies that 2 = 2. First supposen 17. By Case 1, there exists aK3-decomposition (Zn;B1) ofKn E(L1) where L1 is a subgraph of Kn with ( 2 1)n ( 1 1) edges which is evenly equitable and connected. By Theorem 2:12, there exists a K3-decomposition (Zn;B2) of Kn E(L2) where L2 is a subgraph of Kn consisting of a n 1 cycle such that the vertex not in the cycle has maximum degree in L1. Then (Zn;B1[B2) is the required decomposition with L = G[E(L1)[E(L2)]. Suppose n = 11 or 13. Condition 3 implies that 2 = 2 or 8, so it can be assumed that 2 = 8. Forn = 11, letB =ff3i+j;3i+1+j;3i+2+jgj0 i 3;0 j 1g. Then (Zn;B) is the required K3-decomposition, since if v2Znnf0;1g, then dL(v) = 2(10) 4 = 16 = 2 2 and dL(0) = dL(1) = 2(10) 6 = 2 2 2. So L is evenly equitable with 2n 1 edges. Since all edges of di erence 4 are in L, L is connected. For n = 13, let B =ff0 +j;1 +j;3 + 27 jg;f1+j;2+j;4+jg;f2+j;3+j;5+jg;f4+j;6+j;7+jg;f5+j;7+j;8+jg;f6+j;8+j;9+ jg;f9+j;10+j;12+jg;f10+j;11+j;0+jg;f11+j;12+j;1+jgj0 j 1g. Then (Zn;B) is the required K3-decomposition, since if v2Znnf1;2g, then dL(v) = 2(12) 8 = 16 = 2 2 and dL(1) = dL(2) = 2(12) 10 = 2 2 2. So L is evenly equitable with 2n 1 edges. Since all edges of di erence 4 are in L, L is connected. Now assume n 2 or 4 (mod 6). In this case, the half-di erence is present and used only once. Instead of thinking of the di erences as 1;2;:::;n2;1;2;:::;n2 1, it is useful to think of them as 1;2;:::;n 1 since, for instance, the di erence 1 can be thought of as a di erence n 1. In both cases, by Condition 1, 2 2 (mod 3), so let 2 = 3z + 2. Suppose n 2 (mod 6) with n> 2, and let n = 6k+ 2. Although, it seems unnecessary at this point, 2 = 2 is allowed for cases where n 2 (mod 6) (see Cases 4 and 5 for the use of this result). Using only di erences 1;2; and n 1 = 1, let B1 = ffi;i + 1;i + 2gj 0 i n 1;i 0;1 (mod 3)g. Then each vertex has degree 4 from the triples in B1 except 0 and 1 which have degree 6. Now assume n 20. Consider the di erences in D0 = f3;4;:::;n 2g. Then jD0j 1 (mod 3). Let v = n 2 or n 3 if n 53 0;1 (mod 4) or 2;3 (mod 4) respectively. By Corollary 2:16, there exists a set of triples B02 that generates a K3-decomposition of Gn(D = D0nfvg). Note that 2k 1 z, since by Condition 3, 4 + 2n(n 1) 2 2n = (6z + 4)n, so since n 1 is an integer and n > 2, (n 1) (3z + 2), so 6k + 1 3z + 2, so 2k 1 z. Therefore, B2 can be formed by removing z 0 triples from B02; if z 1, choose one that contains the di erence 3. So jB2j = jB02j z = 2k 1 z 0. For n = 8, by Condition 3, 2 = 2 or 5. If 2 = 2, let B2 = ff0;2;5gg, and if 2 = 5 and let B2 = ;. For n = 14, by Condition 3, 2 = 2;5;8; or 11. If 2 = 2, let B2 = ff0;2;6g;f0;3;6g;f0;4;9gg. If 2 = 5, let B2 = ff0;4;9g;f0;6;13gg. If 2 = 8, let B2 = ff0;4;9gg. If 2 = 11, let B2 = ;. Then for n 8, (Zn;B1 [fb + j j j 2 Zn;b 2 B2g) is the required K3-decomposition, since if v 2 Znnf0;1g, then dL(v) = (2n 2) 4 6((2k 1) z) = 6z + 4 = 2 2 and dL(0) = dL(1) = (2n 2) 6 6((2k 1) z) = 2 2 2. So L is evenly equitable with 28 2n 1 edges. So it remains to show that L is connected. If 2 5 or if n 20 and ( 2;v)2(z;n 3), then since all edges of di erence 3 are in L, L is connected. For n 8, the edges of di erence 1;2; and n 1 not used in B1 form n 23 vertex-disjoint 3-cycles, namely L0 =f(i;i+ 1;i+ 2)ji 2 (mod 3);2 i n 3g. If n 20 and ( 2;v) = (2;n 2), then since Gn(fn 2g) has two components (induced by odd and even vertices), L is connected since it also contains (2;3;4) 2 L0. If n 2f8;14g, then L is formed from L0 by adding E(Gn(fn2g)), so is easily seen to be connected. Suppose n 4 (mod 6) and let n = 6k+4. If n 10, then using only di erences 1 and 2, let B1 =ffi;i+1;i+2gj0 i n 4;i 0 (mod 3)g[ffn 2;n 1;0gg. Then each vertex has degree 2 from the triples in B1 except vertices 0 and n 2 which have degree 4. Now further assume n 22. Consider the di erences in D0 =f3;4;:::;n 1g. ThenjD0j 1 (mod 3). Let v = n 1 or n 2 if n 43 0;1 (mod 4) or 2;3 (mod 4) respectively. By Corollary 2:16, there exists a set of triples B02 that generates a K3-decomposition of Gn(D = D0nfvg). Note that 2k z, since by Condition 3, 4 + 2n(n 1) 2 2n = (6z + 4)n, so since n 1 is an integer and n > 2, (n 1) (3z + 2), so 6k + 3 3z + 2, so 2k z. Therefore, B2 can be formed by removing z 1 triples from B02, one of which contains the di erence 3. So jB2j=jB02j z = 2k z 0. For n = 10, by Condition 3, 2 = 2;5; or 8 so assume 2 = 5 or 8. If 2 = 5, let B2 =ff0;4;9gg, and if 2 = 8, let B2 =;. For n = 16, 2 = 2;5;8;11 or 14, so assume 2 2f5;8;11;14g. If 2 = 5, let B2 =ff0;4;15g;f0;6;13g;f0;5;14gg. If 2 = 8, let B2 = ff0;4;15g;f0;6;13gg. If 2 = 11, let B2 = ff0;4;15gg. If 2 = 14, let B2 = ;. Then for n 10, (Zn;B1 [fb + j j j 2 Zn;b 2 B2g) is the required K3-decomposition, since if v 2 Znnf0;n 2g, then dL(v) = (2n 2) 2 6(2k z) = 6z + 4 = 2 2 and dL(0) = dL(n 2) = (2n 2) 4 6(2k z) = 2 2 2. So L is evenly equitable with 2n 1 edges. Since all edges of di erence 3 are in L, L is connected. Finally, if n = 4, Condition 3 implies 2 = 2 so the result follows from Theorem 2:3. 29 Before proceeding to the general case, because of the limitations of Theorem 2:13, three more special cases need to be handled, namely where 1 = 3 and n 5 (mod 6) and the two cases where n 2 (mod 6) and 1 = 4 or 6. Case 3: Suppose 1 = 3 and n 5 (mod 6). Conditions 1 and 2 imply that 2 3 (mod 6). First suppose n 11. By Case 2, there exists a K3-decomposition (Zn;B1) of 2Kn E(L1) where L1 is a subgraph of 2Kn with ( 2 1)n ( 1 1) edges which is evenly equitable and connected. By Theorem 2:12, there exists a K3-decomposition (Zn;B2) of Kn E(L2) where L2 is a subgraph of Kn consisting of an n 1 cycle; name the vertices so that the vertex not in the cycle has maximum degree in L1. Then (Zn;B1[B2) is the required decomposition with L = G[E(L1)[E(L2)]. Now suppose n = 5. Then Condition 3 in conjunction with the fact that 2 3 (mod 6) implies 2 = 3 so the result follows by Theorem 2:3. Case 4: Suppose 1 = 4 and n 2 (mod 6) with n > 2. Conditions 1 and 2 imply that 2 1 (mod 3). By Case 2, there exist K3-decompositions (Zn;B1) and (Zn;B2) of 2Kn E(L1) and 2Kn E(L2) respectively where L1 is a subgraph of 2Kn with ( 2 2)n ( 1 2) edges which is evenly equitable and connected, and L2 is a subgraph of 2Kn with 2n 2 edges which is evenly equitable and connected. Name the vertices so that G[E(L1)[E(L2)] is also evenly equitable. Then (Zn;B1[B2) is the required decomposition with L = G[E(L1)[E(L2)]. Case 5: Suppose 1 = 6 and n 2 (mod 6) with n> 2. Conditions 1 and 2 imply that 2 0 (mod 3). By Cases 4 and 2, there exist K3-decompositions (Zn;B1) and (Zn;B2) of 4Kn E(L1) and 2Kn E(L2) respectively where L1 is a subgraph of 4Kn with ( 2 2)n ( 1 2) edges which is evenly equitable and connected, and L2 is a subgraph of 2Kn with 2n 2 edges which is evenly equitable and connected. Name the vertices so that G[E(L1)[E(L2)] is also evenly equitable. Then (Zn;B1[B2) is the required decomposition with L = G[E(L1)[E(L2)]. 30 To this point, the theorem is proved if 1 2f1;2g and if ( 1;n)2f(3;5 (mod 6));(4;2 (mod 6));(6;2 (mod 6))g. So now consider the remaining cases. A two-step approach is taken in each of three cases, making use of Theorems 2:13 and 2:17. Case 1: Suppose n 0;1;3; or 4 (mod 6). Let 0 2f1;2g with 0 n (mod 2). Set = 1 0. Since either n or n 1 is divisible by 3 in this case, 1n(n 1)2 0 (mod 3). Also, 1n(n 1)2 ( 2n 1) = 1(1 + n(n 1)2 ) 2n = 1(m(m 1)2 + n(n 1)2 ) 2n 1(m(m 1)2 + n(n 1)2 ) + 2 2n (mod 3) 0 (mod 3) where the last step follows from Condition 1. Therefore, 2n 1 is divisible by 3 . By Condition 2, 2n 1 is even. Since n 0;1;3 or 4 (mod 6), 0n(n 1)2 is divisible by 3. First, suppose 2n 1 n. By Theorem 2:13, there exists a packing (V;B1) of 0Kn with leave a cycle on 2n 1 vertices. By Condition 1 and by de nition, both 1 and 0 respectively are even when n is even; hence is even when n is even. Since n 0;1 (mod 3) and is even when n is even, by Theorem 2:3, there exists a K3-decomposition (V;B2) of Kn. Then (V;B1[B2) is the required packing. Now suppose 2n 1 > n. By Theorem 2:13, let (V;B1) be a packing of 0Kn with leave a cycle on = n vertices when n 0 (mod 3) and = n 1 vertices when n 1 (mod 3). Again is even if n is even so b (n 1)2 c = (n 1)2 . Further, since in this case either n or n 1 is divisible by 3, bn3 (n 1)2 c = n3 (n 1)2 . So by Theorem 2:17, there exists an evenly equitable partial triple system (V;B2) of Kn with n(n 1) 2 ( 2n 1 ) 3 triples; this is an integral number of triples since each of n(n 1)2 , 2n 1, and is divisible by 3. Finally, if n 1 (mod 3), then name the symbols in (V;B2) so that the vertex left out of the n 1 cycle gets maximum degree in the leave of (V;B2). Then (V;B1[B2) is the required packing since jE(L)j= + ( n(n 1)2 3( n(n 1) 2 ( 2n 1 ) 3 )) = 2n 1 and L is easily seen to be evenly equitable and connected. Case 2: Suppose n 5 (mod 6) and 1 > 3. Let 02f1;2;3g with 0 1 (mod 3). Let = 1 0. By the same argument as when n 0 or 1 (mod 3), Condition 1 implies 31 that 1n(n 1)2 ( 2n 1) is divisible by 3. Since 1 0 (mod 3), 0n(n 1)2 ( 2n 1) is also divisible by 3. First suppose that 2n 1 n. By Theorem 2:13, there exists a packing (V;B1) of 0Kn with leave a cycle on 2n 1 vertices. Since 0 (mod 3), by Theorem 2:3, there exists a K3-decomposition (V;B2) of Kn. Then (V;B1[B2) is the required packing. Now suppose 2n 1 > n. Since n 5 (mod 6), mn = 2n 1 (mod 3) and m(m 1) 2 + n(n 1) 2 2 (mod 3); hence, by Condition 1, 1 2 (mod 3). Since n 2 (mod 3) in this case, and since 1 2 (mod 3), 2n 2 1 (mod 3) so 2n 1 1 (mod 3). Also, since n(n 1)2 1 (mod 3), 0n(n 1)2 0 (mod 3). By Theorem 2:13, there exists a packing (V;B1) of 0Kn with leave a cycle on = n 1;n; or n 2 vertices when 0 = 1;2 or 3 respectively. In this case, (n 1) is even and is divisible by 3, sobn3b (n 1)2 cc= n3 (n 1)2 . So by Theorem 2:17, there exists an equitable partial triple system (V;B2) of Kn with n(n 1)2 ( 2n 1 ) 3 triples; this is an integral number of triples since is divisible by 3 and 2n 1 1 0 (mod 3). Finally, if = n 1 orn 2, then name the symbols of (V;B2) so that each vertex not in the n 1 or n 2 cycle gets no smaller degree in the leave of (V;B2) than any vertex in the cycle. Then (V;B1[B2) is the required packing, since L is clearly evenly equitable and connected andjE(L)j= +( n(n 1)2 3( n(n 1) 2 ( 2n 1 ) 3 )) = 2n 1. Case 3: Finally, suppose n 2 (mod 6). By Condition 2, 1 is even, so it can be assumed 1 > 6 (since all smaller cases were handled previously). Recall that n > 2. Let 02f2;4;6gwith 0 1 (mod 6). Set = 1 0. By the same argument as when n 0 or 1 (mod 3), Condition 1 implies that 1n(n 1)2 ( 2n 1) is divisible by 3. Since 1 0 (mod 3), 0n(n 1)2 ( 2n 1) is also divisible by 3. First suppose that 2n 1 n. By Theorem 2:13, there exists a packing (V;B1) of 0Kn with leave a cycle on 2n 1 vertices. Since 0 (mod 6), by Theorem 2:3, there exists a K3-decomposition (V;B2) of Kn. Then (V;B1[B2) is the required packing. Suppose 2n 1 >n. Since n 2 (mod 6), mn = 2n 1 (mod 3) and m(m 1)2 +n(n 1)2 2 (mod 3); hence, by Condition 1, 1 2 (mod 3). Since n 2 (mod 3) in this case, and 32 since 1 2 (mod 3), 2n 2 1 (mod 3) so 2n 1 1 (mod 3). Also, since n(n 1)2 1 (mod 3), 0n(n 1)2 0 (mod 3). By Theorem 2:13, there exists a packing (V;B1) of 0Kn with leave a cycle on = n;n 1; or n 2 vertices when 0 = 2;4 or 6 respectively. In this case, is even and divisible by 3, so bn3b (n 1)2 cc = n3 (n 1)2 . So by Theorem 2:17, there exists an equitable partial triple system (V;B2) of Kn with n(n 1) 2 ( 2n 1 ) 3 triples; this is an integral number of triples since is divisible by 3 and 2n 1 1 0 (mod 3). Finally, if = n 1 or n 2, then name the symbols of (V;B2) so that each vertex not in the n 1 or n 2 cycle gets no smaller degree in the leave of (V;B2) than any vertex in the cycle. Then (V;B1[B2) is the required packing, since L is clearly evenly equitable and connected and jE(L)j= + ( n(n 1)2 3( n(n 1) 2 ( 2n 1 ) 3 )) = 2n 1. 33 Chapter 3 Neighborhoods in Maximum Packings of 2Kn and Quadratic Leaves of Triple Systems 3.1 Introduction In this chapter, the quadratic leave problem is considered again, this time with the focus of allowing 2-cycles in the leave. To do this, a characterization of the possible neighborhood graphs in maximum packings of 2Kn is given which in turn will be used to solve the quadratic leave problem. As mentioned in the introduction, in [9], Colbourn and Rosa characterized the possible neighborhood graphs in a 2-fold triple system on n vertices when n 0 or 1 (mod 3). (A 2-fold triple system is equivalent to a maximum packing in these two cases.) In this chapter, a characterization of the possible neighborhood graphs of vertices in a maximum packing of 2Kn for n 2 (mod 3) is given (see Theorem 3.9). When n 2 (mod 3) the leave of a maximum packing (V;B) of 2Kn is the 2-cycle (a;b) for some a;b2V (with a6= b); see Lemma 3.2. So in this case an additional interesting aspect of nding the neighborhood of a vertex v in a maximum packing of 2Kn arises; the neighborhood is a 2-regular graph on n 2 vertices if v2fa;bg and is a 2-regular graph on n 1 vertices otherwise. The proof technique in this chapter builds on modern observations recently made independently in two papers [3, 22] concerning the existence of leaves of partial hamilton cycle decompositions of Kn. Bryant, Horsley, and Maenhaut have some results which relate to Theorem 3.10. In [4], they show that Kn can be decomposed into 2-regular subgraphs of orders m1;:::;mt provided that n is odd, 3 mi n for 1 i t, and Pmi = n2 . Note that specifying m1;m2;:::;mj (j < t) to be the lengths of the cycles described in Theorem 3.10 is not su cient to force the 2-regular subgraphs to be cycles, nor to force the cycles in the quadratic graph to be vertex disjoint. In [6], Bryant and Horsley extend their rst result by showing 34 that Kn can be decomposed into cycles of orders m1;:::;mt provided that n is odd, 3 mi n for 1 i t, and Pmi = n2 whenever n is su ciently large. Note that Theorem 3.10 cannot be obtained from this result in the special case where = 1 and n is large enough since the cycles in the quadratic graph are not forced to be vertex disjoint. Maximal cycle systems have also been of interest from another perspective. Rather than study the structure of the leave, several papers have considered its size, addressing the spectrum question of nding the set S of integers for which there exists a partial k-cycle system with leave of size l for each l2S. Cycles of length 3 and hamilton cycles have been of particular interest (see for instance [12, 8, 28]). For any multiset D with elements chosen from f1;2;:::;n 1g, let Gn(fDg) be the multigraph with vertex set Zn and edge multiset ffv;v + dgj d 2 D;v 2 Zng reducing sums modulo n. Note that with this de nition Gn(fdg) = Gn(fn dg) and is a 2-regular graph regardless of the value of d (if d = n2 then each component is a 2-cycle). The edges in Gn(fdg) are said to have di erence d. This de nition is slightly non-standard since edges are allowed to have di erence d> n2 , but this approach is very useful when decomposing 2Kn. Iffa;b;cgis a triple on the vertex set Zn then de nefa;b;cg+j =fa+j;b+j;c+jg, reducing sums modulo n. Similarly, if (a0;a1;:::;an) is a cycle on the vertex set Zn then de ne (a0;a1;:::;an) +j = (a0 +j;a1 +j;:::;an +j), reducing sums modulo n. Throughout the chapter, and n are assumed to be positive integers. 3.2 Preliminary Results To start, a well-known result on quasigroups is given. Lemma 3.1. [27] There exists an idempotent quasigroup of order n for all n6= 2. The following is a speci c case of well-known results on packings of Kn, and is su cient for the purposes of this chapter. 35 Lemma 3.2. [14] Suppose 1 and n6= 2. There exists a K3-decomposition of Kn if and only if is divisible by 1. 2 if n 0 or 4 (mod 6), 2. 3 if n 5 (mod 6), and 3. 6 if n 2 (mod 6). Furthermore, there exists a maximum packing of Kn with leave L where: 1. L is a 4-cycle if = 4 and n 2 (mod 3) or = 1 and n 5 (mod 6), and 2. L is a 2-cycle if = 2 and n 2 (mod 3). The next result is a neat way to be able to deal with the many possibilities for Q. Lemma 3.3. For any quadratic multigraph Q on n vertices, there exists a subgraph of Gn(f1;1;2g) which is isomorphic to Q. Proof. For each l with 2 l n, de ne the cycle c(l) of length l in Gn(f1;1;2g) as follows. If l = 2 then let c(l) = (0;1). If l = 2x> 2 then let c(l) = (0;2;4;6;:::;2x 2;2x 1;2x 3;2x 5;:::;1). Finally, if l = 2x 1 then let c(l) = (0;2;:::;2x 2;2x 3;2x 5;:::;1). Suppose that Q is the disjoint union of t cycles of lengths l1;:::;lt (possibly li = 2). For 1 i t let si = Pij=1lj, and let ci = c(li) + si 1, de ning s0 = 0. Then Sti=1ci is a subgraph of Gn(f1;1;2g) and is isomorphic to Q. The following result was proved by Petersen. Lemma 3.4. [26] Let H be any 2k-regular multigraph. There exists a 2-factorization of H. In constructing maximum packings, it will always be rst assumed that the desired neighborhood contains a small cycle, the size of which will depend upon the current case. The following lemma is a well-known approach that will allow for the extension of these constructions to cases where the prescribed small cycle is not present by combining two cycles in the neighborhood of a vertex v into a single cycle. 36 Lemma 3.5. Let (V;S) be a partial 2-fold triple system, and let v2V. Suppose that fa;bg andfc;egare edges in disjoint cycles in the neighborhood of v, and further suppose that there is some w2V with w6= v such that ffa;c;wg;fb;e;wgg S. Then there exists a partial 2-fold triple system (V;S0) such that 1. E(S) = E(S0), 2. the neighborhood of v in S0 is obtained from the neighborhood of v in S by replacing one copy of the edges fa;bg and fc;eg with one copy of the edges fa;cg and fb;eg. Proof. De ne S0 = (Snffv;a;bg;fv;c;eg;fw;a;cg;fw;b;egg) [ffv;a;cg;fv;b;eg;fw;a;bg;fw;c;egg. The next lemma settles cases that will be used in Section 3 for the general construction, and includes a proof of Theorem 3:9 when n2f5;8g. When n2f4;6g, the results follow from the results of Colbourn and Rosa but are included here for completeness. Lemma 3.6. Let S =f(4;C3);(6;C5);(5;C3);(5;C4);(8;C3[C3);(8;C2[C4);(8;C2[C2[ C2);(8;C6);(8;C4[C3);(8;C2[C5);(8;C2[C2[C3);(8;C7)g. For each (n;Q)2S, there exists a maximum packing of 2Kn such that the neighborhood of some vertex is Q. Proof. Let the vertex set of Kn be V = fa;bg[Zn 2. In each case, a maximum packing is formed with leave the 2-cycle (a;b) if n2f5;8g and the empty leave if n2f4;6g. All addition in the following is de ned modulo n 2. In each case, the set of blocks de ned produce a maximum packing of 2Kn. Let n = 4. De ne B = ffa;b;0g;fa;b;1g;fa;0;1g;fb;0;1gg. Then the neighborhood of a is C3. Let n = 6. De ne B =ffa;b;0g;fa;b;1g;fa;0;2g;fa;1;3g;fa;2;3g;fb;0;3g;fb;1;2g; fb;2;3g;f0;1;2g;f0;1;3gg. Then the neighborhood of a is C5. Let n = 5. De ne B =ffj;i;i + 1gjj2fa;bg;0 i 2g. Then the neighborhood of a is C3 and the neighborhood of 0 is C4. 37 Let n = 8. De ne B1 = ffi;i + 1;i + 3g;fa;i;i + 2g;fb;i;i + 1gj i 2 Z6g, B2 = ffi;i+ 1;i+ 2g;fa;i;i+ 3g;fb;i;i+ 2gji2Z6g, B3 =ff0;2;4g;f0;2;5g;f0;3;5g;f1;2;4g; f1;3;4g;f1;3;5g;fb;0;3g, fb;0;4g;fb;1;2g;fb;1;5g;fb;2;3g;fb;4;5g;fa;0;1g;fa;0;1g; fa;2;3g;fa;3;4g;fa;4;5g;fa;2;5gg, andB4 =ffa;0;1g;fa;0;1g;f0;2;3g;f0;2;3g;f0;4;5g; f0;4;bg;f0;5;bg, fa;2;4g;fa;2;5g;fa;3;4g;fa;3;5g;f1;2;4g;f1;2;bg;f1;3;5g;f1;3;bg; f1;4;5g;f2;5;bg;f3;4;bgg. In B1, the neighborhood of a is C3[C3 and of b is C6. In B2, the neighborhood of a is C2[C2[C2. In B3, the neighborhood of a is C2[C4, of 0 is C2[C5, and of 2 is C7. In B4, the neighborhood of 0 is C2[C2[C3. Finally, using an approach similar to Lemma 3.5, the neighborhood of 0 in (B4nff0;1;ag;f0;2;3gfa;2;5g;f1;3;5gg)[ ffa;0;2g;f0;1;3g;fa;1;5g;f2;3;5gg is C4[C3. Before proceeding to the main theorem of this chapter, the powerful result on Langford sequences that was proved over a series of papers is given again (see for example [29]). A Langford sequence of order m 1 and defect 1 is a sequence L = (l1;l2;:::;l2m) of 2m positive integers satisfying the conditions (a) for every k2f ; + 1;:::; + m 1g, there exist exactly two integers li;lj in L such that li = lj = k, and (b) if li = lj = k, then ji jj= k. A hooked Langford sequence of order m 1 and defect 1 is a sequence L = (l1;l2;:::;l2m;l2m+1) of 2m+ 1 nonnegative integers satisfying the conditions (a) l2m = 0 (b) for every k2f ; + 1;:::; + m 1g, there exist exactly two integers li;lj in L such that li = lj = k, and (c) if li = lj = k, then ji jj= k. For emphasis, a Langford sequence is sometimes called a perfect Langford sequence. 38 Theorem 3.7. [29] A Langford sequence of order m and defect exists if and only if 1. m 1, and 2. either m 0;1 (mod 4) and is odd, or m 0;3 (mod 4) and is even. A hooked Langford sequence of order m and defect exists if and only if 3. m(m 2 + 1) + 2 0, and 4. either m 2;3 (mod 4) and is odd, or m 1;2 (mod 4) and is even. Remark: Notice that every pair of integers m and satis es either Condition 2 or Condition 4. Also, if = 2 then Conditions 1 and 3 are satis ed for all m 1 when Conditions 2 and 4 respectively are satis ed. The following well-known result is the purpose of introducing these sequences. Lemma 3.8. If there exists a Langford sequence or a hooked Langford sequence of order m and defect then, for each n > + 3m, there exists a K3-decomposition of Gn(f ; + 1;:::; + 3m 1g) or of Gn(f ; + 1;:::; + 3m 2; + 3mg) respectively. Proof. Let (l1;:::;l2m) or (l1;:::;l2m+1) be a Langford sequence or a hooked Langford se- quence respectively. De ne B =ff0; +m 1 +i; +m 1 +jg+tjli = lj;t2Zng. Then (Zn;B) is the required decomposition. 3.3 Neighborhoods for 2K3x+2 The rst of the two main results of this chapter is now stated and proved. Theorem 3.9. Let n 2 (mod 3) with n> 2, and let Q be a 2-regular multigraph on either n 2 or n 1 vertices. Then there exists a maximum packing of 2Kn with leave a 2-cycle such that the neighborhood graph of some vertex is Q if and only if (n;Q)6= (5;C2[C2). 39 Proof. If there exists a maximum packing of 2K5 such that the neighborhood of some vertex is C2 [C2, then deleting the triples containing this vertex leaves the graph 2K2;2 which contains no K3; so this case is not possible. The su ciency is now proved. So let Q be a 2-regular graph on n 2 or n 1 vertices, n 2 (mod 3), and (n;Q)6= (5;C2[C2). Let jV(Q)j= n 2 + with 2f0;1g. In each case, a maximum packing (V;B) of 2Kn is produced in which the neighborhood of the vertex 10 is Q. If n2f5;8g then the result follows from Lemma 3.6, so it can be assumed that n = 3k + 5 11. Note that if jV(Q)j = n 2 then 10 must be in the leave, so the maximum packing will be constructed with leave the 2-cycle (10;11). If jV(Q)j= n 1 then 10 cannot be in the leave, so for notational convenience the maximum packing will be constructed with leave the 2-cycle (11;13). Case 1: Suppose that Q contains a cycle c of length 3 + . Let V = S4i=0f1ig[Z3k and name the cycle c = (12 ;13 ;:::;14). By Lemma 3.6, let (f1i ji2Z5g;B0) be a maximum packing of 2K5 with leave the 2-cycle (11;13 ) in which the neighborhood of 10 is the (3 + )-cycle c. By Lemma 3:3, let G0 be a subgraph of G3k(f1;3k 2;3k 1g) isomorphic to Qnfcg. Since G3k(f1;3k 2;3k 1g) E(G0) is a 4-regular graph, by Lemma 3:4 it has a 2- factorization fG1;G2g. Let d = 3k 4 if k 2 0 or 3 (mod 4) and let d = 3k 5 if k 2 1 or 2 (mod 4). By Lemma 3:4 letfG3;G4gbe a 2-factorization of G3k(f3k 3;dg). Let B1 =ff1i;y;zgjfy;zg2E(Gi);0 i 4g. So the neighborhood of 10 is Q, and all that remains to do is to partition the edges of G3k(f2;3;:::;3k 4gnfdg) into triples; note that if k = 2 then this graph has no edges, so it can be assumed that k 3. By the remark following Theorem 3.7, there exists either a perfect or a hooked Langford sequence of order k 2 1 and defect 2, so the choice of d ensures that by Corollary 3.8 there exists a K3- decomposition (Z3k;B2) of G3k(f2;3;:::;3k 4gnfdg). Then (f1iji2Z5g[Z3k;S2i=0Bi) is the required decomposition. 40 Case 2: Suppose that Q contains a cycle c0 of length x + 4 + 5 + . Let V = S4 i=0f1ig[Z3k and name the cycle c0 = (0;1;:::;x 1;12 ;13 ; :::;14;x). De ne the cycles c00 = (12 ;13 ;:::;14) and c000 = (0;1;2;:::;x 1;x) (so if x = 1 then c000 is a 2-cycle). Let Q0 be formed from Q by replacing c0 with c00[c000. Since Q0 contains a cycle of length exactly 3 + , the argument in Case 1 can be used to produce a packing (V;B0) of 2Kn 5 with leave S4i=0Gi where G0 = Q0nfc00gandfG1;:::;G4gis a 2-factorization of G0 = G3k(f1;3k 1;3k 2;3k 3;dg) E(G0) withd2f3k 4;3k 5g. Note thatfx 1;xg V(c000) and that x+1 =2V(c000) since x+4+ jV(Q)j= n 2+ = 3k+2+ implies that x 3k 2 (so x + 16= 0). Therefore G0 contains two copies of the edge fx;x + 1g (one of di erence 1 and one of di erence 3k 1) and one copy of the edgefx 1;x+ 1g(of di erence 3k 2), so one copy of the edge fx;x+ 1g must be in a di erent 2-factor than the edge fx 1;x+ 1g; say these 2-factors are G4 and G2 respectively. By Lemma 3.6, let (f1iji2Z5g;B1) be a maximum packing of 2K5 with leave the 2-cycle (11;13 ) such that the neighborhood of 10 is the ( +3)-cycle c00. Then (f1iji2Z5g[Z3k;B0[B1[ff1i;a;bgjfa;bg2E(Gi)g) is a maximum packing of 2Kn such that the neighborhood of10 is Q0. Finally, by applying Lemma 3.5 to this maximum packing with v =10, w = x+1, a =12 , b =14, c = x 1, and e = x, a maximum packing of 2Kn in which the neighborhood of 10 is Q is produced. Case 3: Suppose that = 1 and each cycle in Q is a 2-cycle. Then n is odd so let n = 6l+5 with l 1. Let V =f10g[(Z3l+2 Z2). By Lemma 3:1, let (Z3l+2; ) be an idempotent quasigroup. By Lemma 3.2, there exists a maximum packing (Z3l+2 f1g;B1) of 2K3l+2 with leave a 2-cycle c. Then (f10g[Z3l+2 Z2;B1[ff(a;0);(b;0);(a b;1)g;f(a;0);(b;0);(b a;1)gj 0 a < b 3l + 1g[ff10;(a;0);(a;1)g;f10;(a;0);(a;1)gja2 Z3l+2g) is the required decomposition with leave c. Case 4: In view of Cases 1 and 2, suppose that if = 0 then each cycle in Q has length 2 or 4, and if = 1 then each cycle in Q has length 2;3; or 5. In view of Case 3, if = 1 then also assume that Q contains at least one cycle of length 3 or 5. 41 Case 4.1: Assume that n 17. In this subcase it is convenient to rede ne k so that n = 3k + 8; so k 3. Let V =f1iji2Z8g[Z3k. Suppose = 0. If Q contains only 4-cycles then let Q0 be formed from Q be replacing one 4-cycle, say (1;16;17;2), with the two 2-cycles (16;17) and (1;2), and if Q contains a 2-cycle, say (16;17), then let Q0 = Q. We can assume that either Q0 contains both the 4-cycle c1 = (12;13;14;15) and the 2-cycle c2 = (16;17), or Q0 contains the three 2-cycles c1 = (12;13);c2 = (14;15); and c3 = (16;17); let c = fc1;c2g or fc1;c2;c3g respectively. Suppose = 1 (and hence jV(Q)j = n 1 1 (mod 3)). Since jV(Q)j 1 (mod 3), Q contains at least two cycles of length 2 (mod 3). If Q contains two 5-cycles then let them be (0;1;16;17;2) and c1 = (11;12;13;14;15); form Q0 from Q be replacing the rst 5-cycle with the two cycles c2 = (16;17) and c3 = (0;1;2), and let c = fc1;c2g. If Q contains exactly one 5-cycle and a 2-cycle then let them be c1 = (11;12;13;14;15) and c2 = (16;17); let Q0 = Q and c = fc1;c2g. If Q contains no 5-cycles then it must contain two 2-cycles and a 3-cycle (in view of Case 3), say c1 = (11;12), c2 = (16;17), and c3 = (13;14;15); let Q0 = Q and c =fc1;c2;c3g. In either case, by Lemma 3:6 let (f1i ji2 Z8g;B0) be a maximum packing of 2K8 with leave the 2-cycle (11;13 ) such that the neighborhood of 10 is c . By Lemma 3:3, let G0 be a subgraph of G3k(f1;3k 2;3k 1g) isomorphic to Q0nfc g. Let d = 3k 7 if k 3 0 or 3 (mod 4) and let d = 3k 8 if k 3 1 or 2 (mod 4). Since G = G3k(f1;3k 1;3k 2;3k 3;3k 4;3k 5;3k 6;dg) E(G0) is a 14-regular graph, by Lemma 3:4 it has a 2-factorization fG1;G2;:::;G7g. Note that if Q06= Q, then Q0nc contains either the cycle (1;2) or the cycle (0;1;2), which implies that G0 does not contain any copies of the edge f1;3g or f2;3g and hence that G contains two copies of the edge f2;3g and one copy of the edge f1;3g. Thus one copy of the edge f2;3g must be in a di erent 2-factor than the edge f1;3g; say these 2-factors are G7 and G6 respectively. Let B1 = ff1i;y;zgjfy;zg2E(Gi);0 i 7g. So the neighborhood of 10 is Q0, and all 42 that remains to do is to partition the edges of G3k(f2;3;:::;3k 7gnfdg) into triples; to do so, note that this graph is graph is empty if k = 3, so we can assume that k 4. There exists either a perfect or a hooked Langford sequence of order k 3 1 and defect 2, so the choice of d ensures that by Corollary 3.8 there exists a K3-decomposition (Z3k;B2) of G3k(f2;3;:::;3k 7gnfdg). Then (f1iji2Z8g[Z3k;S2i=0Bi) is a maximum packing of 2Kn such that the neighborhood of10 is Q0. If Q06= Q then apply Lemma 3.5 with v =10, w = 3, a =16, b =17, c = 1, and e = 2 to produce a maximum packing of 2Kn in which the neighborhood of 10 is Q. Case 4.2: Assume that n = 14, jV(Q)j = 13, and Q contains a 5-cycle, c. By Lemma 3.6, let (f1i ji2Z6g;B1) be a K3-decomposition of 2K6 such that the neighborhood of 10 is the 5-cycle c2Q. By Lemma 3:3, let G0 be a subgraph of G8(f1;6;7g) isomorphic to Qnfcg. Since G8(f1;6;7g) E(G0) is a 4-regular graph, by Lemma 3:4 it has a 2-factorization fG1;G2g. Let B2 =ff0;2;5g;f1;3;6gg. Then (G8(f2;3;4;5g))n(E(B2)[f4;7g[f4;7g) is a 6-regular graph so it has a 2-factorization fG3;G4;G5g. Then (f1i ji2Z6g[Z8;B1[ B2[ffa;b;1igjfa;bg2E(Gi);0 i 5g) is the required decomposition (with leave the 2-cycle (4;7)). Case 4.3: Assume that n = 14,jV(Q)j= 13, and Q contains a 3-cycle, c. By Lemma 3.6, let (f1iji2Z4g;B1) be a K3-decomposition of 2K4 such that the neighborhood of10 is the 3-cycle c2Q. By Lemma 3:3, let G0 be a subgraph of G10(f1;8;9g) isomorphic to Qnfcg. Since G10(f1;8;9g) E(G0) is a 4-regular graph, by Lemma 3:4 it has a 2-factorization fG1;G2g. LetB2 =ff0;2;5g;f0;5;7g;f1;3;6g;f1;6;8g;f2;4;7g;f2;7;9g;f3;5;8g;f0;3;8g; f0;4;6g;f1;5;9g;f0;3;7g;f1;4;7g;f1;4;8g;f3;6;9g;f2;6;9g;f2;5;8gg[ff13;i;i+4gji2 Z10g. Then (f1iji2Z4g[Z10;B1[B2[ffa;b;1igjfa;bg2E(Gi);0 i 2g) is the required decomposition (with leave the 2-cycle (4;9)). Case 4.4: Assume that n = 14,jV(Q)j= 12, and Q contains 4-cycles where 0 3. Let B = (ffi;i + 3;i + 4g;fi;i + 2;i + 5g;fi;i + 4;i + 5g;f10;i;i + 6g;f11;i;i + 2gji2 Z12gnffj;j + 3;j + 4g;fj + 4;j + 6;j + 9g;f10;j;j + 6g;f10;j + 3;j + 9gj 1 j 43 g)[ffj;j + 4;j + 6g;fj + 3;j + 4;j + 9g;f10;j;j + 3g;f10;j + 6;j + 9gj1 j g. Then (Z12[f10;11g;B) is a maximum packing of 2K14 with leave (10;11) such that the neighborhood of 10 consists of 4-cycles and 12 4 2 2-cycles as required. Case 4.5: Assume that n = 11. It is impossible forjQj= 9 and to have Q consist only of 2-cycles and 4-cycles, so assume that jQj= 10. Let B =ff10;0;1g;f10;0;1g;f10;2;3g; f10;2;3g;f10;4;5g;f10;4;6g;f10;5;6g;f10;7;8g;f10;7;9g;f10;8;9g;f0;2;4g; f0;2;7g;f0;3;5g;f0;3;8g;f1;2;6g;f1;2;9g;f1;3;4g;f1;3;7g;f0;4;8g;f0;5;9g;f0;6;7g; f0;6;9g;f1;4;9g;f1;5;7g;f1;5;8g;f1;6;8g;f2;4;8g;f2;5;8g;f2;5;9g;f2;6;7g;f3;4;9g; f3;5;7g;f3;6;8g;f3;6;9g;f4;5;6g;f7;8;9gg. Then (V = f10g[Z10;B) is a maximum packing of 2K11 with leave (4;7) in which the neighborhood of10 is C2[C2[C3[C3. Since the triples f0;4;8g;f1;5;8g2B, apply Lemma 3.5 to (V;B) with v = 10, w = 8, a = 0, b = 1, c = 4, and e = 5, to replace the cycles (0;1) and (4;5;6) in the neighborhood of 10 with the cycle (0;1;5;6;4), so in the resulting maximum packing (V;B0) the neighborhood of 10 is C5[C2[C3. Finally, since the triples f2;7;6g;f3;9;6g2B0, apply Lemma 3.5 to (V;B0) with v =10, w = 6, a = 2, b = 3, c = 7, and e = 9, to replace the cycles (2;3) and (7;8;9) in the neighborhood of10 with the cycle (2;3;9;8;7), so in the resulting maximum packing (V;B00) the neighborhood of 10 is C5[C5. 3.4 Quadratic Leaves Having proved Theorem 3:9, it can now be used along with the corresponding Colbourn and Rosa result (see [9]) to assist in proving the second main result of this chapter. Theorem 3.10. Let Q be a quadratic graph in Kn. There exists a K3-decomposition of Kn E(Q) if and only if 1. (n 1) is even, 2. jE( Kn)j jE(Q)j is divisible by 3, 3. ( ;n;Q) =2f(1;7;C3[C3);(1;9;C4[C5);(2;6;C3[C3);(2;5;C2[C3)g, and 44 4. if 6= 2 then n6= 2. Proof. To see the necessity of Conditions (1 4) consider the following. If ( ;n;Q) 2 f(1;7;C3[C3);(1;9;C4[C5)g then by the Colbourn and Rosa result (see Theorem 1.2), there is no K3-decomposition of Kn E(Q). If ( ;n;Q) 2f(2;5;C2[C3);(2;6;C3[C3)g and if there exists a K3-decomposition (Zn;B1) of 2Kn E(Q) then (Zn+1;B1[ffn;a;bgj fa;bg2E(Q)g) is a K3-decomposition of 2Kn+1 in which the neighborhood of n is Q; but this contradicts Theorem 1.1. This proves the necessity of Condition (3). The necessity of Conditions (1) and (2) follows since each vertex in each triple has even degree and each triple contains 3 edges respectively. The necessity of Condition (4) is clear since K2 contains no copies of K3. To prove the su ciency, the result is clear if n 2, and the result follows from Theorem 1.2 if = 1, so assume that n 3 and 2. Let Q be a quadratic graph such that Conditions (1 3) are satis ed. Case 1: Suppose = 2. If (n;Q) 2f(5;C2);(6;C3)g then the result follows in each case from Lemma 3.2 by taking a maximum packing of 2Kn, then removing any one triple if n = 6. By Condition 2, jE(Q)j n (mod 3) where = 1 if n 1 (mod 3) and = 0 otherwise. Form the 2-regular graph Q0 on n vertices by adding n jE(Q)j 3 3-cycles to Q (by Condition (2) this is an integral number of 3-cycles). Let B =ffx;y;zgj(x;y;z)2Q0nQg. It can be assumed that (n+1;Q0) =2f(7;C3[C3);(6;C2[C3)gsince (n+1;Q0)2f(7;C3[C3);(6;C2[C3)gonly if (n;Q)2f(5;C2);(6;C3);(5;C2[C3);(6;C3[C3)g, where the rst two are handled at the beginning of this case and the last two are prohibited by Condition 3. So by either Theorem 1.1 or 3.9 there exists a maximum packing (Zn+1;B0) of 2Kn+1 in which the neighborhood of the vertex n is Q0. Then (Zn;(B0nfb2B0jn2bg)[B) is the required decomposition. Case 2: Suppose > 2 and n 0 or 1 (mod 3). First suppose that (n;Q)6= (6;C3[C3). By Condition 2, jE(Q)j 0 (mod 3) regardless of the value of . By the result of Case 1, let (Zn;B0) be a K3-decomposition of 2Kn E(Q). Let (Zn;B1) be a K3-decomposition of 45 ( 2)Kn; this exists by Lemma 3.2 since n 0 or 1 (mod 3) and since if n is even then 2 is even by Condition (1). Then (Zn;B0[B1) is the required decomposition. Using Lemma 3.2, if (n;Q) = (6;C3[C3) then let (Z6;B1) and (Z6;B2) be K3-decompositions of 2K6 such that f0;1;2g2B1 and f3;4;5g2B2, and let (Z6;B3) be a K3-decomposition of ( 4)K6. Then (Z6;B1[B2[B3nff0;1;2g;f3;4;5gg) is the required decomposition. Case 3: Suppose > 2 and n 2 (mod 3). Let V(Q) Zn. By Condition (4), n6= 2. First suppose that n 6= 5. Let (mod 3) with 2f2;3;4g if n 5 (mod 6) and 2f2;4;6g if n 2 (mod 6). By Lemma 3.2 and Conditions (1) and (2) there exists a K3-decomposition (Zn;B0) of ( )Kn. If = 2 then by Condition (2) jE(Q)j 2 (mod 3), so by Case 1 let (Zn;B1) be a K3-decomposition of 2Kn E(Q). If = 4 then by Condition (2)jE(Q)j 1 (mod 3) sojE(Q)j n 1, so say 0 =2V(Q) and that (1;:::;x) is a cycle in Q. Form Q0 from Q by replacing the cycle (1;:::;x) in Q with the cycle (0;1;:::;x). By Case 1 there exists a K3-decomposition (Zn;B01) of 2Kn E(Q0). By Lemma 3.2 let (Zn;B001) be a maximum packing of 2Kn with leave the 2-cycle (1;x). Let B1 = B01[B001 [f0;1;xg. If 2f3;6g then by Condition (2) jE(Q)j 0 (mod 3), so say 0;1 =2 V(Q). Form Q0 from Q by adding the 2-cycle (0;1). By Case 1 let (Zn;B01) be a K3-decomposition of 2Kn E(Q0). By Lemma 3.2 let (Zn;B001) be a maximum packing of ( 2)Kn with leave the 4-cycle (2;0;3;1). Let B1 = B01[B001 [ff0;1;2g;f0;1;3gg. Then for each 2f2;3;4;6g, (Zn;B0[B1) is the required decomposition. Finally, suppose that n = 5. Based on the above argument, it su ces to nd packings of K5 with leave Q for ( ;Q)2f(2;C5);(3;C3);(4;C4);(4;C2[C2);(5;C2[C3)g. ( ;Q) = (2;C5) was handled in Case 1. When ( ;Q) = (3;C3), by Lemma 3.2 let (Z5;B) be a K3- decomposition of 3K5 and let b2B; then (Z5;Bnb) is the required decomposition. When ( ;Q) = (4;C4) the result follows from Lemma 3.2 by taking a maximum packing of 4K5. When ( ;Q) = (4;C2[C2), by Lemma 3.2 let (Z5;B1) and (Z5;B2) be maximum packings of 46 2K5 with leaves (0;1) and (2;3) respectively; then (Z5;B1[B2) is the required decomposition. Finally, when ( ;Q) = (5;C2[C3), by Lemma 3.2 let (Z5;B1) be a K3-decomposition of 3K5 that contains the triple f0;1;2g, and let (Z5;B2) be a maximum packing of 2K5 with leave the 2-cycle (3;4); then (Z5;B1[B2nf0;1;2g) is the required decomposition. 47 Chapter 4 Neighborhoods in Maximum Packings of 2Kn- A Second Version 4.1 Introduction Having completed the solution to the neighborhood graph problem in the last chapter by solving the case where n 2 (mod 3), this chapter focuses on nding a uni ed proof for the neighborhood graph problem. While the proof technique used in the last chapter for n 2 (mod 3) is similar in principle to the proof technique used in the corresponding Colbourn and Rosa result, it does not seem that the techniques used in either proof can be used to readily obtain the other result, even if one \allows" extreme cases (such as the case when each cycle in the neighborhood has length two) to be handled using alternate methods. In this chapter, a new, simpler, and uni ed proof that obtains both results is provided (see Theorem 4.5). However, this new proof relies heavily on a major result, namely a recent and quite powerful result due to Bryant, Horsley, and Pettersson (see Theorem 4.3). Section 4:2 will begin with some well-known lemmas that are useful in handling extreme cases of Theorem 4.5. The theorem of Bryant, Horsley, and Pettersson will then be given and used to establish a lemma that will be used in several cases of the proof of the main theorem. Finally, Section 4:3 contains the new proof of the main theorem. 4.2 Preliminary Results To begin this section, two well-known results are given, one being on idempotent quasi- groups and the other on maximum partial triple systems. These lemmas will be used to handle extreme cases of the main theorem (speci cally the cases where n 1 or 5 (mod 6) and Q contains only 2-cycles). 48 Lemma 4.1. [27] There exists an idempotent quasigroup of order n for all n6= 2. The second lemma is more extensive than what appears below; however, what appears below is su cient for this chapter. Lemma 4.2. [14] The leave of a maximum partial triple system of Kn is 1. ? if = 2 and n 0;1 (mod 3), 2. a 2-cycle if = 2 and n 2 (mod 3), 3. a K1;3 and n 42 independent edges if = 1 and n 4 (mod 6), and 4. a 1-factor if = 1 and n 2 (mod 6). The powerful cycle-decomposition theorem of Bryant, Horsley, and Petterson from [5] appears next. Theorem 4.3. [5] 1. Let n be odd. There exists a decomposition of Kn into cycles of length m1;:::;mt if and only if (a) 3 mi n for 1 i t and (b) Pti=1mi = n2 . 2. Let n be even. There exists a decomposition of Kn into cycles of length m1;:::;mt and a 1-factor F if and only if (a) 3 mi n for 1 i t and (b) Pti=1mi = n2 n2 . This result provides the backbone of the proof technique used in this chapter, estab- lishing that Kn minus the edges of a certain set of cycles and possibly a 1-factor can be decomposed into triples. 49 The full power of this result is not needed for the main theorem, since at most three cycle lengths are chosen for any particular case. However, while older and more basic results can be used in many of the cases, it does not seem like older results are su cient to handle all cases in the proof of the theorem (for instance, the case in which Kn needs to be decomposed into a 1-factor, a Hamilton cycle, a near Hamilton cycle, and triples.) A lemma that will be used in multiple cases in the proof of Theorem 4.5 is now given. The lemma and the proof of it will look quite similar to the proofs that appear in the cases of the proof of the main theorem; this lemma is stated here however since it is used in several cases of the main theorem. Lemma 4.4. Let n 0 (mod 3) and let Q be a 2-regular graph on n vertices. Then for any integer 2 k n 1, there exists a decomposition of 2Kn into triples and k 2-factors, one of which is Q. Proof. Let 2f0;1g with n (mod 2). Let Q = fc0;:::;cq 1g, where for each i2Zq, the cycle ci = (ci;1;:::;ci;li) has length li. Since n 0 (mod 3), the number of edges in any Hamilton cycle of Kn and any 1-factor of Kn is a multiple of 3. Further, since jE(Kn)j 0 (mod 3), by Theorem 4.3, Kn can be decomposed into j Hamilton cycles for 0 j n 2+ 2 , 1 1-factors, and triples. So let (Zn;B1) be a K3-decomposition of Kn E(G1), where G1 consists of the h = minfk 1;n 2+ 2 g Hamilton cycles H1;:::;Hh, along with the 1-factor F0 if = 0. In particular, let H1 = (c0;1;:::;c0;l0;c1;1;:::;c1;l1;:::;cq 1;1;:::;cq 1;lq 1). Let (Zn;B2) be a K3-decomposition of Kn E(G2) where G2 contains the k h 1 + Hamilton cycles Hh+2 ;:::;Hk, along with the 1-factor F1 if = 0. Note that if = 1, then k h 1 + = k h k (k 1) = 1 so G2 contains a Hamilton cycle in this case. If = 1 then let Hh+1 = (c0;1;c0;l0;c1;1;c1;l1;:::;cq 1;1;cq 1;lq 1;v1;:::;vn 2q) where v1;:::;vn 2q are arbitrarily named. If = 0 then name the vertices so that q of the edges in F1 are in ffci;1;ci;ligji2Zqg and let Hh+1 = F0[F1. Let H01 be the 2-factor induced by (E(H1)[ffci;1;ci;ligji2Zqg)nffci;li;ci+1;1gji2Zqg reducing the sum in the subscript modulo q. Then H01 Q. The graph H0h+1 induced by 50 E(H1)[E(Hh+1) E(H01) is a 2-factor. Finally, for i2f1;2;:::;kgnf1;h+1g, let H0i = Hi. Then (Zn;B1[B2[[i2ZkH0i) is the required decomposition. 4.3 Main Result The main theorem is now stated and proved. The theorem was previously proved by Colbourn and Rosa in [9] when n 0 or 1 (mod 3) and in Chapter 3 when n 2 (mod 3). Theorem 4.5. [7, 9] Suppose n6= 2. Let Q be a 2-regular multigraph on n 1 vertices with 2f0;1g. Then there exists a maximum packing of 2Kn (possibly the leave is empty) such that the neighborhood graph of some vertex is Q if and only if 1. = 0 if n 0 or 1 (mod 3) and 2. (n;Q) =2f(5;C2[C2);(6;C2[C3);(7;C3[C3)g. Proof. If n 0 or 1 (mod 3), then a maximum packing of 2Kn is a 2-fold triple system, so the neighborhood graph of every vertex will be a 2-regular graph on n 1 vertices so = 0 in these cases, which shows the rst condition is necessary. If (n;Q) = (5;C2[C2);(6;C2[C3); or (7;C3[C3) and there exists a maximum packing of 2Kn such that the leave of some vertex v is Q, then deleting the triples containing v leaves the graph K2W2K2, K2W2K3, or K3W2K3 respectively. So each graph can be thought of as a graph with two parts with 2 edges joining each pair of vertices in di erent parts. In each case, any triple that contains an edge with its incident vertices in di erent parts (a mixed edge) contains 2 such edges and 1 edge whose incident vertices lie in the same part (a pure edge). But in each case, there are more than twice as many mixed edges as pure edges remaining. Hence these cases are not possible. To prove the su ciency, two extreme cases (Case 1) will be followed by 9 main cases. While this is a large number of cases, most follow from Lemma 4.4 or from similar ideas. Let Q be a 2-regular multigraph on n 1 vertices (with the size of Q speci ed in each case) such that (n;Q) =2f(5;C2[C2);(6;C2[C3);(7;C3[C3)g. 51 Case 1: Suppose n 1 or 5 (mod 6) and that Q consists entirely of 2-cycles (so since n is odd then = 0). By assumption (n;Q) 6= (5;C2[C2), and the case where n = 1 is trivial. So it can be assumed that n 7; let n = 6l + 1 + with l 1 and 2f0;4g. Let V = f11g[(Z3l+ 2 Z2). By Lemma 4:1, let (Z3l+ 2; ) be an idempotent quasigroup (l 1, so 3l + 2 3, so the quasigroup exists). By Lemma 4.2, there exists a maximum packing (Z3l+ 2 f1g;B1) of 2K3l+ 2 with leave c where c is a 2-cycle if = 4 and c = ? otherwise. Then (f11g[(Z3l+ 2 Z2);B1[ff(a;0);(b;0);(a b;1)g;f(a;0);(b;0);(b a;1)gj 0 a 8, a maximum packing is constructed on the vertex set Zn 4[f1jj1 j 4g where the neighborhood of11 is Q =fc0;:::;cq 1g, where c0 = (12;13;14), and the q 1 other-cycles are de ned on the vertex set Zn 4. The maximum packing will be constructed so that the leave will be (13;a), where a is de ned below. 54 For each i2(Zqnf0g), let ci = (ci;1;:::;ci;li) where li is the length of ci. In this case, n 4 4 (mod 6) and 10 and thus (n 4)2 (n 4) n 42 (n 4 1) and (n 4)2 (n 4) n 42 are both divisible by 3 and nonnegative. So by Theorem 4.3, let (Zn 4;B1) be a K3- decomposition of Kn 4 (E(H1)[E(H3)[E(F1)) and let (Zn 4;B2) be a K3-decomposition of Kn 4 (E(H2)[E(F2)) where H1 and H2 are Hamilton cycles, H3 is a near-Hamilton cycle with arbitrarily named vertex a2Zn 4 omitted, F1 and F2 are 1-factors, and H1 and H2 are named as follows: Let H1 = (c1;1;:::;c1;l1;c2;1;:::;c2;l2;:::;cq 1;1;:::;cq 1;lq 1). Let H2 = (c1;1;c1;l1;c2;1;c2;l2;:::;cq 1;1;cq 1;lq 1;v1;:::;vn+2 2q) where v1;:::;vn+2 2q are arbi- trarily named. Let H01 be the graph induced by (E(H1)[ffci;1;ci;ligji2Zqnf0gg)n(ffci;li;ci+1;1gji2 Zqnf0;q 1gg[ffcq 1;lq 1;c1;1gg). Let H2 be the graph induced by (E(H1)[E(H2))nE(H01). Then H01 and H02 are 2-regular spanning subgraphs of Kn 4, with the set of cycles formed by the components in H01 being Qnc0. Let H03 = H3 and H04 be the graph induced by E(F1)[E(F2). Let (f1j j1 j 4g;B3) be a K3-decomposition of 2K4 (where the neighborhood of 11 is the 3-cycle (12;13;14)). Then (Zn 4[f1j j1 j 4g;B1[B2[B3[ff1i;ai;bigjfai;big2E(H0i)g) is the required decomposition. Case 6: Suppose n 0 (mod 3), = 0, and that Q has a 2-cycle. A maximum packing is constructed on the vertex set Zn 3 [ff1jg j 1 j 3g where the neighborhood of 11 is Q = fc0;:::;cq 1g, where c0 = (12;13), and the q 1 other-cycles are de ned on the vertex set Zn 3. Note that n6= 6, since otherwise Q = C2[C3 and (n;Q)6= (6;C2[C3) by assumption. The case n 3 is trivial. Otherwise w = n 3 0 (mod 3) and 3 w 1, so by Lemma 4.4, there exists a K3-decomposition (Zn 3;B) of 2Kn 3 (E(H01)[E(H02)[E(H03)) where H01; H02; and H03 are 2-regular graphs and H01 Qnc0. 55 Let (ff1jgj1 j 3g;B3) be a K3-decomposition of 2K3 (where the neighborhood of 11 is the 2-cycle (12;13)). Then (Zn 3[ff1jgj 1 j 3g;B1[B2[B3[ff1i;ai;bigjfai;big2E(H0i)g) is the required decomposition. Case 7: Suppose n 0 (mod 6), = 0, and that Q has no cycles of length 2 (and hence one of length at least 4). First, suppose n = 6. De ne B =ff11;5;0g;f11;5;1g;f11;0;2g;f11;1;3g; f11;2;3g;f5;0;3g;f5;1;2g;f5;2;3g;f0;1;2g;f0;1;3gg. Then (Z5[f11g;B) is a maximum packing of 2K6 such that the neighborhood of 11 is C5. Otherwise for n 12, a maximum packing is constructed on the vertex set Zn 2 [ ff1jgj1 j 2g where the neighborhood of 11 is Q =fc0;:::;cq 1g. For each i2Zq, let ci = (ci;1;:::;ci;li) where li is the length of ci, cj;k 2Zn 2 for all (j;k)6= (0;2), andc0;2 =12. In this case, n 2 4 (mod 6) and thus (n 2)2 n 22 (n 2 3) and (n 2)2 n 22 1 are both divisible by 3, and since n 2 10, both quantities are nonneg- ative. So by Theorem 4.3, let (Zn 2;B1) be a K3-decomposition of Kn 2 (E(H1)[E(F1)) and by Lemma 4.2, let (Zn 2;B2) be a K3-decomposition of Kn 2 E(H2) where H1 is a n 5 cycle, H2 consists of a K1;3 and (n 2) 42 independent edges, F1 is a 1-factor, and H1 and H2 are named as follows: If l0 = 4, let H1 = (c1;1;:::;c1;l1;c2;1;:::;c2;l2;:::;cq 1;1;:::;cq 1;lq 1) (so that c0;1;c0;3; and c0;4 are omitted) and if l0 5, let H1 = (c0;4;c0;5;:::;c0;l0;c1;1;:::;c1;l1;c2;1; :::;c2;l2;:::;cq 1;1;:::;cq 1;lq 1 1) (so that c0;1;c0;3; and cq 1;lq 1 are omitted). If l0 = 4, let H2 be de ned to contain the edges fci;1;ci;lig for each i2Zq as well as the edges fc0;4;c0;3g andfc0;4;c1;2g(note that c1;2 6= c1;l1 since all cycles have length greater than 2 and note that c0;4 is the vertex of degree 3 in H2) and nally (n 2) 4 2(q 1)2 arbitrarily named edges. If l0 5, let H2 be de ned to contain the edges fci;1;ci;lig for each i2Zq as well as the edges fc0;3;c0;4g;fcq 1;lq 1;cq 1;lq 1 1g; and fcq 1;lq 1;c1;2g (note that c1;2 6= c1;l1 since all cycles have length greater than 2, c0;4 6= c0;l0 since l0 5, and cq 1;lq 1 is the vertex of degree 3 in H2) and nally (n 2) 4 2q2 arbitrarily named edges. 56 Note that in each case[q 1i=1E(ci)[E(c00) E(H1)[E(H2) where c00 is formed from c0 by removing the edges fc0;1;c0;2g and fc0;2;c0;3g. Let H01 be the graph induced by [q 1i=1E(ci)[ E(c00) and let H02 be the graph induced by (E(H1)[E(H2))nE(H01). Then every vertex has degree 2 in H01 and H02 except c0;1 and c0;3 both of which have degree 1 in both H01 and H02. Then (Zn 2 [ff1jg j 1 j 2g;B1 [B2 [ff1i;ai;big j fai;big 2 E(H0i)g[ ff11;12;c0;lgjl2f1;3gg) is the required decomposition. Case 8: Suppose n 1 or 3 (mod 6), = 0, and that Q has a cycle of length at least 4. A K3-decomposition of 2Kn will be constructed on the vertex set Zn 2[f11;12gsuch that the neighborhood of the vertex 11 is Q. Let Q =fc0;:::;cq 1g where for each i2Zq, the cycle ci = (ci;1;:::;ci;li) has length li, cj;k 2Zn 2 unless (j;k) = (0;2), c0;2 = 12, and l0 4. Since n 2 1 or 5 (mod 6), by Theorem 4.3, there exists a decomposition of Kn 2 into triples and a near-Hamilton cycle. So let (Zn 2;B1) be a K3-decomposition of Kn 2 E(H1), where H1 is a near-Hamilton cycle named so that H1 = (c0;3;c0;4;c0;5;:::;c0;l0;c1;1;:::;c1;l1;:::;cq 1;1;:::;cq 1;lq 1) (so c0;1 is omitted). Let (Zn 2;B2) be a K3-decomposition of Kn 2 E(H2), where H2 is the near-Hamilton cycle H2 = (c0;1;c0;l0;c1;1;c1;l1;:::;cq 1;1;cq 1;lq 1;v1;:::;v(n 2) 1 2q) where v1;:::;v(n 2) 1 2q omit c0;3 and are otherwise arbitrarily named. (Note that c0;3 6= c0;l0 since l0 4.) Then c0;1 has degree 2 in H2 and degree 0 in H1, c0;3 has degree 2 in H1 and degree 0 in H1, and every other vertex in Zn 2 has degree 2 in both H1 and H2. Let H01 be the graph induced by (E(H1)[ffci;1;ci;ligji2Zqg)n(ffci;li;ci+1;1gji2Zqg[ ffc0;3;cq 1;lq 1gg) reducing the sum in the subscript modulo q. (Note that fc0;1;cq 1;lq 1g=2 E(H1) so this edge is not removed). Note that in H01 every vertex in Zn 2 has degree 2 except c0;1 and c0;3, both of which have degree 1. Let H02 be the graph induced by (E(H1)[ E(H2))nE(H01). Note that in H02, every vertex in Zn 2 has degree 2 except c0;1 and c0;3, both of which have degree 1. The set of cycles formed by the components in H01 contains the cycles c1;:::;cq 1 and c00 where c00 is formed from c0 by deleting the edges fc0;1;c0;2g and fc0;2;c0;3g. 57 Then (Zn[f11;12g;B1[B2[ff1i;ai;bigjfai;big2E(H0i);1 i 2g[ff11;12;c0;lgj l2f1;3gg) is the required K3-decomposition. Case 9: Suppose n 1 (mod 3), = 0, and that Q has a 3-cycle. A maximum packing is constructed on the vertex set Zn 4[ff1jgj1 j 4gwhere the neighborhood of 11 is Q = fc0;:::;cq 1g, where c0 = (12;13;14), and the q 1 other-cycles are de ned on the vertex set Zn 4. When n = 4, the result is trivial, and Q cannot have a 3-cycle when n = 1 (obviously) or when n = 7 (since then Q = C3[C3, and (n;Q)6= (7;C3[C3) by assumption). So it can be assumed that n 10. Then w = n 4 0 (mod 3) and 4 w 1. So by Lemma 4.4, there exists a K3-decomposition (Zn 4;B) of 2Kn 4 (E(H1)[E(H2)[E(H3)[E(H4)) where H1; H2;H3, and H4 are 2-regular graphs and H1 Qnc0. Let (ff1jgj1 j 4g;B3) be a K3-decomposition of 2K4 (where the neighborhood of 11 is the 3-cycle (12;13;14)). Then (Zn 4[ff1jgj1 j 4g;B[B3[ff1i;ai;bigjfai;big2E(Hi);1 j 4g is the required decomposition. Case 10: Suppose n 4 (mod 6), = 0, and that Q has a cycle of length at least 5. A maximum packing is constructed on the vertex set Zn 2[ff1jgj1 j 2gwhere the neighborhood of 11 is Q =fc0;:::;cq 1g. For each i 2 Zq, let ci = (ci;1;:::;ci;li) where li is the length of ci, l0 5, cj;k 2 Zn 2 for all (j;k) 6= (0;2), and c0;2 = 12. In this case, n 2 2 (mod 6) and thus (n 2) 2 n 2 2 (n 2 2) and (n 2) 2 n 2 2 are both divisible by 3, and since n 2 8, both quantities are nonnegative. So by Theorem 4.3, let (Zn 2;B1) be a K3-decomposition of Kn 2 (E(H1)[E(F1)) and let (Zn 2;B2) be a K3-decomposition of Kn 2 (E(F2)) where H1 is a n 4 cycle, F1 and F2 are 1-factors, and H1 and F2 are named as follows: Let H1 = (c0;4;c0;5;:::;c0;l0;c1;1;:::;c1;l1;c2;1;:::;c2;l2;:::;cq 1;1;:::;cq 1;lq 1) (so that c0;1 and c0;3 are omitted). Let F2 be de ned to contain the edges fci;1;ci;lig for each i2Zq as well 58 as the edge fc0;3;c0;4g and nally n 2 2q 22 arbitrarily named edges. (Note that c0;4 6= c0;l0 since l0 5.) Note that[q 1i=1E(ci)[E(c00) E(H1)[E(H2) where c00 is formed from c0 by removing the edges fc0;1;c0;2g and fc0;2;c0;3g. Let H01 be the graph induced by [q 1i=1E(ci)[E(c00) and let H02 be the graph induced by (E(H1)[E(H2))nE(H01). Then every vertex has degree 2 in H01 and H02 except c0;1 and c0;3 both of which have degree 1 in both H01 and H02. Then (Zn 2 [ff1jg j 1 j 2g;B1 [B2 [ff1i;ai;big j fai;big 2 E(H0i)g[ ff11;12;c0;lgjl2f1;3gg) is the required decomposition. Note that this covers all the cases since Q must contain an odd cycle when n 2 (mod 6) and = 0, Q cannot contain all 3-cycles when n 0 (mod 3) (jQj= 2 (mod 3)), and Q cannot consist entirely of even cycles when n 4 (mod 6). 59 Chapter 5 Quadratic Excesses or Paddings of Covers with Triples of Kn 5.1 Introduction Having found a solution to the quadratic leave problem (completed in Chapter 3), this chapter will focus on the quadratic excess problem. As mentioned in the introduction, Colbourn and Rosa found necessary and su cient conditions for a quadratic graph to be the excess of a cover of Kn when = 1 (see [10]). In this chapter, their results are extended to all (see Theorem 5.2). 5.2 Results In this section, the main result of the chapter is given, namely necessary and su cient conditions for a quadratic graph to be the excess of a cover of Kn (naturally it is assumed that 1 in this chapter). However, to begin a very well known theorem on maximum packings and minimum covers of Kn (packings and covers for which the leave and excess have as few edges as possible) is given. Theorem 5.1. [14, 23] Let 1 and n6= 2. Let P (or L) be any multigraph with the least number of edges in which all vertices have degree congruent to (n 1) (mod 2) and with jE(P)j+ n(n 1)2 0 (mod 3) (or n(n 1)2 jE(L)j 0 (mod 3) respectively). Then there exists a K3-decomposition of Kn[E(P) (or Kn E(L) respectively). The statement and proof of the main theorem are now given. Theorem 5.2. Let Q be a quadratic graph on n vertices. Then Q is the excess of a cover of Kn if and only if 60 1. (n 1) is even, 2. jE(Q)j+jE( Kn)j 0 (mod 3), and 3. n6= 2. Proof. The necessity of Conditions (1) and (2) follows since each vertex in each triple has even degree and each triple contains 3 edges respectively. The necessity of Condition (3) is clear since K2 +E(Q) contains no copies of K3. To prove the su ciency, suppose that (1 3) hold. Several cases are considered in turn. Case 1: n 1;3 (mod 6) By Theorem 5.1, let (V;B1) be a K3-decomposition of ( 1)Kn (with L = ;). By Condition (2) and Theorem 1.3, let (V;B2) be a cover of Kn with excess Q. Then (V;B1[B2) is the required cover. Case 2: n 5 (mod 6) Let 2f1;2;3g with (mod 3). Note that jE( Kn)j jE( Kn)j (mod 3). Since n 5 (mod 6), by Theorem 5.1, there exists a K3-decomposition (V;B1) of ( )Kn. If = 1 then by Condition (2) and Theorem 1.3, let (V;B2) be a cover of Kn with excess Q. Suppose = 2. By Condition (2),jE(Q)j 1 (mod 3). Sincen 2 (mod 3), some vertex inV has degree 0 inQ, sayx. Letc = (c0;c1;:::;ci) be a cycle inQand letc0 = (c0;x;c1;:::;ci). Form Q0 from Q by replacing c with c0. Q0 is quadratic on the vertex set V andjE(Q0)j 2 (mod 3), so by Theorem 1.3, let (V;B02) be a cover of Kn with excess Q0. By Theorem 5.1, let (V;B002) be a maximum packing of Kn with leave the 4-cycle (c0;x;c1;d) where d is any vertex in V other than c;x0; and x1 (this exists since in this case n 5 (mod 6) so n 5). Let B2 = B02[B002 [ffc0;c1;dgg. If = 3 then by Condition 2 jE(Q)j 0 (mod 3). Since n 2 (mod 3), some vertex in V has degree 0 in Q, say x. Let c = (c0;c1;:::;ci)2Q and let c0 = (c0;x;c1;:::;ci). Form Q0 from Q by replacing c with c0. Q0 is quadratic on the vertex set V andjE(Q0)j 1 (mod 3), 61 so by the previous case in this proof when = 2, let (V;B02) be a cover of 2Kn with excess Q0. By Theorem 5.1, let (V;B002) be a maximum packing of Kn with leave the 4-cycle (c0;x;c1;d) where d is any vertex in V other than x;c0; and c1. Let B2 = B02[B002 [ffc0;c1;dgg. Then in each subcase ( = 1;2; and 3), (V;B1[B2) is the required cover. Case 3: n 4 (mod 6) Since n 4 (mod 6), by Condition (1), is even. By Theorem 5.1, let (V;B1) be a K3-decomposition of ( 2)Kn. By Condition (2), jE(Q)j 0 (mod 3). Hence, Q also satis es the conditions for an excess for v = n 1 and = 1. So let x 2 V be an isolated vertex in Q (in this case jV(Q)j 1 (mod 3) andjE(Q)j 0 (mod 3) so such an x exists) and let (V nfxg;B2) be a cover of Kn 1 with excess Q. By Theorem 5.1, let (V;B3) be a maximum packing of Kn with leave Q0 consisting of a K1;3 and n 42 independent edges, where the vertex set of the K1;3 is fw;x;y;zg V with y being the vertex of degree 3. Then (V;B1[B2[B3[ffx;ai;bigj fai;bigis an independent edge in Q0g[ffx;y;zg;fx;y;wgg) is the required decomposition. Case 4: = 2 and n 0;2 (mod 6) First suppose Q consists entirely of 2-cycles and isolated vertices. HencejE(Q)jis even, and by Condition (2),jE(Q)j 0 or 1 (mod 3) when n 0 or 2 (mod 6) respectively (recall = 2 in this case). Hence jE(Q)j 0 or 4 (mod 6) when n 0 or 2 (mod 6) respectively and thus the number of isolated vertices in Q is equivalent to 0 or 4 (mod 6) when n 0 or 2 (mod 6) respectively. If Q contains no isolated vertices (so n 0 (mod 6)), then by Theorem 5.1, for each k2f1;2glet (V;Bk) be a minimum cover of Kn with the same 1-factor excess. Then (V;B1[B2) is the required cover. Otherwise Q contains at least 4 isolated vertices, and this case is handled below by using the observation in the next paragraph. Note that if Q is a quadratic graph in which there are three isolated vertices, say a;b; and c, in Q, then Q is a quadratic excess if and only if Q[ffa;bg;fa;cg;fb;cggis a quadratic excess. If Q contains at least 3 isolated vertices, then add a cycle of length 3 on three of the isolated vertices to Q. 62 In light of the last two paragraphs, to complete the proof of Case 4 it now su ces to consider the situation where Q has a cycle c = (v0;v1;:::;vx) of length x + 1 3. Form Q0 from Q by replacing c with c0 = (v1;v2;:::;vx). Note thatjE(Q0)j 2 (mod 3) and 0 (mod 3) when n 0 and 2 (mod 6) respectively. Further note that v0 =2V(Q0) and that Q0 satis es the conditions for an excess when = 1 and n0 = n 1 5 (mod 6) and for an excess when = 1 and n0 = n 1 1 (mod 6). So by Theorem 1.3, let (Vnfv0g;B1) be a cover of Kn 1 with excess Q0. By Theorem 5.1, let (V;B2) be a maximum packing of Kn with leave a 1-factor F named to contain the edges fv1;vxg and fv0;dg where d is a vertex for which fv1;vx;dg2 B1. Then (V;(B1 [B2 nffv1;vx;dgg)[ffv0;ai;bigjfai;big2 F nffv1;vxg;fv0;dggg[ ffv0;v1;dg;fv0;v1;vxg;fv0;vx;dgg) is the required cover. Case 5: > 2 and n 0 (mod 6) By Condition (1), is even. Hence, by Theorem 5.1, let (V;B1) be a K3-decomposition of ( 2)Kn. By Condition (2), jE(Q)j 0 (mod 3). Hence, by Case 4, let (V;B2) be a cover of 2Kn with excess Q. Then (V;B1[B2) is the required cover. Case 6: > 2 and n 2 (mod 6) By Condition 1, is even. Let 2f2;4;6g with (mod 6). Note that jE( Kn)j jE( Kn)j(mod 3) and (mod 2) so Q satis es the necessary conditions for an excess of Kn precisely when it satis es the necessary conditions for an excess of Kn. By Condition (3), n 8, so by Theorem 5.1, let (V;B1) be a K3-decomposition of ( )Kn. If = 2, by Case 4, let (V;B2) be a cover of 2Kn with excess Q. If = 4 then by Condition 2 jE(Q)j 2 (mod 3). First suppose Q consists only of 2-cycles and isolated vertices. SincejE(Q)j 4 n (mod 6), the number of isolated vertices in Q must be a multiple of 6. If Q has no isolated vertices, then let Q0 consist of two of the 2-cycles and Q00 consist of the remaining n2 2 2 2-cycles (n 8 in this case). Note that jE(Q0)j jE(Q00)j 1 (mod 3) so by Case 4, let (V;B02) be a cover of 2Kn with excess Q0 63 and (V;B002) be a cover of 2Kn with excess Q00. Let B2 = B02[B002. Otherwise Q has at least 6 isolated vertices; add a 3-cycle on three of the isolated vertices to Q. It remains to consider the case where Q has a cycle c = (v0;v1;:::;vx) of length x+1 3. Form Q0 from Q by replacing c with c0 = (v1;v2;:::;vx). NotejE(Q0)j 1 (mod 3) so by Case 4, let (V;B02) be a cover of 2Kn with excess Q0. By Theorem 5.1, let (V;B002) be a packing of 2Kn with leave ffc1;cxg;fc1;cxgg. Let B2 = B02[B002 [ffc0;c1;cxgg. If = 6 then jE(Q)j 0 (mod 3). Since n 2 (mod 6), there are at least two vertices, say v0 and v1 such that v0;v1 =2V(Q). Form Q0 from Q by adding the 2-cycle (v0;v1). Note jE(Q0)j 2 (mod 3), so by the previous case where = 4, let (V;B02) be a cover of 4Kn with excess Q0. By Theorem 5.1, let (V;B002) be a packing of 2Kn with leave ffv0;v1g;fv0;v1gg. Let B2 = B02[B002. In each case, (V;B1[B2) is the required cover, so the result is proved. 64 Chapter 6 Conclusion To conclude this dissertation, it seems appropriate to mention some applications of the work done as well as some future directions of research. Some of the mathematical applications of the results in this dissertation (such as telling when two 2-fold triple systems are isomorphic) were already discussed, so at this point, a couple of applications of the general topic of graph decompositions and structure within them are mentioned in relation to other topics. One useful application of graph decompositions involves scheduling problems. For instance, a 1-factorization of K12 would correspond to an 11 week football schedule in which each team plays each other team exactly once. A structure question related to this application is whether the schedule could be made so that six xed games, say rivalry games, appear on the last week of the season. (Incidentally, this can be done.) In terms of more scienti c applications, there is the following application. In research on viruses, a method known as the Ouchterlony method tests how antigens interact. Around the edge of a Petri dish, v ofnantigens are placed where they can di use, and then the interaction of neighboring antigens is observed. For research purposes, it may be bene cial to have each pair of antigens appear as neighbors on exactly Petri dishes. This can be modeled mathematically as a v- cycle-decomposition of Kn. In terms of the research in this dissertation, the topics covered in Chapter 2 directly correspond to a slight variant of the Ouchterlony method. Suppose now that there are n + m antigens which are to be placed into two groups, one of size m and one of size n (for instance one group may share a speci c trait while the other group may share a di erent trait). It may be desirable to see how two antigens in the same group interact 1 times while only seeing how antigens in di erent groups interact 2 times. This 65 corresponds to a decomposition of the graph 1Kn_ 2 1Km that was discussed in Chapter 2. In terms of future research, several problems seem interesting. An original topic for this dissertation involved nding necessary and su cient conditions for a gregarious K3- decomposition of 1Km_ 2 1Kn, where in this setting gregarious simply means that each triple contains two mixed edges and one pure edge. In [13], El-Zanati, Punnim, and Rodger solved this problem when 1 = 1 and 2 = 2. Little other work has been done on the subject, although some minor results have been obtained. This would be an interesting problem to consider, as would the problem of nding necessary and su cient conditions for a K3-decomposition (not necessarily gregarious) of 1Km_ 2 1Kn when 1 < 2; both problems seem di cult. 66 Bibliography [1] A. Bialostocki and J. Sch onheim, Packing and Covering of the Complete Graph with 4-cycles, Canadian Mathematical Bulletin 18 (5) (1975), 703-708. [2] R.C. Bose and T. Shimamoto, Classi cation and analysis of partially balanced incom- plete block designs with two associate classes, Journal of the American Statistical As- sociation 47 (1952) 151 184. [3] D. Bryant, Hamilton cycle rich two-factorizations of complete graphs, Journal of Com- binatorial Designs 12 (2) (2004), 147 155. [4] D. Bryant, D. Horsley and B. Maenhaut, Decompositions into 2-regular subgraphs and equitable partial cycle decompositions, Journal of Combinatorial Theory. Series B 93 (1) (2005), 67 72. [5] D. Bryant, D. Horsley, and W. Pettersson, Cycle decompositions V: Complete graphs into cycles of arbitrary lengths, submitted. [6] D. Bryant and D. Horsley, An asymptotic solution to the cycle decomposition problem for complete graphs, Journal of Combinatorial Theory. Series A 117 (8) (2010), 1258 1284. [7] J. Cha ee and C.A. Rodger, Neighborhoods in Maximum Packings of 2Kn and Quadratic Leaves of Triple Systems, Jounral of Combinatorial Designs, to appear. [8] C.J. Colbourn, D.G. Ho man and R. Rees, A new class of group divisible designs with block size three, Journal of Combinatorial Theory Series A 59 (1) (1992) 73 89. [9] C.J. Colbourn and A. Rosa, Element neighbourhoods in twofold triple systems, Journal of Geometry 30 (1) (1987), 36 41. [10] C.J. Colbourn and A. Rosa, Quadratic excesses of coverings by triples, Ars Combinatoria 24 (1987), 23-30. [11] C.J. Colbourn and A. Rosa, Quadratic leaves of maximal partial triple systems, Graphs and Combinatorics 2 (4) (1986), 317-337. [12] C.J. Colbourn, A. Rosa, and S. Zn am, The spectrum of maximal partial Steiner triple systems, Designs, Codes and Cryptography. An International Journal 3 (3), (1993), 209 219. 67 [13] S.I. El-Zanati, Narong Punnim, C.A. Rodger, Gregarious GDDs with two associate classes, Graphs and Combinatorics, 26 (6) (2010), 775-780. [14] M.K. Fort Jr. and G.A. Hedlund, Minimal coverings of pairs by triples, Paci c Journal of Mathematics 8 (1958), 709 719. [15] H.L. Fu and C.A. Rodger, Group divisible designs with two associate classes: n = 2 or m = 2, Journal of Combinatorial Theory A 83 (1) (1998) 94 117. [16] H.L. Fu, C.A. Rodger and D.G. Sarvate, The existence of group divisible designs with rst and second associates, having block size 3, Ars Combinatoria 54 (2000) 33 50. [17] Haim Hanani, The existence and construction of balanced incomplete block designs, Annals of Mathematical Statistics, 32 (1961), 361-386. [18] D.G. Ho man, C.A. Rodger, and A. Rosa, Maximal sets of 2-factors and Hamiltonian cycles, Journal of Combinatorial Theory. Series B 57 (1) (1993), 69 76. [19] Thomas P. Kirkman, On a problem in combinations, Cambridge and Dublin Math, J 2 (1847), 191-204. [20] H. Lenz and G. Stern, Steiner triple systems with given subspaces; another proof of the Doyen-Wilson-Theorem, Unione Matematica Italiana. Bollettino. A (5), 17 (1) (1980) 109 114. [21] C.C. Lindner and C.A. Rodger, Design theory, CRC Press, Boca Raton, FL, 2009. [22] L. McCauley and C.A. Rodger, Hamilton cycle rich 2-factorizations of complete multi- partite graphs, Graphs and Combinatorics 24 (1) (2008), 47 52. [23] E. Mendelsohn, N. Shalaby and H. Shen, Nuclear designs, Ars Combinatoria 32 (1991), 225-238. [24] S. Milici, Minimum coverings of the complete graph with 5-cycles, Journal of Combi- natorial Mathematics and Combinatorial Computing, 57 (2006), 33-46 [25] N. Pabhapote and N. Punnim, Group divisible designs with two associate classes and 2 = 1, International Journal of Mathematics and Mathematical Sciences (2011). [26] J. Petersen, Die Theorie der regul aren graphs, Acta Mathematica 15 (1) (1891), 193 220. [27] C.A. Rodger and S.J. Stubbs, Embedding partial triple systems, Journal of Combina- torial Theory Series A 44 (2), (1987) 241 252. [28] E.A. Severn, Maximal Partial Triple Systems, Computer Science Technical Report 172=84, University of Toronto (1984). [29] J.E. Simpson, Langford sequences: perfect and hooked,Discrete Math 44 (1) (1983) 97 104. 68