K4 ? e Designs with a Hole by Roxanne Isabell Back A dissertation submitted to the Graduate Faculty of Auburn University in partial fulfillment of the requirements for the Degree of Doctor of Philosophy Auburn, Alabama December 13, 2010 Approved by: Dean Hoffman, Chair, Professor of Mathematics Chris Rodger, Professor of Mathematics Curt Lindner, Professor of Mathematics Abstract In this paper we look at K4 ?e designs on Kw?v +v. We settle the case when w and v are of the same parity. ii Acknowledgments Dr. Hoffman, thank you for your patience, guidance, optimism and support. Thank you for your willingness to share your knowledge and ideas. I have thoroughly enjoyed working with you and taking your classes. You are a model teacher; one in which I aspire to be like. Although this dissertation would have been impossible for me without the help and influence of Dr. Hoffman, there are a series of people and events that clearly led me to the math program at Auburn University, beginning of course, with my parents. Thank you for setting me on the path to college and for your love and support during all my years in school. I thank my father for teaching me about algebra in elementary school and my aunt Heather for the many Mensa books she gave me as birthday and Christmas gifts. I would like to thank my 8th grade math teacher who moved me into the advanced math class which eventually allowed me to take AP Calculus in high school. I thank my college math professor, Susan Serrano, who on the day I needed to declare a major convinced me to major in math. Dr. Serrano encouraged me to attend graduate school at Auburn University as she herself had received her Ph.D. there under Dr. Hoffman. I would like to thank my son for being a source of joy and inspiration. I thank my colleagues at Mount Mary College who have been patient and supportive of the completion of my dissertation. In fact, I need to thank every family member and friend, past and present, for making me who I am and helping me to get to this place in my life. iii Table of Contents Abstract . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ii Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iii List of Figures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . v 1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 2 Recursion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 3 a is even . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 4 a is odd . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 5 5|d . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 6 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32 iv List of Figures 1.1 Kd +v . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.2 K4 ?e . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 1.3 Kn?1 + 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.4 Kn?2 + 2 and Kn?3 + 3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.5 Zt ?{1,2}+v . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 1.6 Graph H . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 1.7 Block types . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 2.1 Recursion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 3.1 Bridge . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 3.2 Bridges for (34,16) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 3.3 2,3,8 bridge . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 4.1 One class of ? blocks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 4.2 Dead Zone for Lemma 4.1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 4.3 Extra ? block needed in Lemma 4.2 . . . . . . . . . . . . . . . . . . . . . . . 17 5.1 Number of edge colors . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 5.2 Another construction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 5.3 K10t +h . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 5.4 Bridges for Case 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28 v Chapter 1 Introduction A G-design of H is an edge-disjoint decomposition of H into isomorphic copies of the graph G. When H is the complete graph on n vertices, H = Kn, it is called a G-design of order n. The spectrum problem for G, i.e. solving for which values of n there exists a G-design of order n, has been solved for many graphs G, including all graphs G on less than 6 vertices. [1, 2] A complete graph with a hole of size v, Kn\Kv, is a complete graph on n vertices where the edges of a complete subgraph of size v have been removed. Let V be an independent set of vertices of size v. The graph G+v is a graph G where every vertex in V is adjacent to every vertex in G. So, Kd +v = Kn\Kv where d = n?v. Kd ... V Figure 1.1: Kd +v G-designs with holes of size v partition the edges of Kd + v into edge disjoint copies of G. These designs were first studied by Doyen and Wilson in 1973 where G = K3. [3] 1 A Steiner Triple System of order v, STS(v), is an ordered pair (S,T), where S is a finite set of points of size v, and T is a set of 3-element subsets of S called triples, where any two distinct points lie in exactly one triple. (S1,T1) is a subsystem of (S,T) if, S1 ? S, T1 ? T, and (S1,T1) is a STS. Doyen and Wilson?s theorem give the necessary and sufficient conditions of a STS(w) which contains a STS(v) as a subsystem to be w ? 1 or 3 (mod 6) and v ? 1 or 3 (mod 6) and w ? 2v + 1. Since the structure of the subsystem plays no role in the design on w, the subsystem could just be a hole. Thus we have a K3 design on Kw?v + v. These also exist when w ? v ? 5 (mod 6). This result has been extended to find G-designs on graphs with holes where G is a cycle of length at most 14 and a triangle with a pendent edge. [4, 5] A packing of Kn with a graph G is a triple, (S,T,L), where S is the vertex set of Kn, T is a collection of edge disjoint copies of G from the edge set of Kn, and L is the collection of edges in Kn not belonging to one of the copies of G in T. The collection of edges in L is called the leave. When |L| is as small as possible, (S,T,L) is called a maximum packing of order n. We look at the case when G = K4 ? e, the complete graph on four vertices minus one edge. We will denote a K4 ? e, as shown in Figure 1.2, by any of the quadruples (a,b,c,d),(a,b,d,c),(b,a,c,d) or (b,a,d,c). = K4 ? e a b c d Figure 1.2: K4 ?e In 1977, Bermond and Schonheim showed a K4 ?e design of order n exists if and only if n ? 0 or 1 (mod 5) and n ? 6. Hoffman, Lindner, Sharry, and Street, in 1993, solved 2 maximum packings of Kn, with K4 ? e. [6] These two results solve the K4 ? e design on Kd + v when v = 0,1,2,3. (A K4 ? e design of order n can be considered a Kn + 0 or a Kn?1 + 1.) Figure 1.3: Kn?1 + 1 The maximum packing paper tells us precisely when Kn has a leave of a single edge or a triangle. These graphs may be considered a Kn?2 + 2 and Kn?3 + 3 respectively. Figure 1.4: Kn?2 + 2 and Kn?3 + 3 3 The two main tools we use are difference methods and 1-factors. When d is even let d = 2t. We will depict Kd as Zt ?{1,2} with all possible edges between the sets (see Figure 1.5). We refer to the edges and vertices in Kd as being upstairs and the vertices in V as downstairs. 0 1 2 t ? 1 Zt .. . ... 210 v ? 1 0 1 2 t ? 1 Zt .. . V Figure 1.5: Zt ?{1,2}+v If a and b are integers, define |b?a|t, the difference of a and b (mod t), to be the smallest non-negative integer congruent to b?a or a?b (mod t). So, 0 ? |b?a|t ? t/2. The edges of the complete graph on vertex set Zt are partitioned into differences 1,2,...,?t/2? and the edge ab is defined to be of pure difference |b?a|t. When t/2 is an integer this is called the half difference and will generate t/2 edges in each Zt. All other pure differences will generate t edges in each Zt. Mixed differences describe the distance between vertices in different sets. Let (x,1) be a vertex in Zt?{1} and let (y,2) be a vertex in Zt?{2}. The mixed difference between them is y ?x (mod t). There are t mixed differences each consisting of t edges. Let Dt = {1,2,...,?t/2?}, the set of differences in Zt. If S is a subset of Dt, we define G[S] to be the graph on t vertices induced by the differences in S. We call x ? Dt a good difference if t/gcd(x,t) is even. 4 A 1-factor is a perfect matching, i.e. a set of a single edges that contain each vertex exactly once. When the edges of a graph can be partitioned into a set of 1-factors, this is called a 1-factorization. Lemma 1.1 (Stern and Lenz) Let ? negationslash= S ? Dt. G[S] has a 1-factorization if and only if S contains at least one good difference. In the proof they use: Lemma 1.2 Let G be a simple regular graph and G? an isomorphic copy of G. Form the graph H by adding an edge between each vertex in G and its isomorphic mate in G?. Then H, the graph shown below, has a 1-factorization. .. . .. . G? Graph H .. . .. . G x x? Figure 1.6: Graph H To ensure the use of these lemmas is possible while constructing blocks, we will use the same pure differences in each Zt ? {1} and Zt ? {2} and make sure we have at least one mixed difference remaining. Let S,U ? Dt, let T ? Zd. Define the graph G[S,T,U] on vertex set Zt ? {1,2} as follows: It?s edges are those edges on Zt ? {1} induced by the pure diferences in S, edges 5 on Zt ? {2} are induced by the pure differences in U, and those edges between Zt ? {1} and Zt ? {2} induced by the mixed differences in T. Since the edges of any single mixed difference are a 1-factor, Lemma 1.2 implies that G[S,T,S] has a 1-factorization whenever T negationslash= {?}. In a K4 ?e design on Kd +v, there are four possible types of blocks, ?,?,?, and ?. ? ? ? ? Kd V Figure 1.7: Block types Counting the edges of each block type gives us two helpful equations. In Kd, each ? block contributes one edge, ? blocks 2 edges, ? blocks 3 edges, and ? blocks 5 edges. Let A,B, ?, and ? represent the number of blocks of each respective type. Thus A+2B+3?+5? = (1/2)d(d?1). Counting the edges contributed by each block type between sets v and d yields 4A+ 3B + 2? = vd. We also know that A,B,?,? ? 0. In every construction we use Lemma 1.2 to find 1-factors and create ? blocks. Each 1-factor of Kd can be used to create t ??s that will contain all the edges between Kd and two vertices in V. Suppose a and b are vertices in V. For each xy in a particular 1-factor, we create the ? block (x,y,a,b). We will construct many blocks using difference methods (mod t). In the constructions, all ? and ? blocks will be defined explicitly. Blocks of type ? and ? will most often be described as base blocks. Base blocks are K4 ? e quadruples, where initial values for the vertices in Zt will be given. Base blocks represent a set of t total blocks. They are developed 6 (mod t) by taking each vertex that is an element of Zt and adding the integers (mod t). Let (a,b,c,d) be an ? base block where, a,b ? Zt and c and d are vertices in v. The ? base block is developed (mod t) by taking all blocks (a + i,b + i,c,d) where 0 ? i ? t ? 1. Let (x,y,w,z) be a ? base block where x,y,w,z ? Zt. The ? base block is developed (mod t) by taking all blocks (x+i,y +i,w +i,z +i) where 0 ? i ? t?1. Let?s consider some necessary conditions for a K4 ? e design on Kd + v. First, the number of edges K4 ?e must divide the number of edges of Kd +v. 5|d(d+ 2v ?1). (1.1) Second, v cannot be too large. Each block must use at least one edge upstairs. The number of blocks must be less than or equal to the number of edges in Kd. This simplifies to v ? 2(d?1). (1.2) When d is odd, each vertex in V will be of odd degree. The only block type that uses an odd number of edges incident to a vertex in V is ?. Each ? block uses 2 edges upstairs and each vertex in V must be contained in at least one ? block. This gives us another necessary condition when d is odd: v ? 2d(d?1)d+ 5 . (1.3) Although K5+2 satisfies the above three necessary conditions, it was proved in the maximum packing paper that the design does not exist. Therefore, when d is odd, these conditions are not sufficient. When d is odd, 1-factors do not exist. Therefore, many of our constructions do not apply when d is odd. Thus, the main purpose (of this dissertation) is to settle the case when d is even, i.e. d = 2t. This is our main theorem: Theorem 1.1: There exists a K4 ?e design on Kd +v when d is even if and only if 1. 5|d(d+ 2v ?1) 2. v ? 2(d?1) and v negationslash= 2d?3, v negationslash= 2d?4 7 Chapter 2 Recursion Let W = {(d,v): there exists a K4 ?e design on Kd +v}. Recall we are now assuming d = 2t. Part of our proof of the Main Theorem will be by induction on d+v, using the following Lemma and Theorem: Lemma 2.1 If (d?x,v +x) and (x,v) ? W then (d,v) ? W. x Kd V Figure 2.1: Recursion Proof The union of the blocks from the designs on Kd?x + (v + x) and Kx + v form a design on Kd +v. square Let R = {(d,v) : 5|d(d+ 2v ?1), d is even, and v ? 2d?5}. Theorem 2.1 Let (d,v) ? R and v ? 4/5d ? 17. Then for some x, (d ? x,v + x) and (x,v) ? R. Proof The conditions on d,v,x for (d ? x,v + x) and (x,v) ? R simplify to x ? 0 or 3v + 1 (mod 5) and v/2 + 1 ? x ? 1/3(2(d ? 1) ? v)). Since x must also be even, we are 8 guaranteed to find a value of x ? 0 or 3v+1 (mod 5) in the interval if it is at least of length ten. This is the case when v ? 4/5d?17. square The alert reader may notice that v is restricted to be less than or equal to 2d?5 rather than the before mentioned 2(d?1). The reason for this will become apparent in Chapter 5. Although Theorem 2.1 guarantees an x value for which we may use the recursion to find a design on (d,v) there are many cases in which v notlessorslnteql 4/5d ? 17 and a viable x value still exists. In these cases the x value will be stated explicitly. 9 Chapter 3 a is even To satisfy necessary Condition 1.1, 5 must divide d or d+2v?1. We will first consider when the latter case is true. This condition is satisfied when v is the maximum value, 2(d?1). Let a = 1/5(2(d?1)?v) ? 0 and this condition will also be satisfied. Lemma 3.1 (d,v) ? W when d = 2t, v = 2(d?1)?5a, and a is even. Proof Let d = 2t. Let A = t(2t?1?5/2a), B = 0, ? = 0, and ? = ta/2. We require (a/2) ? base blocks. These will be constructed using bridges. Bridges are produced by listing the mixed differences and taking two connected arcs, the length of which are pure differences. The bridge a b c Figure 3.1: Bridge represents the ? base block ((0,1),(b,2),(c,2),(b?a,1)). Pure differences 1 through a/2 will be used exactly once in each Zt upstairs. For example: (34,16), a = 10 requires 5 ? base blocks. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 160 1 3 5 1 3 5 2 4 2 4 Figure 3.2: Bridges for (34,16) 10 The bridge 2 3 8 1 5 Figure 3.3: 2,3,8 bridge describes the base block ((0,1),(3,2),(8,2),(1,1)) and uses pure differences 1 from Zt ?{1}, 5 from Zt ?{2} and mixed differences 2,3, and 8. The odd pure differences between 1 and a/2 form the ? base blocks: ((0,1),(?a/4?+j,2),(2j + 1,1),(3?a/4??j ?1,2)) where 1 ? 2j + 1 ? a/2 The even pure differences between 1 and a/2 form ? base blocks: ((0,1),(3?a/4?+?a/4?+j,2),(2j,1),(3a/2?j + 2,2)) where 2 ? 2j ? a/2. The ? blocks have used 3a/2 mixed differences and a/2 pure differences. So, |T| = t? 3a/2 and |S| = ?t/2?? a/2. The graph G[S,{t},S] will form t?a 1-factors and leaves t?3a/2?1 mixed difference 1-factors. Therefore we have the required 2t?1?5/2a ? base blocks. A 1-factorization of the re- maining edges may be found using Lemma 1.2 to create ? blocks using the method described in Chapter 1. The half difference may not be used in the construction of ? blocks. We need a/2 < ?d/4?. However, the requirement on mixed differences is more restrictive. The ? block construction requires the number of mixed differences, when a ? 3, to be at least 3a/2 + 2. Therefore, d ? 3a+4. All pairs d and a are either covered by this construction, or a special case of the recursion with values listed below. 11 (38,14) x = 10, (30,8) x = 10, (32,12) x = 10, (26,10) x = 10, (24,6) x = 4, (20,8) x = 10, (18,4) x = 8, (14,6) x = 4, (12,2) x = 2 square 12 Chapter 4 a is odd Lemma 4.1 (d,v) ? W when t = 3s and v = 2(d?1)?5a. Proof The cases where v ? 3 have been previously solved. Lemma 3.1 solves the case when a is even. We now assume that v > 3 and a is odd. Let A = t(2t?1?4a+ 3(a?1)/2),B = 2t,? = 0,? = t(a?1)/2. The ? blocks are constructed using pure differences 1 and 2 and the first 3 vertices in V. Each ? connects a vertex in V with 3 vertices in Zt. The vertices in Zt can be partitioned into three parallel classes. Each class contains s disjoint sets of size 3. These sets of size 3, along with a single vertex in V, will create a ? block using an edge of pure difference 1 and 2. Each of the three classes uses s edges of each difference 1 and 2 therefore exhausting all 2t edges of these differences. 1 2 v 30 copy of Zt ?{1} Figure 4.1: One class of ? blocks 13 All ? blocks are defined by: ((i,3),(i+3j,1),(i+3j+2,1),(i+3j+1,1)) and ((i,3),(i+3j,2),(i+3j+2,2),(i+3j+1,2)) where 0 ? i ? 2 and 0 ? j ? s?1. The (a ? 1)/2 ? base blocks are constructed using a similar method as in Lemma 3.1. In this case however, since pure differences 1 and 2 have been used in the ? blocks, we use pure differences 3 through (a?1)/2 + 2. Let ?? = (a?1)/2. The following are ? base blocks and are developed (mod t): ((0,1),(???/2?+ 1 +j,2),(2j + 1,1),(3???/2?+ 4?j,2)) where 3 ? 2j + 1 ? ?? + 2 ((0,1),(3???/2?+???/2?+ 5 +j,2),(2j,1),(3?? + 11?j,2)) where 4 ? 2j ? ?? + 2 The half difference may not be used in the construction of ? blocks. So, we need (a ? 1)/2 + 2 < ?d/4?. However, the requirement on mixed differences is more restrictive. The ? block construction requires the number of mixed differences, when a ? 4, (?? ? 2), to be at least 3?? + 10. Therefore, d ? 3a+ 17. The shaded region in the following graph, referred to as the dead zone, indicates pairs (a,d) that are not covered by this construction and are not guaranteed to be covered by the recursion. 14 17 Dead Zone DNE (7.8,22.5) a construction applies d (23.1,86.4) Theorem 2.1 applies Figure 4.2: Dead Zone for Lemma 4.1 Several of these cases can be covered by modifying the above the construction to using only odd pure differences in the ? blocks by replacing the ? base blocks with: ((0,1),(?? + 1 +j,2),(2j + 1,1),(3?? + 4?j,2)) where 1 ? j ? ?? This modification is used for designs on: (54,41), (48,39), (42,37), (36,35), (30,33),(30,23) and (24,21). The remaining dead zone cases needed for this lemma are: (60,43): In the main construction above replace ? base blocks with: ((0,1),(8 +j,2),(2j + 1,1),(25?j,2)) where 1 ? j ? 6 and ((0,1),(14,2),(8,1),(22,2)) (42,27): In the main construction above replace the ? base blocks with: ((0,1),(5 +j,2),(2j + 1,1),(16?j,2)) where 3 ? 2j + 1 ? 9 ((0,1),(11,2),(6,1),(17,2)) (36,25): In the main construction above replace the ? base blocks with: ((0,1),(4 +j,2),(2j + 1,1),(13?j,2)) where 3 ? 2j + 1 ? 7 ((0,1),(9,2),(6,1),(15,2)) (12,7): ? blocks: ((0,3),(5,1),(2,1),(1,1)),((0,3),(3,2),(3,1),(1,2)), ((0,3),(0,1), 15 (4,1),(0,2)),((0,3),(2,2),(5,2),(4,2)),((1,3),(3,1),(0,1),(5,1)), ((1,3),(1,2),(1,1),(5,2)),((1,3),(4,1),(2,1),(4,2)),((1,3),(0,2),(3,2),(2,2)), ((2,3),(1,1),(4,1),(3,1)),((2,3),(2,1),(0,1),(2,2)),((2,3),(5,2),(5,1),(3,2)), ((2,3),(4,2),(0,2),(1,2)) ? base block: ((0,1),(2,2),(1,1),(3,2)) Create ? blocks with pure differences 4 and 5 and the remaining four vertices in V. (6,5): Let {0,1,2,3,4,5} be the vertices of K6. (1,(0,3),5,0),(4,(0,3),2,3),(2,(1,3),0,1),(5,(1,3),3,4),(3,(2,3),1,2), (0,(2,3),4,5),(0,3,(3,3),(4,3)),(1,4,(3,3),(4,3)),(2,5,(3,3),(4,3)). Special cases of the Recursion: (84,51) x = 30, (78,49) x = 28, (72,47) x = 30, (66,45) x = 26, (60,33) x = 20, (54,31) x = 20, (48,29) x = 18, (42,17) x = 20, (36,15) x = 10, (30,13) x = 10, (24,11) x = 10, (18,9), x = 8. square Lemma 4.2 (d,v) ? W when t = 3s+ 1 and v = 2(d?1)?5a. Proof The cases where v ? 3 have been previously solved. Lemma 3.1 solves the case when a is even. We now assume that v > 3 and a is odd. Let A = t(2t?1?4a + 3(a?1))/2, B = 2t,? = 0,? = t(a?1)/2. Similar to Lemma 4.1, s ? blocks are constructed using pure differences 1 and 2 with each of the first 3 vertices in V. We need one more ?, which will contain vertex (3,3), to exhaust the edges of pure differences 1 and 2. Mixed difference 0 will then be used to create ? blocks with the first five vertices in V. These ? blocks will use all remaining edges adjacent to those five vertices in V. Here are the details: 16 1 2 3 40 copy of Zt ?{1} V Figure 4.3: Extra ? block needed in Lemma 4.2 All ? blocks are defined by: ((i,3),(i+3j+2,1),(i+3j,1),(i+3j+1,1)),((i,3),(i+3j+2,2),(i+3j,2),(i+3j+1,2)) where 0 ? i ? 2 and 0 ? j ? s?1. ((3,3),(1,1),(0,1),(t?1,1)) and ((3,3),(1,2),(0,2),(t?1,2)). Since mixed difference 0 is used in the ? blocks, the ? bridges begin at mixed difference 1. Let ?? = (a?1)/2. The following are ? base blocks and are developed (mod t): ((0,1),(???/2?+ 2 +j,2),(2j + 1,1),(3???/2?+ 5?j,2)) where 3 ? 2j + 1 ? ?? + 2 ((0,1),(3???/2?+???/2?+ 6 +j,2),(2j,1),(3?? + 12?j,2)) where 4 ? 2j ? ?? + 2 The last blocks to be constructed are ? blocks. First, the remaining edges between the vertices upstairs and the first five vertices in V will be exhausted. Each vertex upstairs needs to be connected with two of the five vertices downstairs. These ? blocks are as follows: ((1,1),(1,2),(2,3),(4,3)),((0,1),(0,2),(1,3),(4,3)),((t ? 1,1),(t ? 1,2),(0,3),(4,3)),((t ? 2,1),(t?2,2),(3,3),(4,3)) and ((j,1),(j,2),(3,3),(4,3)) where 2 ? j ? t?3 All other ? blocks are constructed as described in Chapter one with all vertices v ? 5. 17 The dead zone indicates pairs (a,d) that are not covered by this construction and are not guaranteed by Theorem 2.1. We must also ensure that all cases when v ? 5 are covered. As in Lemma 4.1, many of these cases are covered by the following modification on ? blocks where only odd pure differences are used. Use the above construction replacing the ? base blocks with: ((0,1),(?? + 2 +j,2),(2j + 1,1),(3?? + 5?j,2)) where 1 ? j ? ?? This modification works for the following cases: (70,43),(64,41) (62,47), (56,45), (50,43), (44,31), (38,29), (38,39), (32,27), (32,37), and (26,25). (14,11): ? base block: ((0,1),(0,2),(3,1),(3,2)) ? blocks: ((0,1),(j,3),(5,1),(6,1)),((0,2),(j,3),(5,2),(6,2)) where 1 ? j ? 6 ? blocks: ((1,1),(2,2),(0,3),(5,3)),((2,1),(1,2),(0,3),(5,3)),((3,1),(4,2),(0,3),(2,3)), ((2,1),(3,2),(1,3),(6,3)),((3,1),(1,2),(1,3),(6,3)),((4,1),(5,2),(1,3),(3,3)), ((5,1),(4,2),(1,3),(3,3)),((5,1),(6,2),(4,3),(2,3)),((6,1),(5,2),(4,3),(2,3)), ((6,1),(0,2),(5,3),(3,3)),((0,1),(6,2),(5,3),(3,3)),((0,1),(1,2),(6,3),(4,3)), ((1,1),(0,2),(6,3),(4,3)). The two one factors from mixed differences 2 and 5 are then used to make ? blocks with vertices 7,8,9, and 10 in V. (20,13): Inthemain constructionabove replace? baseblocks with: ((0,1),(9,2),(4,1),(3,2)) and ((0,1),(4,2),(3,1),(7,2)). Special cases of the Recursion: (92,57) x = 40, (86,55) x = 30, (80,53) x = 30, (74,51) x = 30, (68,49) x = 28, (68,39) x = 30, (62,37) x = 22, (56,35) x = 20, (50,33) x = 20, (44,21) x = 20, (38,19) x = 18, (32,17) x = 12, (26,15) x = 10, (26,5) x = 10. square 18 Lemma 4.3 (d,v) ? W when t = 3s+ 2 and v = 2(d?1)?5a. Proof The cases where v ? 3 have been previously solved. Lemma 3.1 solves the case when a is even. We now assume that v > 3 and a is odd. Let A = t(2t?1?4a+ 3(a?1)/2), B = 2t, ? = 0, ? = t(a?1)/2 Similar to Lemma 4.1, in each Zt ?{1} and Zt ?{2}, s ? blocks are constructed using pure differences 1 and 2 with the first 3 vertices in v. We need two more ??s in each Zt?{1} and Zt ? {2} to exhaust the edges of pure differences 1 and 2. One of which will contain vertiex (3,3), and the other (4,3). Mixed difference 0 will then be used to create ? blocks with the first five vertices in V. These ? blocks will use all remaining edges adjacent to those first five vertices in V. Here are the details: All ? blocks are defined by: ((i,3),(i+3j+2,1),(i+3j,1),(i+3j+1,1)),((i,3),(i+3j+2,2),(i+3j,2),(i+3j+1,2)) where 0 ? i ? 2 and 0 ? j ? s ? 1. ((4,3),(1,1),(0,1),(t ? 1,1)),((4,3),(1,2),(0,2),(t ? 1,2)), ((3,3),(0,1),(t?1,1),(t?2,1)), and ((3,3),(0,2),(t?1,2),(t?2,2)) Since mixed difference 0 is used in the ? blocks, the ? bridges begin at mixed difference 1. Let ?? = (a?1)/2. The following are ? base blocks and are developed (mod t): ((0,1),(???/2?+ 2 +j,2),(2j + 1,1),(3???/2?+ 5?j,2)) where 3 ? 2j + 1 ? ?? + 2 ((0,1),(3???/2?+???/2?+ 6 +j,2),(2j,1),(3?? + 12?j,2)) where 4 ? 2j ? ?? + 2 Now the remaining edges between the vertices upstairs and the first five vertices in V will be exhausted. Each vertex upstairs will be connected with two of the first five vertices downstairs in ? blocks as follows: ((0,1),(0,2),(2,3),(1,3)),((1,1),(1,2),(2,3),(3,3)),((t?1,1),(t?1,2),(1,3), (0,3)),((t?2,1),(t?2,2),(3,3),(1,3)), ((t?3,1),(t?3,2),(3,3),(4,3)) and ((j,1),(j,2),(3,3),(4,3)) where 2 ? j ? t?4. All other ? blocks are constructed as described in Chapter one with the remaining vertices v ? 5. 19 This lemma has the same restrictions as Lemma 4.2 and thus has the same dead zone. The same modification on the ? blocks as in Lemmas 4.1 and 4.2 cover the following dead zone cases: (46,35), (34,31), (40,33), (62,47), (28,29), and (22,17). (52,37): Use the main construction for ? and ? blocks. Use the following ? base blocks: ((0,1),(7 +j,2),(2j + 1,1),(20?j,2)) where 1 ? j ? 5 and ((0,1),(14,2),(8,1),(22,2)). (58,39): Use the main construction of this lemma for ? and ? blocks. The ? base blocks are((0,1),(15?j,2),(15?2j,1),(16+j,2)) where3 ? 2j+1 ? 13and((0,1),(16,2),(8,1),(24,2)). (40,23): Usemainconstrcutionabove replacingthe? baseblocks with: ((0,1),(6,+j,2),(2j+ 1,1),(17?j,2)) where 1 ? j ? 4 and ((0,1),(12,2),(6,1),(18,2)). (28,19): Use the main construction of this lemma for ? and ? blocks. The ? base blocks are ((0,1),(5,2),(3,1),(10,2)),((0,1),(6,2),(5,1),(9,2)), and ((0,1),(4,2), (8,1),(12,2)). Special cases of the Recursion: (76,45) x = 30, (52,27) x = 20, (46,25) x = 16, (34,21) x = 14, (34,11) x = 10, (28,9) x = 8, (22,7) x = 10, (16,5) x = 6. square 20 Chapter 5 5|d Lemma 5.1 When d is even, 5|d, and v = 2d?3 or v = 2d?4 a K4 ?e design does not exist, on Kd +v. ? ? ? ? 2 1 1 1 0 0 0 0 0 0 0Kd V Figure 5.1: Number of edge colors Proof Assign each vertex in V a unique color. We then assign colors to the edges upstairs in accordance with the block type and vertices downstairs as follows: Each edge upstairs in an ? block will be assigned two colors. These are the colors of the two vertices in V that are contained in the ? block. Each edge upstairs in a ? block will be assigned the one color of the vertex v contained in the ? block. Let e be the edge in a ? block that is incident to both vertices upstairs that are adjacent to the vertex in v. Color e the same color as the vertex in V. The other two edges in a ? block and all edges in a ? block will not be assigned colors. Let p be the number of edges upstairs that are assigned two colors. Let q be the number of edges upstairs that are assigned one color in ? blocks. Let r be the number of pairs of one colored edges in ? blocks and s is the number of uncolored edges upstairs. 21 Counting edges upstairs at a particular vertex we get the equation d?1 = p+q+2r+s. Counting colors at each a vertex upstairs we get v = 2p + q + r. From necessary Condition 1.2 we know that 2(d?1)?v ? 0. Call this value the deficiency. The deficiency, 2(d?1)?v = q + 3r + 2s. Case 1: The deficiency = 1 = q + 3r + 2s. Thus, q = 1, r = s = 0. Since this is the only possible combination, all vertices upstairs must have this coloring. However, the single one colored edge (q = 1) cannot come from a ? block because there are no uncolored edges (s = 0). The single one colored edge cannot come from a ? block because there are no pairs of single colored edges (r = 0). The other block types do not contain single one colored edges. Therefore, the deficiency cannot equal one and there does not exist a K4 ?e design when v = 2d?3. Case 2: The deficiency = 2 = q + 3r + 2s. There are two possibilities, 2 = q and r = s = 0 or q = r = 0 and s = 1. In either case, since r = 0, there are no ? blocks. The two single one colored edges (q = 2) must come from ? blocks. However, a ? block cannot exist unless there is a vertex with 2 uncolored edges and s = 0 or 1. Therefore, the deficiency cannot equal two and there does not exist a K4 ?e design when v = 2d?4. square Lemma 5.2 If (d,v) ? W then (dk,v + 2d(k ?1)) ? W. Proof Create the graph Kdk + v by taking each vertex upstairs in Kd + v with a (d,v) design and blowing it up by k. Then k copies of the (d,v) design will exhaust all edges incident to vertices in V and (kd(d?1)2 ) edges upstairs. By Lemma 1.2 the remaining edges upstairs can be partitioned into d(k ? 1) one-factors. For each one-factor, add a pair of vertices downstairs and the appropriate edges to obtain Kdk + (v + 2d(k ? 1)). Now each one-factor and pair of vertices downstairs can be partitioned into ? blocks. square 22 Ka,b,c is a complete multipartite graph. Let S = {(a,b,c): there exits a K4 ? e design on Ka,b,c. Lemma 5.3 If (a,b,c) ? S, (b,v) and (c,v) ? W then (b+c,a+v) ? W. b a c b c v a Figure 5.2: Another construction Proof The union of the blocks from the designs (a,b,c), (b,v), and (c,v) create a (b + c,a+v) design. square Lemma 5.4 (10,10,10) ? S. Proof The following blocks form (10,10,10): ((0 +i,a),(0 +i,b),(2 +i,c),(3 +i,c)) ((0 +i,b),(0 +i,c),(2 +i,a),(3 +i,a)) ((0 +i,c),(0 +i,a),(2 +i,b),(3 +i,b)) ((5 +i,a),(0 +i,b),(1 +i,c),(6 +i,c)) ((5 +i,b),(0 +i,c),(1 +i,a),(6 +i,a)) ((5 +i,c),(0 +i,a)(1 +i,b),(6 +i,b)), for 0 ? i ? 9 square 23 Lemma 5.5 (d,v) ? W when 5|d, and v ? 2(d?1) and v negationslash= 2d?3, v negationslash= 2d?4. Proof Since 5|d and d is even, let d = 10t. Case 1: t = 1 Previously solved cases: v = 1,2,3 [6], v = 4 [6, example 4.2], v = 7 [6, example 4.5], and v = 9 [6, example 4.9] When v = 8,13 and 18, v = 2(d?1)?5a and are solved in Chapters 3 and 4. (10,4): Let {1,2,3,4,5,6,7,8,9,10} be the vertices upstairs (5,6,(2,3),(3,3)), (4,10,(2,3),(3,3)), (3,9,(2,3),(3,3)), (2,8,(2,3),(3,3)), (1,7,(2,3),(3,3)), ((1,3),3,1,7), (1,4,2,8),(2,5,3,9),(3,(0,3),4,10),(4,7,5,6),(5,8,(0,3),(1,3)), ((0,3),9,7,1),(7,10,8,2), (8,6,9,3), (9,(1,3),10,4),(10,1,6,5),(6,2,(1,3),(0,3)). (10,5): Let {0,1,2,3,4,5,6,7,8,9} be the set of vertices upstairs. ((1,3),1,0,2), (9,3,(1,3),1), ((1,3),6,5,7), (8,3,(1,3),6), (7,1,5,8), (7,2,3,4), (6,2,0,3), (3,4,5,0), (8,9,5,0), (1,4,(2,3),(3,3)), (6,9,(2,3),(3,3)), (6,1,(0,3),(4,3)), (0,4,(0,3),(4,3)), (5,2),(2,3),(3,3)), (8,3,(2,3),(3,3)), (7,0,(2,3),(3,3)), (5,0,(0,3),(4,3)), (7,3,(0,3),(4,3)), (8,2,(0,3),(4,3)). [7, page 12] (10,6): Z5 ? {1} ? (0,3) and Z5 ? {2} ? (0,3) each form a copy of K6 and can be de- composed in 6 blocks. The following blocks complete the design. ((1,3),(0,1),(0,2),(1,2)), ((2,3),(1,1),(1,2),(2,2)), ((3,3),(2,1),(2,2),(3,2)), ((4,3),(3,1),(3,2),(4,2)), ((5,3),(4,1),(4,2),(0,2)), ((1,3),(2,2),(4,1),(3,1)), ((2,3),(3,2),(0,1),(4,1)), ((3,3),(4,2),(1,1),(0,1)), ((4,3),(0,2),(2,1),(1,1)), ((5,3),(1,2),(3,1),(2,1)), ((0,1),(2,2),(4,3),(5,3)), ((1,1),(3,2),(1,3),(5,3)), ((2,1),(4,2),(1,3),(2,3)), ((3,1),(0,2),(2,3),(3,3)), ((4,1),(1,2),(3,3),(4,3)). (10,7): Let{1,2,3,4,5,6,7,8,9,10}betheverticesupstairs. ((0,3),7,5,8), ((0,3),10,6,9), (1,2,(0,3),(4,3)), (3,4,(0,3),(1,3)), ((1,3),1,7,9), ((1,3),2,10,8),(6,5,(1,3),(2,3)), ((2,3),8,1,3), ((2,3),9,2,4),(7,10,(2,3),(3,3)), ((3,3),4,1,5), ((3,3),3,2,6),(8,9,(3,3),(4,3)), ((4,3),5,3,10), ((4,3),6,4,7), ((5,3),5,1,8),(3,10,(5,3),1), ((5,3),6,2,9),(4,7,(5,3),2), ((6,3),5,2,9),(3,7,(6,3),9), ((6,3),6,1,8),(4,10,(6,3),8). 24 (10,9): Let {1,2,3,4,5,6,7,8,9,10} be the vertices upstairs. ((0,3),1,4,10), ((0,3),7,2,3), (5,8,(0,3),(2,3)), (6,9,(0,3),(1,3)), ((1,3),1,2,8), ((1,3),5,3,4), (7,10,(1,3),(2,3)), ((2,3),1,3,9), ((2,3),6,2,4),(1,5,(3,3),(4,3)), (2,8,(3,3),(4,3)), (3,4,(3,3),(4,3)), (6,7,(3,3),(4,3)), (9,10,(3,3),(4,3)), (1,6,(5,3),(6,3)), (2,4,(5,3),(6,3)), (3,9,(5,3),(6,3)), (5,7,(5,3),(6,3)), (8,10,(5,3),(6,3)), (1,7,(7,3),(8,3)), (2,3,(7,3),(8,3)), (4,10,(7,3),(8,3)), (8,9,(7,3),(8,3)), (2,5,9,10),(3,6,8,10),(4,7,8,9). (10,10): Let {0,1,2,3,4,5,6,7,8,9} be the set of vertices upstairs. ((i,3),i,8,9) for 0 ? i ? 7, ((0,3),7,2,1), ((6,3),5,0,7),((7,3),6,1,0),(0,1,(4,3)(6,3)), (1,2,(5,3),(7,3)),(2,2,(0,3),(6,3)),(3,4,(1,3),(7,3)),(4,5,(0,3),(2,3)), (5,6,(1,3),(3,3)),(6,7,(2,3),(4,3)),(7,0,(5,3)(3,3)), (8,9,(8,3),(9,3)),(0,4,(8,3),(9,3)),(1,5,(8,3),(9,3)), (2,6,(8,3),(9,3)),(3,7,(8,3),(9,3)). (10,11): Put a (5,1) deisgn on Z5 ?{1}?(0,3) and Z5 ?{2}?(0,3). Then use mixed differences 0 through 4 to create ? blocks with the last 10 vertices in V. (10,12): Let {1,2,3,4,5,6,7,8,9,10} be the vertices upstairs. ((i,3),i,7,8) for 1 ? i ? 6, ((j + 1,3),j,9,10) for 1 ? j ? 5, ((1,3),6,9,10), (1,6,(3,3),(4,3)),(1,2,(5,3),(6,3)),(3,6,(2,3),(3,3)),(3,4,(1,3),(6,3)), (1,5,(7,3),(8,3)),(4,6,(7,3),(8,3)),(2,3,(7,3),(8,3)),(7,8,(7,3),(8,3)), (9,10,(7,3),(8,3)),(1,3,(11,3),(12,3)),(2,4,(11,3),(12,3)),(5,6,(11,3),(12,3)), (7,9,(11,3),(12,3)),(8,10,(11,3),(12,3)),(1,4,(9,3),(10,3)),(2,6,(9,3),(10,3)), (3,5,(9,3),(10,3)),(8,9,(9,3),(10,3)),(7,10,(9,3),(10,3)). (10,14): ((1,3),(0,1),(4,1),(1,1)),((1,3),(0,2),(4,2),(1,2)), ((2,3),(1,1),(4,1),(2,1)),((2,3),(1,2),(4,2),(2,2)),((3,3),(2,1),(4,1),(3,1)), ((3,3),(2,2),(4,2),(3,2)),((4,3),(3,1),(4,1),(0,2)),((4,3),(3,3),(4,2),(0,1)), ((3,1),(3,2),(1,3),(2,3)),((2,1),(2,2),(1,3),(4,3)),((1,1),(1,2),(3,3),(4,3)), ((0,1),(0,2),(2,3),(3,3)),((3,1),(4,2),(5,3),(6,3)),((2,1),(0,1),(4,3),(6,3)), 25 ((0,1),(0,2),(5,3),(6,3)),((4,1),(2,2),(5,3),(6,3)),((3,2),(1,2),(5,3),(6,3)), ((3,1),(2,2),(7,3),(8,3)),((2,1),(0,2),(7,3),(8,3)),((1,1),(3,2),(7,3),(8,3)), ((0,1),(1,2),(7,3),(8,3)),((4,2),(4,1),(7,3),(8,3)),((3,1),(0,1),(9,3),(10,3)), ((2,1),(4,2),(9,3),(10,3)),((1,1),(2,2),(9,3),(10,3)),((4,1),(1,2),(9,3),(10,3)), ((3,2),(1,2),(0,3),(10,3)),((3,1),(1,2),(11,3),(12,3)),((2,1),(3,2),(11,3),(12,3)), ((1,4),(4,2),(11,3),(12,3)),((0,1),(2,2),(11,3),(12,3)),((4,1),(0,2),(11,3),(12,3)), ((3,1),(1,1),(13,3),(14,3)),((0,1),(4,2),(13,3),(14,3)),((4,1),(3,2),(13,3),(14,3)), ((0,1),(4,2),(13,3),(14,3)),((4,1),(3,2),(13,3),(14,3)),((2,2),(0,2),(13,3),(14,3)), ((2,1),(1,2),(13,3),(14,3)). (10,15): ((1,3),(4,1),(0,1),(1,1)),((1,3),(4,1),(0,2),(1,1)), ((2,3),(3,1),(0,1),(1,1)),((2,3),(3,2),(0,2),(1,2)),((3,3),(2,1),(0,1),(1,1)), ((3,3),(2,2),(0,2),(1,2)),((0,1),(0,2),(6,3),(7,3)),((1,1),(1,2),(6,3),(7,3)), ((2,1),(2,2),(4,3),(7,3)),((3,1),(3,2),(6,3),(7,3)),((4,1),(4,2),(5,3),(7,3)), ((3,1)(2,1),(1,3),(5,3)),((3,2),(2,2),(1,3),(5,3)),((4,1),(2,1),(2,3),(6,3)), ((4,2),(2,2),(2,3),(6,3)),((3,1),(4,1),(3,3),(4,3)),((3,2),(4,2),(3,3),(4,3)), ((0,1),(1,1),(4,3),(5,3)),((0,2),(1,2),(4,3),(5,3)). Use mixed differences 1,2,3, and 4 to make ? blocks with vertices 8 through 15 in V. We will now assume that t > 1. (The edges of pure difference t and 2t and mixed differences 0, t, 2t, 3t, and 4t produce t copies of K10 upstairs. This set of edges is replaced with K10 +h in Lemma 5.2). 26 0 t 2t3t 4t 0 t 2t3t 4t h Figure 5.3: K10t +h For 20t ? 20 ? v ? 20t ? 2, use (10,h), 0 ? h ? 18, in Lemma 5.2. In these designs, d(k ? 1) one-factors are used to make ? blocks with 2d(k ? 1) vertices downstairs. For every 5 sets of one-factors that we can turn into ? blocks, we reduce the number of vertices downstairs by 10. For each ? base block we can construct, we can cover the values of v where 20t?20?10? ? v ? 20t?2?10?. Here are the details: Case 2: t is odd ? base blocks: ((0,1),(2t?1?i,2),(2t?2?2i,1),(2t + 1 +i,2)) where 0 ? i ? t?2 ((0,1),(3t+ 2,2),(1,1),(3t + 3,2)), ((0,1),(4t+ 1 +j,2),(3 + 2j,1),(5t?1?j,2)) where 0 ? j ? t?32 ?1 27 4 2 2t ? 4 2t ? 2 2t 3tt0 3t 5 3 t ? 2 t ? 4 4t 5t ? 1 1 1 Figure 5.4: Bridges for Case 2 This produces (t + t?32 ) ? base blocks and v ? 5t?5, which is small enough to overlap with the recursion when t ? 3. As shown in figure 5.4 the construction of the odd ? blocks requires t ? 6. Modifications on this construction to cover t = 3 and 5 will be described following Case 3. Case 3: t is even The even pure difference construction of ? blocks as described in Case 2 produces (t?1) ? base blocks. When t is even, there are an odd number of ? base blocks produced and the bridge when i = t?22 will look like x x where x = t. Since the pure difference t has already been used, this ? block may not be constructed. ? base blocks: ((0,1),(2t?1?i,2),(2t?2?2i,1),(2t+1+i,2)) where 0 ? i < t?22 and t?22 < i ? t?2 ((0,1),(3t+ 2,2),(1,1),(3t + 3,2)), 28 ((0,1),(4t+ 2 +j,2),(3 + 2j,1),(5t?1?j,2)) where 0 ? j ? t?42 ?1 This construction of the ? blocks requires t ? 6. However, (t ? 1 + t?42 ) ? base blocks are produced which will allow v to overlap with the recursion when t > 8. Modifications on this construction and special cases of the recursion to cover t = 2,4,6,8 will be described. Here are the details for t = 2,3,4,5, 6, and 8. (20,v): For 20 ? v ? 38 use Lemma 5.2 and (10,h) where 0 ? h ? 18. When v = 18, Lemma 3.1 applies. When v = 13, Lemma 4.3 applies. v = 10,11,12,14,15,16,17 and 19: Use Lemma 5.3 where (a,b,c) = (10,10,10) and v = 0,1,2,4,5,6,7 and 9 respectively. v = 9: Use the Recursion with x = 8. 4 ? v ? 8: Use the Recursion with x = 10. (30,v): Modifytheaboveconstructionusing? baseblocks((0,1),(4,2),(2,1),(8,2)) and((0,1),(5,2), (4,1),(7,2)) to cover values 20 ? v ? 58. v = 19: Use the Recursion with x = 13. v = 18: Lemma 3.1 applies. v = 16 and 17: Use the Recursion with x = 14 and 12 respectively. 11 ? v ? 15: Use the Recursion with x = 10. v ? 10: The Recursion applies. (40,v): For 20 ? v ? 78 modify the above construction using ? base blocks: 29 ((0,1),(2,2),(1,1),(3,2)), ((0,1),(0,2),(3,1),(14,2)), ((0,1),(10,2),(5,1),(13,2)), ((0,1),(17,2),(2,1),(19,2)). v = 19: Use the Recursion with x = 13. v ? 18: The Recursion applies. (50,v): For 20 ? v ? 98 use the above construction replacing the ? base blocks with: ((0,1),(6,2),(2,1),(14,2)), ((0,1),(7,2),(4,1),(13,2)),((0,1),(8,2),(6,1),(12,2)), ((0,1),(9,2), (8,1),(11,2)),((0,1),(18,2),(1,1),(21,2)),((0,1),(22,2),(3,1),(23,2)). v ? 20: The Recursion applies. (60,v): For 30 ? v ? 118 use the above construction with the additional ? base block: ((0,1),(15,2),(12,1),(27,2)). v < 30: The Recursion applies. (80,v): For 50 ? v ? 158: Lemma 5.5 applies. v = 49,48: Use the Recursion with x = 30. v ? 47: The Recursion applies. square 30 Chapter 6 Conclusion Theorem 6.1 There exists a K4 ?e design on Kd +v when d is even if and only if 1. 5|d(d+ 2v ?1) 2. v ? 2(d?1) and v negationslash= 2d?3, v negationslash= 2d?4 Proof This is a direct result from Lemmas 3.1, 4.1, 4.2, 4.3, 5.1 and 5.5. square To solve the case when d is odd, new techniques will need to be applied. The use of difference methods in the construction of ? blocks and the use of 1-factors is not applicable when d is even. However, Lemma 2.1, the Recursion, and Lemma 5.3 are true regardless of the parity of d and may be useful tools in the future. 31 Bibliography [1] J. C. Bermond, and J. Scaonhein, G-Decomposition of Kt, where G has Four Vertices or Less. Discrete Mathematics 19 (1977) 113-126. [2] J. C. Bermond, C. Huang, A. Roda and D. Sotteau, Decomposition of Complete Graphs into Isomorhphic Subgraphs with Five Vertices. Ars Combinatoria 10 (1980) 211-254. [3] J. Doyen and R. M. Wilson, Embedding of Steiner Triple Systems. Discrete Mathematics 5 (1973) 229-239. [4] D. E. Bryant, C. A. Rodger and E. R. Spicer, Embedding m-cycle systems, and incom- plete m-cycle systems: m ? 14 Discrete Mathematics 171 (1997) 55-75. [5] D. G. Hoffman and K. S. Kirkpatrick, Another Doyen-Wilson Theorem. Ars Combina- toria 54 (2000), pp 87-92. [6] D. G. Hoffman, C. C. Lindner, Martin J. S. Harry and Anne Penfold Street, Maximum Packing of Kn with copies of K4 ?e. Aequationes Mathematicae 51 (1996) 247-269. [7] E. J. Billington, C. C. Lindner, E. S. Yazici, The triangle intersection problem for K4?e designs. Utilitas Mathematica 73 (2007) 3-21. 32