5-cycle systems by John Asplund A dissertation submitted to the Graduate Faculty of Auburn University in partial ful llment of the requirements for the Degree of Doctor of Philosophy Auburn, Alabama May 4, 2014 Keywords: 5-cycle systems, enclosing, cycle, embedding, decomposition Copyright 2014 by John Asplund Approved by Christopher Rodger, Chair, Don Logan Endowed Chair of Mathematics and Associate Dean for Research in the College of Sciences and Mathematics Dean Ho man, Professor of Mathematics Curt Lindner, Distinguished University Professor Peter Johnson, Professor of Mathematics Jessica McDonald, Assistant Professor Abstract A k-cycle system of a multigraph G is an ordered pair (V;C) where V is the vertex set of G and C is a set of k-cycles, the edges of which partition the edges of G. A k-cycle system of Kv is known as a -fold k-cycle system of order v. A k-cycle system (V;C) of Kv is said to be enclosed (embedded) in a k-cycle system (V[U;P) of ( + m)Kv+u if C P and u;m 1 (m = 0 and u 1). We settle the enclosing problem for -fold 5-cycle systems when u = 1 or 2. We settle the embedding problem for -fold 5-cycle systems except possibly in two cases. Other analogues of this are considered and consequently settled. ii Acknowledgments First and foremost, I would like to thank Dr. Rodger for his endless patience with me. This would not have been possible without you. Thank you for putting up with me and mentoring me for my next stage in life. My family have also played a pivotal role in getting me to where I am now. Thanks to the support and encouragement of Mom, Dad, Erin, and Nancy, I made to where I am today. Though my friends are scattered throughout the country, they have been a con- stant source of relief and help. These people have been able to keep me sane in times of great strife. Thank you Bill, Braxton, Carrie, Dave K., David C., Desi, Diane, Evie, James, Jason, Joe, Kat, Kevin, Kristina, Mel, Missy, Richard, Steve, Susan, and Tim. Thanks are in order for the secretaries for their help throughout my time at Auburn University: Gwen, Carolyn, and Lori. iii Table of Contents Abstract . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ii Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iii List of Figures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . vi List of Tables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . vii 1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.1 De nitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.2 History . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 2 Enclosings when u = 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 2.2 The small cases when u = 1 . . . . . . . . . . . . . . . . . . . . . . . 10 2.3 The Main Theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 3 Enclosings when u = 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28 3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28 3.2 Necessary tools . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28 3.3 Creating closed trail systems of Gv(D) . . . . . . . . . . . . . . . . . 33 3.4 The small cases for m . . . . . . . . . . . . . . . . . . . . . . . . . . . 50 3.5 The Main Result . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63 4 5{CS of ( +m)Kv+u Kv when u = 1 . . . . . . . . . . . . . . . . . . 67 4.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67 4.2 5{CSs of ( +m)Kv+1 Kv: The small cases . . . . . . . . . . . . . 68 4.3 5{CSs of ( +m)Kv+1 Kv: The Main Result . . . . . . . . . . . . 73 5 5-cycle systems when m = 0 . . . . . . . . . . . . . . . . . . . . . . . . . 78 5.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78 iv 5.2 5{CSs of Kv+u Kv: Preliminary Results . . . . . . . . . . . . . . 78 5.3 5{CSs of Kv+u Kv: 5 (mod 10) and u< 3v + 1 . . . . . . . 82 5.4 5{CSs of Kv+u Kv: Main Result . . . . . . . . . . . . . . . . . . 88 6 Conclusion/Future Work . . . . . . . . . . . . . . . . . . . . . . . . . . . 98 Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102 v List of Figures 1.1 K5 (left) and 2K5 (right) . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.2 A 4K6 K5 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 1.3 A 7-cycle (Hamilton cycle) with vertex set f0;1;:::;6g . . . . . . . . . . 3 1.4 A 5{CS of K5 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.5 A Steiner triple system on 7 vertices (STS(7)) . . . . . . . . . . . . . . . 4 1.6 A 5{CS of K5 is enclosed in a 5{CS of 4K6 . . . . . . . . . . . . . . . . 5 3.1 Possible 5-cycle Types . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33 5.1 Possible Types of 5-cycle . . . . . . . . . . . . . . . . . . . . . . . . . . . 79 5.2 Possible 5-cycle Types when 5 (mod 10) and u< 3v + 1 . . . . . . . 84 6.1 All types of 5-cycles based on the number of pure and mixed edges . . . 101 vi List of Tables 1.1 Necessary and su cient conditions for the existence of a 5{CS(v; ) . . . 7 2.1 Di erences of edges in BnE when is as large as possible . . . . . . . 13 2.2 Di erences of edges in BnE when is as large as possible . . . . . . . 15 2.3 Di erences of edges in B0 and E when is as large as possible for ?2 f2;3g and m = 5 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 2.4 Di erences of edges in B0 when is as large as possible for ?2f7;8gand m = 5 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 2.5 Di erences of edges in B when is as large as possible for ? = 1 and m = 1 20 2.6 Di erences of edges in B when is as large as possible for ?2f4;6g and m = 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 2.7 Di erences of edges in B when is as large as possible for ? = 9 and m = 1 21 2.8 Checking min(v;m) when v 1 or 6 (mod 10): each cell contains min(v;m) 24 2.9 Checking min(v;m) when v6 1 or 6 (mod 10): each cell contains min(v;m) 25 2.10 Checking the largest values of : each cell contains max(v;m) max(v;t(v)) max(v;m t(v)) for k 0;1; and 2 (mod 3) in turn. . . . . . . . . . . . 26 2.11 Checking the smallest values of for v 6 1 or 6 (mod 10): each cell contains min(v;m t(v)) + min(v;t(v)) min(v;m). . . . . . . . . . . 27 2.12 Checking the smallest values of for v 1 or 6 (mod 10): each cell contains min(v;m t(v)) + min(v;t(v)) min(v;m). . . . . . . . . . . 27 3.1 Edges of di erences in B0 when is as large as possible, v 0 (mod 10), and m = 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51 3.2 Edges of di erences in B00 when is as large as possible, v 0 (mod 10), and m2f4;6;8g . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52 vii 3.3 Edges of di erences in BnE when is as large as possible and v 5 (mod 10) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54 3.4 Edges of di erences in B when is as large as possible for ? = 1 . . . . . 56 3.5 Edges of di erences in B when is as large as possible for ?2f3;9g . . 56 3.6 Edges of di erences in B0 when is as large as possible for ?2f4;6g . . 58 3.7 Edges of di erences in B when is as large as possible for ? = 8 . . . . . 58 3.8 Edges of di erences in B0[E0 when is as large as possible for ? = 2 . 61 3.9 Edges of di erences in B0nE0 when is as large as possible for ? = 7 . 62 3.10 Checking min(v;m) when v 0;1;5 or 6 (mod 10): each cell contains min(v;m) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64 3.11 Checking min(v;m) when v 6 0;1;5 or 6 (mod 10): each cell contains min(v;m) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64 3.12 Checking the largest values of : each cell contains max(v;m) max(v;t(v)) max(v;m t(v)) except for some special values listed in Table 3.13. . . . 65 3.13 Checking the largest values of : each cell contains max(v;m) max(v;t(v)) max(v;m t(v)). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65 3.14 Checking the smallest values of for v6 0;1;5 or 6 (mod 10): each cell contains min(v;m t(v)) + min(v;t(v)) min(v;m). . . . . . . . . . . 66 3.15 Checking the smallest values of for v 1 or 6 (mod 10): each cell contains min(v;m t(v)) + min(v;t(v)) min(v;m). . . . . . . . . . . 66 4.1 Edges of di erences in B0 when is as large as possible for ?2f2;3gand m = 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70 4.2 Edges of di erences in B0 when is as large as possible for ?2f7;8gand m = 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72 4.3 List of min(v;m) values . . . . . . . . . . . . . . . . . . . . . . . . . . . 74 4.4 Each cell contains max(v;m) max(v;m 1) max(v;1) for k 0;1;2 (mod 3) in turn . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76 4.5 Each cell contains min(v;m 1) + min(v;1) min(v;m) . . . . . . . . 76 viii 5.1 Edges of di erences in B0 when is as large as possible for ? 4 and ?6= 5 91 5.2 Edges of di erences in B0 when is as large as possible for ? = 0 . . . . 92 5.3 Edges of di erences in B0 when is as large as possible for ?2f1;3g . . 94 5.4 Edges of di erences in B0 when is as large as possible for ? = 2 . . . . 94 5.5 Edges of di erences in B0 when is as large as possible for ? = 5 . . . . 95 ix Chapter 1 Introduction The goal of this dissertation is to construct 5-cycle systems of a speci c family of graphs using tools from design theory. With that said, we begin with an overview of the terminology in Section 1.1 and history in Section 1.2 that will set the foundation for the rest of the dissertation. At the end of Section 1.1 there will be a brief outline of the entire dissertation. 1.1 De nitions A graph G is an ordered pair (V(G);E(G)) where V(G) is a set of vertices and E(G) is a set of unordered pairs of vertices called edges. A subgraph of a graph G is a graph H such that V(H) V(G) and E(H) E(G). To simplify notation, V and E will be used instead of V(G) and E(G) respectively when the underlying graph is not important. Two vertices u and v are adjacent if there is an edge e =fu;vg2E(G); e is said to join these vertices. A graph with no loops or multiple edges is called a simple graph. On the other hand, a graph that does have loops or multiple edges is called a multigraph. When a graph on v vertices has exactly one edge between every pair of vertices, it is called a complete graph and is denoted Kv. The -fold complete graph on v vertices, denoted by Kv, is the multigraph in which every edge of Kv is repeated times (see Figure 1.1). The graph ( +m)Kv+u Kv is the graph formed from ( + m)Kv+u on the vertex set V [U by removing the edges of the subgraph Kv on the vertex set V where jVj= v and jUj= u (see Figure 1.2). Figure 1.1: K5 (left) and 2K5 (right) It is easier to understand the structure of a graph by describing the properties of the edges and vertices of a graph. An edge fvi;vjg is said to be incident to the vertices vi and vj. Two edges are incident if they share a common vertex. The 1 0 4 3 2 1 5 V U Figure 1.2: A 4K6 K5 degree of a vertex v0 is the number of edges that are incident with v0 and is denoted degG(v0) or deg(v0) when the underlying graph is not important. A sequence of vertices (v0;v1;:::;vn) such that fvi;vi+1g is an edge for each 0 i n 1 in the graph G is called a trail. A trail where v0 = vn is called a closed trail. A trail where each vertex in the sequence is unique is called a path. Two vertices v1 and v2 in a graph are connected if there is a path between v1 and v2. If every pair of vertices is connected then the graph is said to be connected. At times it will be convenient to talk about the set of integers from 0 to k 1. This notation is given as Zk = f0;1;:::;k 1g. A graph is k-regular if the degree of each vertex is k. A 2-regular connected graph is called a cycle. A cycle that contains every vertex in the graph G is called a Hamilton cycle. We will encounter situations where it will be very useful to talk about the length of a cycle. So a k-cycle (v0;v1;:::;vk 1) is the graph on k distinct vertices v0;v1;:::;vk 1 and with edge set E = ffvi;vi+1gj i 2 Zkg, reducing sums modulo k. The graph in Figure 1.3 is a 7-cycle and a Hamilton cycle. A decomposition of a graph G is a set of subgraphs that partition the edges of G. Typically, a graph is decomposed into copies of the same subgraph. This dissertation will only focus on the decomposition of graphs into cycles. A k-cycle system, k{CS, of a multigraph G is an ordered pair (V;C) where V is the vertex set of G and C is a set of k-cycles, the edges of which partition the edges of G. A k-cycle system of (a subgraph of) Kv, k{CS(v; ), is known as a (partial) -fold k-cycle system of order v. The graph in Figure 1.4 is a 5{CS of K5 (i.e. a 1-fold 5-cycle system). When k = 3 and = 1, this structure is also called a Steiner triple system of order v, or an STS(v). A Steiner triple system is a pair (V;B) whereV is a v-set of points andB is a collection of 3-subsets, called blocks, such that each pair of points ofV is contained in exactly one block. The graph in Figure 1.5 is a decomposition of K7 into 3-cycles 2 0 1 2 34 5 6 Figure 1.3: A 7-cycle (Hamilton cycle) with vertex set f0;1;:::;6g (i.e. a Steiner triple system of order 7). Kirkman showed in [21] that there exists a Steiner triple system of order v if and only if v 1 or 3 (mod 6). Figure 1.4: A 5{CS of K5 A problem that has attracted much interest over the years is to nd conditions which guarantee that a given (partial) k{CS of Kv (V;C) is contained in a k{CS of ( +m)Kv+u (V[U;P) with C P. If u;m = 0 then (V;C) is said to be completed in (V [U;P) = (V;P), if m = 0 then (V;C) is said to be embedded, if u = 0 then (V;C) is said to be immersed, and if u;m 1 then (V;C) is said to be enclosed in (V [U;P). This dissertation will focus exclusively on enclosings and embeddings. In particular, the focus will be placed on both the existence of enclosings of 5{CSs and the existence of 5{CSs of ( +m)Kv+u Kv. When nding such cycle systems, since the edges of Kv have already been placed in the given k-cycles in C, it remains to nd a k{CS of ( + m)Kv+u Kv. Figure 1.6 shows that a 5{CS of K5 can be enclosed in a 5{CS of 4K6. In order to attack these 5-cycle system problems, we need to construct 5-cycles in a exible manner. To this end, Skolem-type sequences are used in a creative way. In 1957, while working on the construction of Steiner triple systems, Skolem published 3 0 1 2 34 5 6 Figure 1.5: A Steiner triple system on 7 vertices (STS(7)) in [30] a construction that used sequences of integers with special properties. Later, an equivalent formulation in terms of sequences was made with an improvement on their construction in [1, 5, 26, 29]. Formally we de ne a Skolem sequence of order n as a sequence of integers S = (d1;:::;d2n) such that the following two conditions are met: 1. For every 2f1;:::;ng there exist exactly two elements dx;dy 2S such that dx = dy = , and 2. if dx = dy = with x 1. For a k{CS of Kv, de ne v to be (k; )-admissible if the degree of each vertex is even, the number of edges in Kv is divisible by k, and v = 1 or v k. Through the e orts of Bermond, Hanani, Huang, Rosa, and Sotteau in [7, 8, 17, 18, 27], it was shown that for 3 k 14 and k = 16, there exists a k{CS of Kv if and only if v is ( ;k)-admissible. It was not until recently that Bryant, Horsley, Maenhaut, and Smith in [10] were able to show there exists a k{CS of Kv if and only if v is ( ;k)-admissible. Of particular interest to this dissertation is the case when k = 5. Theorem 1.2.2. [10] A 5{CS of Kv exists if and only if (a) v(v 1) 0 (mod 5), (b) (v 1) 0 (mod 2), and (c) either v = 1 or v 5. Since the immersing problem is exactly the same as showing there exists a k{CS of Kv, this problem has already been completely solved by Bryant, Horsley, Maenhaut, and Smith in [10]. Since this paper focuses solely on building 5{CS, it will cause no confusion to refer to a ( ;5)-admissible integer as simply being -admissible. Also is said to be v-admissible if the conditions in Theorem 1.2.2 are satis ed by Kv. Some consequences of Theorem 1.2.2 are summarized in Table 1.1. Possible values of v 0 (mod 10) v62f2;3;4g 1;3;7;9 (mod 10) v 1;5 (mod 10) 2;4;6;8 (mod 10) v 0;1 (mod 5) 5 (mod 10) v 1 (mod 2);v6= 3 Table 1.1: Necessary and su cient conditions for the existence of a 5{CS(v; ) Doyen and Wilson were able to prove in 1973 the following result for embeddings 7 on Steiner triple systems (i.e. embedding a 3{CS in another 3{CS); commonly called the Doyen-Wilson theorem. Theorem 1.2.3. [16] A Steiner triple system of order u can be embedded in a Steiner triple system of order v>u if and only if v 2u+ 1 and v 1 or 3 (mod 6). Rodger and Bryant were able to extend the Doyen-Wilson theorem to hold for all odd k-cycle lengths when k 9. Theorem 1.2.4. [12, 13] A k{CS of Kv can be embedded in a k{CS of Kv+u if and only if the following conditions hold: If k = 5 then v +u 1 or 5 (mod 10) and u v=2 + 1. If k = 7 then v +u 1 or 7 (mod 14) and u v=3 + 1. If k = 9 then v +u 1 or 9 (mod 18) and u v=4 + 1. Later, Bryant, Rodger, and Spicer were able to extend these results to embedding k-cycle systems when k 14 in [14]. Some work has been seen in generalizing these results to establish the existence of a k{CS of Kv+u Kv. Mendelsohn and Rosa were able to show the necessary conditions were su cient for the existence of a 3-cycle system of Kv+u Kv. Bryant, Ho man and Rodger were able to establish the necessary and su cient conditions for the existence of a 5-cycle system of Kv+u Kv. Theorem 1.2.5. [23] There exists a 3-cycle system of Kv+u Kv if and only if u v + 1 and 1. v +u;v 1 or 3 (mod 6), or 2. v +u v 5 (mod 6). Theorem 1.2.6. [11] There exists a 5-cycle system of Kv+u Kv if and only if u v=2 + 1 and 1. v +u;v 1 or 5 (mod 10), or 2. v +u v 3 (mod 10), or 3. v +u;v 7 or 9 (mod 10). Again in [14], Bryant, Rodger, and Spicer were able to show there exists a k-cycle system of Kv+u Kv when k = 4;6;7;8;10;12; and 14. Many papers have investigated the -fold 3{CS enclosing problem (see for ex- ample [15, 19, 20, 25]). The di culty of this problem is clear since as yet there is no complete solution to this problem. Newman and Rodger [24] completely solved the problem of enclosing a -fold 4{CS of order v into a ( +m)-fold 4{CS of order v+u for all u;m 1. Typically, problems involving odd cycles have many more di culties than related even cycle problems, and that is certainly the case here. The techniques used in the subsequent chapters for the 5{CS enclosing problem are very di erent to those used in [24]. 8 Chapter 2 Enclosings when u = 1 2.1 Introduction In this chapter, we study the -fold 5{CS enclosing problem, settling the fol- lowing conjecture in the case where u = 1 (see Theorem 2.3.2). The joint work in this chapter has been published in [4]. As in Lemma 2.1.2, all 5 conditions in this conjecture are necessary, i.e. the di culty when studying Conjecture 2.1.1 lies in proving su ciency. Conjecture 2.1.1. Let u 1. Every 5{CS of Kv can be enclosed in a 5{CS of ( +m)Kv+u if and only if (a) ( +m)u+m(v 1) 0 (mod 2), (b) u2 ( +m) +m v2 +vu( +m) 0 (mod 5), (c) if u = 1, then m(v 1) 3( +m), and (d) if u = 2, then m v2 2( +m) (v 1)( +m)=2 0. (e) if u 3, then dvu( + m)=4e+ 2 mv(v 1)=2 + ( + m)u(u 1)=2 where = 0 or 1 if vu( +m) 0 or 2 (mod 4) respectively. Lemma 2.1.2 establishes the necessary conditions in Conjecture 2.1.1. Lemma 2.1.2. Suppose there exists a 5{CS of Kv. If this can be enclosed in a 5{CS of ( +m)Kv+u, then: (a) ( +m)u+m(v 1) 0 (mod 2), (b) u2 ( +m) +m v2 +vu( +m) 0 (mod 5), (c) if u = 1, then m(v 1) 3( +m), (d) if u = 2, then m v2 2( +m) (v 1)( +m)=2 0, and (e) if u 3, then dvu( + m)=4e+ 2 mv(v 1)=2 + ( + m)u(u 1)=2 where = 0 or 1 if vu( +m) 0 or 2 (mod 4) respectively. Proof. Suppose there exists a 5{CS (V;C1) of Kv that can be enclosed in a 5{CS (V [U;C2) of ( +m)Kv+u. It is clear that each vertex in each of ( +m)Kv+u and Kv has even degree in order for the 5{CSs of ( + m)Kv+u and Kv to exist. So ( + m)(v + u 1) and (v 1) are both even, proving (a). Since there exists a 5{CS of ( + m)Kv+u and a 5{CS of Kv, the number of edges of each graph must be divisible by 5. Thus ( + m)u(u 1)=2 + ( + m)v(v 1)=2 + ( + m)uv and v(v 1)=2 are divisible by 5. So ( +m) u 2 + ( +m) v 2 + ( +m)uv v 2 = ( +m) u 2 +m v 2 +vu( +m) 0 (mod 5): 9 Therefore condition (b) holds. Suppose u = 1 and let U = f1g. There must be + m edges connecting each vertex in V to1, so the degree of1is ( +m)v. Each 5-cycle in C2 containing1uses two of these edges, so the number of 5-cycles containing 1 is v( + m)=2. Because mKv has m v2 edges, and since any 5-cycle containing 1 uses 3 edges from this graph, it follows that the number of such 5-cycles in C2 must be at most mv(v 1)=6, so v( +m)=2 mv(v 1)=6. Thus condition (c) holds. Suppose u = 2 and let U =f11;12g. An edge is pure if it joins two vertices in V or if it joins two vertices in U; otherwise it is said to be mixed. Each of the +m edges joining11 to12 must be in a 5-cycle in C2 that contains exactly 2 pure edges in mKv and exactly 2 mixed edges. There are 2v( +m) 2( +m) = 2(v 1)( +m) remaining mixed edges. Furthermore, the other 5-cycles in C2 which contain at least one vertex in U must exhaust these remaining edges. Each 5-cycle in C2 can use at most 4 of the mixed edges, and so each 5-cycle of this type uses at least one edge in mKv. Thus it must be that 0 m v 2 2( +m) 2(v 1)( +m)4 = m v 2 2( +m) 12(v 1)( +m): Therefore condition (d) holds. Suppose u 3. Every 5-cycle in C2 that contains a mixed edge must contain at least one pure edge, and at most 4 mixed edges. So there are at leastdvu( +m)=4e 5-cycles in C2 containing mixed edges. Furthermore, if vu( +m) 2 (mod 4) then at least one such 5-cycle must contain 2 mixed and 3 pure edges. (Note that since each 5-cycle contains 0, 2, or 4 mixed edges it follows that vu( +m) is even.) Thus, there must be at leastdvu( +m)=4e+2 pure edges in 5-cycles containing at least one vertex in U where 2f0;1g. Sodvu( +m)=4e+2 mv(v 1)=2+( +m)u(u 1)=2 and condition (e) holds. Notice that if u = 1 and = 0 then the enclosing problem is equivalent to the existence of a 5{CS of mKv+1, and Conditions Lemma 2.1.2(a-c) imply Conditions Theorem 1.2.2(a-c) with replaced by m and v by v + 1. So this case is already solved. Section 2.2 addresses the cases when v = 10k + ? for ?2 Z10 and m is small. We take the results from Section 2.2 and use them to prove our main result of this chapter, Theorem 2.3.2, in Section 2.3. 2.2 The small cases when u = 1 We now create the tools necessary to solve the problem of enclosing a -fold 5{CS of order v into a ( + m)-fold 5{CS of order v + u for all m > 0 and u = 1. For the remainder of this chapter, let u = 1 with U = f1g being the vertex set of V(Kv+u)nV(Kv). 10 Recall that for any cycle c = (c1;:::;cx) with entries in Zv, we de ne c + j = (c1 +j;:::;cx +j), reducing the sums modulo v, and de ne C +j =fc+jjc2Cg. For any D f1;:::;bv=2cg; let Gv(D) be the graph with vertex set Zv and edge set ffi;jgjdv(i;j)2Dg. Let D(v) =f1;:::;bv=2cg. Since we consider multigraphs in this dissertation, we need to introduce the multiset D? de ned to contain ? copies of each element in D; then Gv(D(v)?) contains ? copies of each edge with di erence in D(v). When v and ? are both even, it is useful to let D(v) ? be formed from D(v)? by removing ?=2 copies of the di erence v=2. This is very important notation because then the edge set of ?Kv = Gv(D(v) ?) can usefully be de ned as E(?Kv) =ff0;dg+jjd2D(v) ?;j2Zvg since each occurrence of v=22D(v) ? gives rise to two copies of the edgefx;x+v=2g in E(Gv(D(v)?)) (namely when j = x and when d = x + v=2). Another multiset convention we use is that for any positive integer t, tD is the multiset containing t copies of each element of D. The following is a critical result, being used hand in hand with the observation that there exists a 5{CS of Gv(fv=5g) and of Gv(f2v=5g) when v 0 (mod 5), since each component is a 5-cycle. So throughout this dissertation, when v 0 (mod 5) let (Zv; 1), (Zv; 2) and (Zv; 3) be a 5{CS of Gv(fv=5g);Gv(f2v=5g), and Gv(f1;2;3g) respectively. Lemma 2.2.1. If 5 divides v, then there exists a 5{CS of Gv(f1;2;3g). Proof. (Zv;f(0;1;4;5;2)+5j;(3;4;6;8;5)+5j;(2;3;6;7;4)+5jjj2Zv=5g) is a 5{CS of Gv(f1;2;3g) since for each d 2f1;2;3g, the edges of di erences d in the cycles (0;1;4;5;2), (3;4;6;8;5), and (2;3;6;7;4) are of the form fx;x+dg where each x is distinct modulo 5. The next lemma points to our main approach to proving Theorem 2.3.2, showing that the number of 5-cycles to be de ned on the originalv vertices during the enclosing is divisible by v. The parameter will play a critical role throughout the rest of the dissertation. Lemma 2.2.2. Suppose there exists a 5{CS (V[U;B) of ( +m)Kv+1 Kv where U = f1g. Then the number of edges in 5-cycles avoiding the vertex 1 is v = (m(v 1)=2 3( +m)=2)v. Proof. There are mv(v 1)=2 edges in mKv, 3v( +m)=2 of which occur in 5-cycles in B, that contain the vertex 1. So mv(v 1)2 3v( +m)2 = m(v 1) 2 3( +m) 2 v = v (2.1) is the number of edges in 5-cycles in B with all vertices in V. 11 An integer x is said to be (v;m)-admissible if there exists an integer for which v is -admissible and for which Lemma 2.1.2(c) is satis ed by m;v and such that = m(v 1)=2 3( + m)=2 = x. (During the enclosing process, we usually x v and m to consider all possible values of . Each such value of has an associated value of , and the set of all such values are the (v;m)-admissible integers.) The next lemma will be used when constructing the 5-cycles in the enclosing that contain the vertex 1; each such 5-cycle uses exactly 3 edges joining vertices in mKv. Lemma 2.2.3. Suppose that the Conditions Lemma 2.1.2(a-c) are satis ed and that there exists a 5{CS of Kv. Then if v is odd, or if v is even and m is even, 3 divides m(v 1)=2 . If v is even and m is odd then 3 divides m(v 1)=2 3=2. Proof. If v is odd then by Lemma 2.1.2(a), +m is even. If v is even then is even by Theorem 1.2.2(b) (since there exists a 5{CS of Kv). Thus if v is odd or if v is even and m is even, then 3 divides m(v 1)=2 . Now suppose v is even and m is odd. Then m(v 1)=2 3=2 = 3( + m 1)=2 is clearly divisible by 3, and otherwise m(v 1)=2 = 3( +m)=2 is divisible by 3. The following result will be useful to refer to throughout the subsequent con- structions. Note that it implies that all (v;m)-admissible integers are non-negative. Lemma 2.2.4. Suppose u = 1. Condition (c) Lemma 2.1.2 is equivalent to 0. Proof. Clearly m(v 1) 3( +m) if and only if m(v 1)=2 3( +m)=2 0. The following lemma is constantly used in subsequent constructions. Lemma 2.2.5. If 0 d1 d2 d3 v=2, d1 < d3, and d2 < v=2 then c = (d1;0;d3;d2 +d3;1i) is a 5-cycle in Kv+u with vertex set Zv[f10;11;:::;1u 1g. Proof. The 5 vertices in c are clearly distinct. For all positive integers v and m, let max(v;m) and min(v;m) be the largest and smallest integers for respectively satisfying Conditions (a-c) in Lemma 2.1.2 with u = 1. It is probably no surprise that many larger enclosings can be found by combining two smaller enclosings. This observation is the basis of the inductive proof of Theo- rem 2.3.2. So now we focus on nding enclosings that cannot be found using this ap- proach. This involves the cases where m = 1, and where 2f max(v;m); min(v;m)g for some small values of m. Lemma 2.2.6. Let v = 10k and assume conditions (a-c) of Lemma 2.1.2 are satis ed. If m = 1, or if m2f2;3gand = max(v;m), then any 5{CS of Kv can be enclosed in a 5{CS of ( +m)Kv+1. 12 Proof. Let (V = Z10k;A) be a 5{CS of Kv and let U =f1g. Since (V;A) exists, is even by Lemma 2.1.2(a). First, note that there aremv(v 1)=2 edges inmKv, 3v( +m)=2 of which must be placed in 5-cycles that contain the vertex1. So we de ne v as in Equation (2.1) of Lemma 2.2.2 to be the number of edges we must place in 5-cycles contained completely in mKv. Since this is divisible by v, our plan is to create 5-cycles in mKv using all the edges of specially chosen di erences. Note that 0 by Lemma 2.2.4. Suppose m = 1. Then mKv = Kv contains edges of each di erence in D(v) = f1;:::;5kg. To explicitly describe the 5-cycles containing all the edges of di erences (yet to be chosen), we make use of Skolem and hooked Skolem sequences. Let P0 =f(x0i;y0i)j1 i k 1;y0i >x0igbe the collection of pairs from a Skolem sequence or hooked Skolem sequence of order k 1 from the setf1;2;:::;2k 2gor f1;2;:::;2k 1gif k 1 0 or 1 (mod 4) or k 1 2 or 3 (mod 4) respectively (see Theorems 1.1.1 and 1.1.2). So each element inf1;2;:::;2k 2gorf1;2;:::;2k 1gn f2k 2goccurs in exactly one element of P0. If k 1 0 or 1 (mod 4) then name the Skolem pairs so that (x0k 1;y0k 1) contains 2k 3. If k 1 2 or 3 (mod 4) then name the hooked Skolem pairs so that x0k 1 = 1. Now de ne P =f(xi = x0i+3;yi = y0i+3)j (x0i;y0i) 2 P0g when using Skolem sequences and P = f(xi = x0i + 2;yi = y0i + 2) j (x0i;y0i) 2 P0g when using hooked Skolem sequences; notice that 2k 2fxk 1;yk 1g and xk 1 = 3 respectively. Then form the set of 5-cycles B = n (0;xi;xi yi;3k;5k + 1 +i) +jj1 i j 5 k ;j2Zv;(xi;yi)2P o [E where computations are done modulo v, and where E = 8 >>> >>> < >>> >>> : ? if 0 (mod 5); 2 if 1 (mod 5); 1[ 2 if 2 (mod 5); 3 if 3 (mod 5); 2[ 3 if 4 (mod 5): (2.2) Table 2.1 lists the di erences of edges that occur in cycles in BnE when is as big as possible (from Lemma 2.2.2 we see this happens when is as small as possible and not 0, namely when = 2, and so when = 5k 5). Edges Di erenceswhenk 1 0;1 (mod 4) Di erenceswhenk 1 2;3 (mod 4) f0;xig;fxi;xi yig 4;5;:::;2k+1 3;4;:::;2k 1;2k+1 fxi yi;3kg 3k+1;3k+2;:::;4k 1 3k+1;3k+2;:::;4k 1 f3k;5k+1+ig 2k+2;2k+3;:::;3k 2k+2;2k+3;:::;3k f5k+1+i;0g 4k;4k+1;:::;5k 2 4k;4k+1;:::;5k 2 Table 2.1: Di erences of edges in BnE when is as large as possible Notice that when is as large as possible: 13 (i) if k 1 0 or 1 (mod 4), then the 5-cycle in BnE de ned when i =b =5c= k 1 contains edges of di erences 2k = v=5 (since 2k 2 fxk 1;yk 1g) and 4k = 2v=5, and (ii) if k 1 2 or 3 (mod 4), then the 5-cycle in BnE de ned when i =b =5c= k 1 contains edges of di erences 3 (since xk 1 = 3) and 4k = 2v=5. Fortunately, when is as large as possible, 0 (mod 5) since = 2, so E = ?. If is smaller, then (i)-(ii) from above shows that the edges of di erences 1;2;3;v=5 and 2v=5 do not occur in 5-cycles in BnE (since then ix0ig be the collection of pairs from a Skolem sequence or hooked Skolem sequence of order k 2 from the set f1;2;:::;2k 4g or f1;2;:::;2k 3g if k 2 0 or 1 (mod 4) or k 2 2 or 3 (mod 4) respectively (this exists by Theorems 1.1.1 and 1.1.2 since k 3). So each element inf1;2;:::;2k 4gorf1;2;:::;2k 3gnf2k 4goccurs in exactly one element of P0. Now de ne P =f(xi = x0i + 3;yi = y0i + 3)j(x0i;y0i)2P0g. Then with ci = 8 >< >: (0;xi;xi yi;4k + 2;7k + 3 i) if 1 i b =5c 1; (0;2k;6k + 1;8k + 3;5k + 2) if i =b =5c and k 2 0;1 (mod 4), and (0;2k 1;6k;8k + 2;5k + 1) if i =b =5c and k 2 2;3 (mod 4), we form the set of 5-cycles B = fci +jj1 i b =5c;j2Zvg[E where the computations are done modulo v, k 3, and where E is de ned as in Equation (2.2). Table 2.2 lists the di erences of edges that occur in cycles in BnE if is as big as possible (from Lemma 2.2.2 this happens when is as small as possible, namely when = 1 and so = 5k 1). Fortunately, the edges of di erences 1;2;3;v=5 and Edges Di erenceswhenk 2 0;1 (mod 4) Di erenceswhenk 2 2;3 (mod 4) f0;xig;fxi;xi yig 4;5;:::;2k 1 4;5;:::;2k 2;2k fxi yi;4k+2g 4k+3;4k+4;:::;5k 4k+3;4k+4;:::;5k f4k+2;7k+3 ig 2k+3;2k+4;:::;3k 2k+3;2k+4;:::;3k f7k+3 i;0g 3k+3;3k+4;:::;4k 3k+3;3k+4;:::;4k ci ifi=b =5c 2k;2k+2;3k+1;4k+1;5k+2 2k 1;2k+2;3k+1;4k+1;5k+1 Table 2.2: Di erences of edges in BnE when is as large as possible 2v=5 do not occur in 5-cycles in BnE , hence are available to form the 5-cycles in 15 E . By Lemma 2.2.3 we know that m(v 1)=2 0 (mod 3), and so the edges not occurring in a 5-cycle in B can be partitioned by the m(v 1)=2 remaining di erences. Form a partition P0 of these di erences into ((v 1)=2 )=3 sets of size 3. De ne C as in Equation (2.4). Notice that by Lemma 2.2.5 the edges in ffd1;0g;f0;d3g;fd3;d3 + d2gg induce a 3-path in Kv. So the elements of C are all 5-cycles. Then, (Z10k+5[f1g;A[B[C) is a 5{CS(v + 1; + 1) for v = 10k + 5. It is left to provide the required sets of 5-cycles when m = 1 and k = 0;1 and 2. Notice that if k = 0, then 0, so this case need not be considered. Suppose k = 1, so v = 15. Then by Lemma 2.1.2(c) and since +m = + 1 is even, it follows that 2f1;3g. So ( ; )2f(1;4);(3;1)g. De ne C = ( f(d1;0;d3;d2 +d3;1) +jj(d1;d2;d3) = (4;5;7);j2Zvg if = 1, and f(d1;0;d3;d2 +d3;1) +jj(d1;d2;d3)2f(1;2;3);(4;5;7)g;j2Zvg if = 3, and B = E . Then (Z15 [f1g;A[B[C) is a 5{CS(16; + 1). If k = 2, so v = 25, then 7; so = 1;3;5; or 7 and = 9;6;3; or 0 respectively. De ne C= 8> >< >>: f(d1;0;d3;d2 +d3;1)+jj(d1;d2;d3) =(5;7;9);j2Zvg if =1, f(d1;0;d3;d2 +d3;1)+jj(d1;d2;d3)2f(1;2;3);(5;7;9)g;j2Zvg if =3, f(d1;0;d3;d2 +d3;1)+jj(d1;d2;d3)2f(4;5;6);(7;8;9);(10;11;12)g;j2Zvg if =5,and f(d1;0;d3;d2 +d3;1)+jj(d1;d2;d3)2f(x;x+1;x+2)jx2f1;4;7;10gg;j2Zvg if =7; and B = ( f(0;4;10;22;8) +jjj2Z25g[E if 2f1;3g, E if 2f5;7g. Then (Z25[f1g;A[B[C) is a 5{CS(26; + 1). Now suppose m = 2 and = max(v;m). By Lemma 2.1.2(c), m(v 4)=3, and by Lemma 2.1.2(a), is even. So max(v;2) = 2b(v 4)=3c, and = v 4 3b(v 4)=3c= 0;1; or 2 if k 2;0; or 1 (mod 3) respectively. So de ne B = ?; 1, or 1 [ 2 if k 2; 0; or 1 (mod 3) respectively, and let = ?;fv=5g, or fv=5;2v=5g when = 0;5; or 10 respectively. Using Lemma 2.2.3 we know that jD(v)2n j 0 (mod 3), we can form a partition P0 of D(v)2n into sets of size 3. Then de ne C as in Equation (2.4), again noting that the elements of C are 5-cycles by Lemma 2.2.5. Therefore, (Zv[f1g;A[B[C) is a 5{CS(v+1; +2) with = max(v;2). Finally, suppose m = 3 and = max(v;3) = v 4. It follows that = 0 for all k. So we de ne B = ?. Since 3(v 1)=2 0 (mod 3) by Lemma 2.2.3, form a partition P0 of D(v)3 into (3(v 1)=2 )=3 sets of size 3 (again it is easy to ensure that no element of P0 contains a di erence three times). De ne C as in Equation (2.4). Then elements of C are all 5-cycles by Lemma 2.2.5. Then, (Zv[f1g;A[B[C) is a 5{CS(v + 1; + 3) with = max(v;3). 16 Lemma 2.2.8. Let v 2 or 3 (mod 5) and assume conditions (a-c) of Lemma 2.1.2 are satis ed. If m = 5 or if m2f10;15g and = max(v;m), then any 5{CS of Kv can be enclosed in a 5{CS of ( +m)Kv+1. Proof. Let (V = Zv;A) be a 5{CS of Kv where v = 10k+? for some ?2f2;3;7;8g and let U =f1g. By Theorem 1.2.2(c), v 7. In each case it is shown that (V;A) can be enclosed in a 5{CS (V [f1g;A[B[C) of ( +m)Kv+1 by de ning B and C. First, note that by Lemma 2.2.2, the number of edges we must place in 5-cycles contained completely in mKv is v as de ned in Equation (2.1). Since this is divisible by v, our plan is to create 5-cycles in mKv using the edges of specially chosen di erences. Notice that 0 by Lemma 2.2.4. Suppose m = 5. Then 0 or 5 (mod 10) if v 2;8 or 3;7 (mod 10) respec- tively. Note that when is as small as possible is as large as possible: that is, when = 10, = 25k 20 for ? = 2 and = 25k 5 for ? = 8; and when = 5, = 25k 10 for ? = 3 and = 25k for ? = 7. The edges of 5Kv are considered to be E(Gv(D(v) 4))[E(Gv(D(v))) when v is even and E(Gv(D(v)5)) when v is odd. For v even, care must be taken with edges of di erence v=2 in E(Gv(D(v))) since there are only v=2 of them. As in Lemma 2.2.6, we will use Skolem and hooked Skolem sequences to explicitly describe the 5-cycles containing all the edges of di erences (yet to be chosen). To form the set of cycles B, we consider the cases ?2f2;3g and ?2f7;8g in turn. Suppose ? 2 f2;3g. Let P0 = f(x0i;y0i) j 1 i k 1;y0i > x0ig be the collection of pairs from a Skolem sequence or hooked Skolem sequence of order k 1 for the set f1;2;:::;2k 2g or f1;2;:::;2k 1g, if k 1 0 or 1 (mod 4) or k 1 2 or 3 (mod 4) respectively. So each element in f1;2;:::;2k 2g or f1;2;:::;2k 1gnf2k 2g occurs in exactly one element of P0. Now de ne P =f(xi = x0i + 2;yi = y0i + 2)j(x0i;y0i)2P0g. Then we form the set of 5-cycles B0 =fci 1 = (0;xi;xi yi;3k + 1;5k +?+i)j1 i k 1;(xi;yi)2Pg where computations are done modulo v. We also need to de ne E when is as large as possible. Let E0 = 8 >>>< >>> : (0;2k + 1;2k;2k 1;5k) if k 1 0;1 (mod 4) and ? = 2, (0;2k;5k + 1;5k 1;5k) if k 1 2;3 (mod 4) and ? = 2,S 3 i=1f(0;2;2k + 3;1;5k + 1)g if k 1 0;1 (mod 4) and ? = 3, andS 3 i=1f(0;1;2k + 1;7k + 2;5k)g if k 1 2;3 (mod 4) and ? = 3. Notice that when ? = 3, E0 is a multiset that contains 3 copies of the 5-cycle. Table 2.3 lists the di erences of the edges that occur in cycles in B0 when is as large as possible and in E0 . Let B00 = 5B0 be the multiset consisting of 5 copies of each 5-cycle in B0. When is as large as possible,jB00[E0 j= 5k 4 or 5k 2 if ? = 2 or 3 respectively, sojB00[E0 j= =5. If is not as big as possible then 25k 25 17 in all cases (since as increases by 10, decreases by 15) so jB00j = 5k 5 =5. Therefore we de ne B = (S j2Zv(B 00 +j)[fc+jjc2E0 ;j2Zvg if is as large as possible, and fci +jji2Z =5;ci (mod k 1) 2B00;j2Zvg otherwise. Edges Di erenceswhenk 1 0;1 (mod4) Di erenceswhenk 1 2;3 (mod4) f0;xig;fxi;xi yig 3;4;:::;2k 3;4;:::;2k 1;2k+1 fxi yi;3k+1g 3k+2;3k+3;:::;4k 3k+2;3k+3;:::;4k f3k+1;5k+?+ig 2k+?;2k+1+?;:::;3k 2+? 2k+?;2k+1+?;:::;3k 2+? f5k+?+i;0g 5k 1;5k 2;:::;4k+1 5k 1;5k 2;:::;4k+1 E if =25k 20;?=2 1;1;2k+1;3k+1;5k 1;2;2k;3k+1;5k E0 if =25k 10;?=3 2;2;2;2k+1;2k+1;2k+1;2k+2;2k+2; 1;1;1;2k;2k;2k;2k+2;2k+2;2k+2;2k+2;5k;5k;5k;5k+1;5k+1;5k+1 5k;5k;5k;5k+1;5k+1;5k+1 Table 2.3: Di erences of edges inB0 andE when is as large as possible for?2f2;3g and m = 5 Now suppose ?2f7;8g. Let P =f(xi;yi)j1 i k;yi >xig be the collection of pairs from a Skolem sequence or hooked Skolem sequence of order k for the set f1;2;:::;2kg or f1;2;:::;2k + 1g, if k 0 or 1 (mod 4) or k 2 or 3 (mod 4) respectively. So each element in f1;2;:::;2kg or f1;2;:::;2k + 1gnf2kg occurs in exactly one element of P. Form the set of 5-cycles B0 = fci 1 = (0;xi;xi yi;3k + 2;5k + 4 + i) j 1 i k;(xi;yi) 2 Pg where computations are done modulo v. Let B00 = 5B0 be the multiset consisting of 5 copies of each 5-cycle in B0. De ne B =fci +jji2Z =5;ci (mod k) 2B00;j2Zvg. Table 2.4 lists the di erences of edges that occur in cycles in B0. Edges Di erenceswhenk 0;1 (mod 4) Di erenceswhenk 2;3 (mod 4) f0;xig;fxi;xi yig 1;2;:::;2k 1;2;:::;2k 1;2k+1 fxi yi;3k+2g 3k+3;3k+4;:::;4k+2 3k+3;3k+4;:::;4k+2 f3k+2;5k+4+ig 2k+3;2k+4;:::;3k+2 2k+3;2k+4;:::;3k+2 f5k+4+i;0g 5k 5+?;5k 6+?;:::;4k 4+? 5k 5+?;5k 6+?;:::;4k 4+? Table 2.4: Di erences of edges in B0 when is as large as possible for ?2f7;8gand m = 5 To de ne C, suppose ?2f2;3;7;8g. Notice that by Lemma 2.2.3 we know that 3 divides (5(v 1)=2 ) when v is odd and 3 divides (5(v 1)=2 3=2) when v is even. Form a partition P0 of the di erences not used to form B into (5(v 1)=2 )=3 sets of size 3 when v is odd, and when v is even into (5(v 1)=2 3=2)=3 sets of size 3 (not multisets) and one setfd;v=2gof size 2 with d6= v=2, when v is even; it is easy to ensure that d1 < >: ? if = 0, f(0;1;4;2;6) +jjj2Zvg if = 5, and f(0;1;4;2;6) +jjj2Zvg[f(0;1;4;2;6) +jjj2Zvg if = 10, and let = ?;f1;2;3;4;6g, or f1;1;2;2;3;3;4;4;6;6g when = 0;5; or 10 respec- tively. By Lemma 2.2.3,jD(v)10n j 0 (mod 3) when v is odd andj(D(v) 10)n j 0 (mod 3) when v is even. Form a partition P0 of D(v)10n when v is odd and D(v) 10n when v is even into (m(v 1)=2 )=3 sets of size 3. Then de ne the 5-cycles in C as in Equation (2.4) (it is easy to ensure that d1 < d3 and d2 < v=2, and so by Lemma 2.2.5 the elements of C are all 5-cycles). Thus (Zv[f1g;A[B[C) is a 5{CS(v + 1; + 10) for v 2 or 3 (mod 5) and = max(v;m). Let m = 15 and = max(v;15) = 5(v 4). It follows that = 0 for all k. So de ne B = ?. Using Lemma 2.2.3 we know that 15(v 1)=2 0 (mod 3) when v is odd and 15(v 1)=2 3=2 0 (mod 3) when v is even, so we can form a partition P0 of D(v)15 into (15(v 1)=2 )=3 sets of size 3 when v is odd and when v is even form a partition P0 of D(v) 14[D(v) into (15(v 1)=2 3=2)=3 sets of size 3 and one set fd;v=2g of size 2 with d6= v=2. De ne C as in Equation (2.4) when v is odd and as in Equation (2.3) when v is even (it is easy to ensure d1 xig be the collection of pairs from a Skolem sequence or hooked Skolem sequence of order k for the set f1;2;:::;2kg or f1;2;:::;2k + 1g, if k 0 or 1 (mod 4) or k 2 or 3 (mod 4) respectively. So each element in f1;2;:::;2kg or f1;2;:::;2k + 1gnf2kg occurs in exactly one element of P. For ? = 1, let P = f(xi;yi) j 1 i k 1;yi > xig be the collection of pairs from a Skolem sequence or hooked Skolem sequence of order k 1 for the set f1;2;:::;2k 2g or f1;2;:::;2k 1g, if k 1 0 or 1 (mod 4) or k 1 2 or 3 (mod 4) respectively. So each element in f1;2;:::;2k 2g or f1;2;:::;2k 1gnf2k 2goccurs in exactly one element of P for ? = 1. Then with ci = 8 >< >: (0;xi;xi yi;3k;5k + 1 +i) if ? = 1, (0;xi;xi yi;3k 1 +?=2;5k +?=2 +i) if ?2f4;6g, and (0;xi;xi yi;3k + 3;5k + 5 +i) if ? = 9, form the set of 5-cycles B = fci + j j 1 i b =5c;j 2 Zv;(xi;yi) 2Pg where computations are done modulo v. Tables 2.5, 2.6, and 2.7 list the di erences of the edges that occur in cycles in B when is as big as possible (that is, when is as small as possible). Edges Di erenceswhenk 1 0;1 (mod 4) Di erenceswhenk 1 2;3 (mod 4) f0;xig;fxi;xi yig 1;2;:::;2k 2 1;2;:::;2k 3;2k 1 fxi yi;3kg 3k+1;3k+2;:::;4k 1 3k+1;3k+2;:::;4k 1 f3k;5k+1+ig 2k+2;2k+3;:::;3k 2k+2;2k+3;:::;3k f5k+1+i;0g 5k 1;5k 2;:::;4k+1 5k 1;5k 2;:::;4k+1 Table 2.5: Di erences of edges in B when is as large as possible for ? = 1 and m = 1 Edges Di erenceswhenk 0;1 (mod4) Di erenceswhenk 2;3 (mod4) f0;xig;fxi;xi yig 1;2;:::;2k 1;2;:::;2k 1;2k+1 fxi yi;3k 1+?=2g 3k+?=2;3k+1+?=2;:::;4k 1+?=2 3k+?=2;3k+1+?=2;:::;4k 1+?=2 f3k 1+?=2;5k+?=2+ig 2k+2;2k+3;:::;3k+1 2k+2;2k+3;:::;3k+1 f5k+?=2+i;0g 5k 1+?=2;5k 2+?=2;:::;4k+?=2 5k 1+?=2;5k 2+?=2;:::;4k+?=2 Table 2.6: Di erences of edges in B when is as large as possible for ?2f4;6g and m = 1 Notice that by Lemma 2.2.3 we know that 3 divides ((v 1)=2 ) when v is odd and 3 divides ((v 1)=2 3=2) when v is even. Form a partition P0 of the di erences not used to form B into ((v 1)=2 )=3 sets (not multisets) of size 3 when v is odd and when v is even ((v 1)=2 3=2)=3 sets (not multisets) of size 3 and one set fd;v=2g of size 2 with d6= v=2. We form the set C of 5-cycles as in 20 Edges Di erenceswhenk 0;1 (mod 4) Di erenceswhenk 2;3 (mod 4) f0;xig;fxi;xi yig 1;2;:::;2k 1;2;:::;2k 1;2k+1 fxi yi;3k+3g 3k+4;3k+5;:::;4k+3 3k+4;3k+5;:::;4k+3 f3k+3;5k+5 +ig 2k+3;2k+4;:::;3k+2 2k+3;2k+4;:::;3k+2 f5k+5 +i;0g 5k+3;5k+2;:::;4k+4 5k+3;5k+2;:::;4k+4 Table 2.7: Di erences of edges in B when is as large as possible for ? = 9 and m = 1 Equation (2.4) when v is odd and as in Equation (2.3) when v is even. Notice that by Lemma 2.2.5 the elements of C are all 5-cycles. Thus (Zv[f1g;A[B[C) is a 5{CS(v + 1; + 1) for v 1 or 4 (mod 5). Now suppose m = 2 and = max(v;2). By Table 1.1: if v 1 (mod 5) then since v + 1 is ( + m)-admissible + m 0 (mod 10) and so 8 (mod 10); and if v 4 (mod 5) then v is -admissible so 0 (mod 10) (and so + m 2 (mod 10)). It follows that = v 1 3( + 2)=2 0 (mod 5). It also follows that for any xed values of v and m, v-admissible values of di er by multiples of 10, so (v;m)-admissible integers di er by multiples of 15 (by Lemma 2.2.2). So when = max(v;m) it follows from Lemma 2.2.4 that 2f0;5;10g. (There is no need to be more speci c for this proof, but the reader may be interested to know that when m = 2 and = max(v;2): = 0;5; or 10 if k 0;2; or 1 (mod 3) respectively when v 1 or 4 (mod 10); and = 0;5;10 if k 1;0; or 2 (mod 3) respectively when v 6 or 9 (mod 10).) De ne B = 8 >< >: ? if = 0, f(0;1;4;2;6) +jjj2Zvg if = 5, and f(0;1;4;2;6) +jjj2Zvg[f(0;1;4;2;6) +jjj2Zvg if = 10, and let = ?;f1;2;3;4;6g, or f1;1;2;2;3;3;4;4;6;6g when = 0;5; or 10 respec- tively. Using Lemma 2.2.3 we know that 3 divides v 1 = jD(v)2 n j if v is odd and jD(v) 2 n j if v is even. Form a partition P0 of D(v)2 n when v is odd and D(v) 2 n if v is even into (m(v 1)=2 )=3 sets of size 3. Form the set C of 5-cycles as in Equation (2.4). By Lemma 2.2.5 the elements of C are all 5-cycles. Thus (Zv[f1g;A[B[C) is a 5{CS(v + 1; + 2) with v 1 or 4 (mod 5) and = max(v;2). Now suppose m = 3 and = max(v;3) = (v 4). It follows that = 0 for all k. So de ne B = ?. Using Lemma 2.2.3 we know that 3(v 1)=2 0 (mod 3) when v is odd and 3(v 1)=2 3=2 0 (mod 3) when v is even, so we can form a partition P0 of the di erences in D(v)3 into (3(v 1)=2 )=3 sets of size 3 when v is odd and when v is even form a partition P0 of the di erences in D(v) 2[D(v) into (3(v 1)=2 3=2)=3 sets of size 3 and one set fd;v=2g of size 2 with d6= v=2; it is easy to ensure that each element of P0 does not contain the same element 3 times. De ne C as in Equation (2.4) when v is odd and as in Equation (2.3) when v is even. 21 By Lemma 2.2.5 the elements of C are cycles. Therefore (Zv[f1g;A[B[C) is a 5{CS(v + 1; + 3) for v 1 or 4 (mod 5), = max(v;3). Let v 1 (mod 10), m 2f2;3;:::;9g, and = 10 m. Let P = f(xi;yi) j 1 i k 1;yi > xig be the collection of pairs from a Skolem sequence or hooked Skolem sequence of order k 1 for the set f1;2;:::;2k 2g or f1;2;:::;2k 1g, if k 1 0 or 1 (mod 4) or k 1 2 or 3 (mod 4) respectively. So each element in f1;2;:::;2k 2gorf1;2;:::;2k 1gnf2k 2goccurs in exactly one element of P. Form the set of 5-cycles B0 =fci 1 = (0;xi;xi yi;3k;5k + 1 +i)j1 i k 1;(xi;yi)2Pg where computations are done modulo v. Let B00 = mB0. Then B00 contains m(k 1) 5-cycles, but we needb =5c= mk 3 of them. Hence for m 4 we need m 3 more 5-cycles. Let c01 = (0;2k + 1;6k + 1;k + 1;5k + 1) and c02 = (0;2k;4k;6k;8k). Also let E contain 1, 2, 3, 3, 4, and 4 copies of c01 if m = 4; 5, 6, 7 8, and 9 respectively and contain 1, 1, and 2 copies of c02 if m = 7; 8, and 9 respectively. Notice that the cycles in E contain at most m copies of edges of di erences not used in cycles in B00, namely the di erences 2k;2k+ 1;4k and 5k (B00 is also missing the di erences 2k 1 or 2k 2). Then B = ci +jj1 i b =5c;ci (mod k 1) 2B00;j2Zv [fc0i +jjj2Zv;c0i2E g: Notice that regardless of our choice of m, +m = 10. So (m(v 1)=2 ) = 15 which is divisible by 3. So we use the elements not used to form B to form a partition P0 of the di erences in D(v)m into ve sets of size 3. De ne C as in Equation (2.4) (it is easy to ensure d1 < d3 and d2 < v=2 so that by Lemma 2.2.5 the elements of C are all 5-cycles). Therefore (Zv[f1g;A[B[C) is a 5{CS(v + 1; + m) with m2f2;3;4;5;6;7;8;9g and +m = 10. Let v 6 (mod 10), m = 3 and = min(v;3) = 2. Let P = f(xi;yi) j 1 i k;yi > xig be the collection of pairs from a Skolem sequence or hooked Skolem sequence of order k for the set f1;2;:::;2kg or f1;2;:::;2k + 1g, if k 0 or 1 (mod 4) or k 2 or 3 (mod 4) respectively. So each element in f1;2;:::;2kg or f1;2;:::;2k+ 1gnf2kgoccurs in exactly one element of P. Then we form the set of 5-cycles B0 =f(0;xi;xi yi;3k + 2;5k + 3 +i)j1 i k;(xi;yi)2Pg where computations are done modulo v. Let B00 = mB0. Notice that b =5c = 3k = jB00j: So de ne B =fc+jjc2B00;j2Zvg: By Lemma 2.2.3 we know that m(v 1)=2 3=2 0 (mod 3). So we use the elements not used to form B to form a partition P0 into one set fd;v=2g of size 2 with d6= v=2 and two sets of size 3. De ne C as in Equation (2.4) (it is easy to ensure that d1 < d3 and d2 < v=2 so that by Lemma 2.2.5 the elements of C are all 5-cycles). Therefore (Zv[f1g;A[B[C) is a 5{CS(v + 1; + m) with v 6 (mod 10), m = 3, and = 2. 22 Corollary 2.2.10. Assume conditions (a-c) of Lemma 2.1.2 are satis ed. Let v 2 or 3 (mod 5). If m = 5, or m2f10;15g and = max(v;m), then any 5{CS of Kv can be enclosed in a 5{CS of ( +m)Kv+1. Let v6 2 or 3 (mod 5). If m = 1, m2f2;3g and = max(v;m), m = 3, = min(v;3) = 2, and v 6 (mod 10), or m2f2;3;:::;9g, +m = 10 and v 1 (mod 10), then any 5{CS of Kv can be enclosed in a 5{CS of ( +m)Kv+1. Proof. By Lemmas 2.2.6, 2.2.7, 2.2.8, and 2.2.9 the results follow. 2.3 The Main Theorem The following lemma will be used to guarantee an important point made in the main result. Lemma 2.3.1. If m 0 (mod 3) then max(v;m) = m(v 4)=3. Proof. Recall that max(v;m) is the largest integer satisfying conditions (a-c) of Lemma 2.1.2. By Lemma 2.1.2(c), max(v;m) bm(v 4)=3c = m(v 4)=3. So the result follows since clearly m(v 1)=3 +m(v 1) = 4m(v 1)=3 is even and mv(v 1)=2 +mv(v 1)=3 = 5mv(v 1)=6 is divisible by 5. In the following theorem, Corollary 2.2.10 is used as a basis for an inductive argument to prove our main result, settling the enclosing problem when u = 1. Theorem 2.3.2. Let m 1. A 5{CS of Kv can be enclosed in a 5{CS of ( + m)Kv+1 if and only if (a) +mv 0 (mod 2), (b) m v2 +v( +m) 0 (mod 5), and (c) m(v 1) 3( +m). 23 Proof. The necessity follows from Lemma 2.1.2, so we now prove the su ciency. Since we are assuming that a 5{CS of Kv exists, it follows by Theorem 1.2.2 that v 62f2;3;4g, and by condition (c) v 6= 1, so we know v 5. If = 0 then by condition (a) mv 0 (mod 2) and by condition (b) mv(v + 1) 0 (mod 5), so by Theorem 1.2.2 there exists a 5{CS of mKv+1. So we can assume that 1. Let (V;A) be a 5{CS of Kv. If v 2 or 3 (mod 5) then from Table 1.1 it follows that m 0 (mod 5); in any other case m can potentially take on any positive integral value. To re ect this situation, let t(v) = 1 if v 6 2 or 3 (mod 5) and let t(v) = 5 if v 2 or 3 (mod 5). We often simply write t instead of t(v) when the value of v is clear. Let max(v;m) be the second largest integer for satisfying conditions (a-c), and let +min(v;m) be the second smallest integer for satisfying conditions (a-c). We will rst establish that for any given v, the di erence between consecutive values of that satisfy conditions (a) and (b) is a constant; call this di erence di (v). Secondly, for all m 1 and v 5, we settle the enclosing problem for both the smallest and the largest values of satisfying conditions (a-c). Finally for all m 1 and v 5 it will be shown that for all satisfying conditions (a-c) there exist non-negative integers 1, 2 with 1 + 2 = and positive integers m1; m2 with m1 + m2 = m such that for 1 i 2 there exists a 5{CS of iKv that can be enclosed in a 5{CS of ( i +mi)Kv+1. So the union of these two enclosings completes the proof. We turn to the rst step of the proof. For any given v and m, the di erence between consecutive values of that satisfy conditions (a) and (b) is a constant; namely di (v;m). Also by conditions (a) and (b), di (v;m) 0 (mod 2) and v di (v;m) 0 (mod 5). Therefore v di (v;m) 0 (mod 10). Since di (v;m) must be the smallest such value, if v 0;5 (mod 10) then di (v;m) = 2, and if v6 0;5 (mod 10) then di (v;m) = 10. Notice that if m1 6= m2 then di (v;m1) = di (v;m2). Therefore we de ne di (v) = di (v;m). We now turn to the second step in the proof; establishing the existence of the enclosing for the smallest and largest values of given v and m. Beginning with the smallest value, Tables 2.8 and 2.9 list the values of min(v;m), and were formed using Theorem 1.2.2 and Corollary 2.2.10. Three cases are considered in turn based on the value of v. m v (mod 10) 0 1 2 3 4 5 6 7 8 9 1 0 9 8 7 6 5 4 3 2 1 6 0 4 8 2 6 0 4 8 2 6 Table 2.8: Checking min(v;m) when v 1 or 6 (mod 10): each cell contains min(v;m) 24 v (mod 10) m 0 2 3 4 5 7 8 9 odd 0 0 5 0 1 5 0 5 even 0 0 0 0 0 0 0 0 Table 2.9: Checking min(v;m) when v 6 1 or 6 (mod 10): each cell contains min(v;m) Let v 1 (mod 10). The proof is by induction on m. By Corollary 2.2.10 if m 10 then any 5{CS of min(v;m)Kv can be enclosed in a 5{CS of ( min(v;m) + m)Kv+1. Suppose that for some m 11 and for all s with 1 s < m, every 5{CS of min(v;s)Kv can be enclosed in a 5{CS of ( min(v;s) + s)Kv+1. Then, since m 11, by induction each 5{CS (V;B1) of min(v;m 10)Kv can be enclosed in a 5{CS (V [f1g;B01) of ( min(v;m 10) + (m 10))Kv+1 and there exists a 5{CS (V [f1g;B2) of 10Kv+1 (by Theorem 1.2.2). Since Table 2.8 shows that min(v;m 10) = min(v;m), (V;B1) is a 5{CS of min(v;m 10)Kv = min(v;m)Kv which is enclosed in a 5{CS (V [f1g;B01[B2) of (( min(v;m 10) + (m 10)) + 10)Kv+1 = ( min(v;m) +m)Kv+1: Let v 6 (mod 10). The proof is by induction on m. We rst settle the base cases where m 5. By Corollary 2.2.10, if m 2 f1;3g then any 5{CS of min(v;m)Kv can be enclosed in a 5{CS of ( min(v;m) + m)Kv+1. Hence a 5{CS of min(v;1)Kv can be enclosed in a 5{CS of ( min(v;1)+1)Kv+1. Since Table 2.8 shows min(v;1) + min(v;1) = 4 + 4 = min(v;2), the union of two copies of this enclosing proves that any 5{CS of min(v;2)Kv can be enclosed in a 5{CS of (( min(v;1) + 1) + ( min(v;1) + 1))Kv+1 = ( min(v;2) + 2)Kv+1. Similarly, since Table 2.8 shows that min(v;1) + min(v;3) = 4 + 2 = min(v;4), any 5{CS of min(v;4)Kv can be enclosed in a 5{CS of (( min(v;1) + 1) + ( min(v;3) + 3))Kv+1 = ( min(v;4) + 4)Kv+1. If m = 5, by Table 2.8 min(v;5) = 0, so this enclosing has been established. Now suppose that for some m 6 and for all s with 1 s 0 and u = 2. For the remainder of this chapter, let U =f11;12g be the vertex set of V(Kv+u)nV(Kv). Also for each pair of positive integers v and m, let max(v;m) and min(v;m) be the largest and smallest values of respectively for which conditions (a),(b) and (d) in Lemma 2.1.2 are satis ed when u = 2. One such tool that we use is the concatenation of trails T1;T2;:::;Tx in Gv(D) which we denote byQxi=1 Ti = T1T2 Tx. (For example we use the trail H1H2 formed by concatenating two Hamilton cycles in a component of Gv(fd1;d2g) obtained using Theorem 3.1.1.) Again, Lemma 2.2.1 is a critical result, being used hand in hand with the obser- vation that there exists a 5{CS of Gv(fv=5g) and of Gv(f2v=5g) when v 0 (mod 5), since each component is a 5-cycle. So when v 0 (mod 5) let (Zv; 1), (Zv; 2) and (Zv; 3) be a 5{CS of Gv(fv=5g);Gv(f2v=5g), and Gv(f1;2;3g) respectively. 28 For the remainder of this chapter, let a = +m; b = 2vd (v + 3)( +m)5 ; c = (3v 1)( +m) vd5 ; and d = 8 >>> < >>> : +m if +m 0 or i> 1 respectively as required by (vii). So for each i2 Zv, Ti(D;v=2) = Qd2Dn(xfv=2g) Pi(fv=2;dg) where the last trail in this concatenation is Pi(fv=2;d ig) (so (vi) is satis ed) is a closed trail satisfying Conditions (i-vii) and so fTi(D;v=2) ji2Zvg is a closed trail system of Gv(D) satisfying all of the listed conditions. In subsequent proofs, edges of di erence v=5 can be problematic when trying to avoid 3-cycles in the concatenation process, so the following lemma uses a di erence d at the end of the trail to separate edges of di erence v=5 from edges in the next trail. To this end, d cannot be 2v=5. Lemma 3.3.5. Let D be a multiset in which each element is v=5 except for a single element d 62 fv=2;v=3;v=5;2v=5g. For some integer w there exists a closed trail system fTi = Ti(D;v=5)ji2Zwg of Gv(D) such that for each i2Zw: (i) each set of 3 consecutive edges in Ti induces a path, (ii) the rst and second edges of Ti can be chosen to be either fi;i + v=5g and fi+v=5;i+ 2v=5g, or fi;i v=5g and fi v=5;i 2v=5g, 36 (iii) Ti ends on an edge of di erence d , (iv) Ti starts on vertex i, and (v) if gcd(fd ;v;v=5g) = 1 then E(Gv(fd ;v=5g)) E(T0(D;v=5)). Proof. Let D be a multiset in which each element is v=5 except for a single element d 62fv=2;v=3;v=5;2v=5g and let k = (v=5)=gcd(fv=5;d g). Let Pi(fv=5g) be the Euler tour of one component of Gv((jDj 1)fv=5g) chosen to meet condition (ii) (use edges of di erence ( 1)jv=5 for the appropriate j2Z2 to form the trail). The edges of di erence d can be used to connect these tours as follows. If i < gcd(fv=5;d g) then let Ti = Y j2Zk Pjd +i(fv=5g)(jd +i;(j + 1)d +i) ! (kd +i;(k+1)d +i;:::; d +i;i): Then fTi = Ti(D;v=5) ji2Zwg is a closed trail system of Gv(D) satisfying Condi- tions (i-iv). Notice that this implies that if gcd(fd ;v=5g) = 1 then Gv(fd ;v=5g) is a single component, so E(Gv(fd;v=5g)) E(T0(D;v=5))). Each of the Lemmas 3.3.1 to 3.3.5 extend the de nition of Ti so that if i2ZvnZw then de ne Ti = ?. This will be important because trails formed using di erent lemmas will be concatenated, but the value of w may change from lemma to lemma. Lemma 3.3.6. Let the following trails be of those described in Lemmas 3.3.1, 3.3.2, 3.3.3, 3.3.4, and 3.3.5 with multisets D1;D2;D3;D4 and D5 respectively are the mul- tisets satisfying the respective conditions. Then in each case by judicious use of the choice available (as described in each lemma) for the rst two edges of the second com- ponent trail, the following trails can be constructed so that each set of 3 consecutive edges induces a path: (i) Ti((jD1j=2)fv=2;v=3g)Ti((jD2j=2)fv=3;v=6g), (ii) Ti((jD1j=2)fv=2;v=3g)Ti(D3;v=3), (iii) Ti((jD1j=2)fv=2;v=3g)Ti(D4;v=2), (iv) Ti((jD1j=2)fv=2;v=3g)Ti(D5;v=5), (v) Ti((jD1j=2)fv=2;v=3g)Ti(fdg) where d62fv=2;v=3;v=6g, (vi) Ti((jD2j=2)fv=3;v=6g)Ti(D3;v=3), (vii) Ti((jD2j=2)fv=3;v=6g)Ti(D4;v=2), (viii) Ti((jD2j=2)fv=3;v=6g)Ti(D5;v=5), (ix) Ti((jD2j=2)fv=3;v=6g)Ti(fdg) where d62fv=3;v=2g, (x) Ti(D3;v=3)Ti(D4;v=2), (xi) Ti(D3;v=3)Ti(D5;v=5), (xii) Ti(D3;v=3)Ti(fdg) where d62fv=2;v=3;v=6g, (xiii) Ti(D4;v=2)Ti(D5;v=5), (xiv) Ti(D4;v=2)Ti(fdg) where d62fv=2;v=3g, (xv) Ti(D5;v=5)Ti(fdg) where d62fv=2;v=3g, and 37 (xvi) Ti(fdg)Ti(fd0g) where d;d062fv=2;v=3;v=5g. Proof. Let D1;D2;D3;D4; and D5 be multisets de ned as D is in Lemmas 3.3.1, 3.3.2, 3.3.3, 3.3.4, and 3.3.5 respectively. Then by Lemmas 3.3.1, 3.3.2, 3.3.3, 3.3.4, and 3.3.5, let Ti(jD1j=2fv=2;v=3g), Ti(jD2j=2fv=3;v=6g), Ti(D3;v=3), Ti(D4;v=2), and Ti(D5;v=5) respectively be the closed trails that satisfy the conditions outlined in the lemmas. Since in each case d;d062fv=3;v=2g, each set of 3 consecutive edges in Ti(fdg) and in Ti(fd0g) induces a path. Therefore, in each case it remains to show that the choices permitted in how the trails start and end described in the lemmas can be exploited to ensure that as two trails are concatenated, the last 1 or 2 of the edges from the rst closed trail followed by the rst 2 or 1 edges from the second closed trail respectively induce a path. Suppose the rst of the two closed trails to be concatenated isTi(jD1j=2fv=2;v=3g). By Lemma 3.3.1, the last edge of Ti(jD1j=2fv=2;v=3g) is an edge of di erence v=2, and the second to last edge of Ti(jD1j=2fv=2;v=3g) is an edge of di erence v=3. Choose the rst and second edge of the following trail as indicated: choose the rst and second edge of Ti(jD2j=2fv=3;v=6g) to be fi;i + v=6g and fi+v=6;i+v=6 v=3gorfi;i v=6gandfi v=6;i v=6 +v=3grespectively; choose the rst and second edge of Ti(D3;v=3) to befi;i v=3gandfi v=3;i v=3 d3gorfi;i+v=3gandfi+v=3;i+v=3 +d3grespectively where d3 2D3; choose the rst and second edge of Ti(D4;v=2) to befi;i+v=2gandfi+v=2;i+ v=2 +d4gorfi;i+v=2gandfi+v=2;i+v=2 d4grespectively where d4 2D4; choose the rst and second edge of Ti(D5;v=5) to befi;i+v=5gandfi+v=5;i+ 2v=5g or fi;i v=5g and fi v=5;i 2v=5g respectively; and choose the rst and second edge of Ti(fdg) to be fi;i + dg and fi + d;i + 2dg respectively (since d62fv=2;v=3;v=6g). This settles Conditions (i-v). Now suppose the rst closed trail is Ti(jD2j=2fv=3;v=6g). By Lemma 3.3.2, the last two edges of Ti(jD2j=2fv=3;v=6g) are edges of di erence v=3. The rst vertex in the second trail is of course vertex i, so it remains to ensure that the second and third vertices in the second trail avoid v=3 and 2v=3 respectively, or avoid 2v=3 and v=3 respectively, depending on whether the last edge of Ti(jD1j=2fv=2;v=3g) isfi;i+v=3g or fi;i + 2v=3g. In Case (vi) this is accomplished by Lemma 3.3.3(ii), noting that v=662D3. This settles conditions (vi-ix). If Ti(D3;v=3) is the rst closed trail then since the last two edges of Ti(D3;v=3) are both edges of di erence v=3, it follows that each set of 3 consecutive edges in Ti(D3;v=3)Ti(D4;v=2), Ti(D3;v=3)Ti(D5;v=5), and Ti(D3;v=3)Ti(fdg) (since d62 fv=2;v=3;v=6g) induces a path. Suppose the rst closed trail is Ti(D4;v=2). Since one of the last two edges of the closed trail Ti(D4;v=2) is an edge of di erence v=2 and we have a choice of the rst two edges of the closed trail Ti(D5;v=5), it follows that each set of 3 consecutive edges in the closed trail Ti(D4;v=2)Ti(D5;v=5) induces a path. Since d62fv=2;v=3g, 38 we can choose the rst two edges of T(fdg) to be either fi;i + dg and fi;i + 2dg or fi;i dgandfi;i 2dgrespectively so that each set of 3 consecutive edges in either Ti(D4;v=2)Ti((d)) induces a path. If the rst closed trail isTi(D5;v=5) then sinced 2D5 withd 62fv=2;v=3;v=5;2v=5g and d62fv=2;v=3;v=5g, it follows that we can choose the rst two edges of Ti(fdg) so that each set of 3 consecutive edges in the closed trail Ti(D5;v=5)Ti(fdg) induces a path. Finally, we can choose the rst two edges of Ti(fd0g) so that each set of 3 con- secutive edges in the closed trail Ti(fdg)Ti(fd0g) induces a path. For the multiset D, let mD(d) be the number of times d appears in D. Note that we use the convention Gv(fdg) = Gv(d) to simplify notation. Lemma 3.3.7. Let v> 3 be a positive integer. Let D be a multiset, each element of which is in f1;2;:::;bv=2cg. Suppose that the following conditions hold: (A) D contains a di erence d1 = ( 1 if v6 5 (mod 10) and 4 otherwise and another di erence d2 62fv=2;v=3;v=4;v=5;2v=5g (possibly d2 is a second copy of d1 in D); (B) 2mD(v=2) + mD(v=4) + jDnfd1gj, where = 1 if fv=2;v=3;v=6g Dn fd1;d2g, mD(v=2) mD(v=3), and mD(v=6) >mD(v=2) min(fmD(v=2);mD(v=3)g) and = 0 otherwise; and (C) 2mD(v=3) +mD(2v=5) jDnfd1gj. Then there exists a closed trail of Gv(D) in which each set of 3 consecutive edges induces a path. Proof. To form the required trail decomposition of Gv(D), we begin by partitioning D into the 7 sets D1;D2;:::;D6, and fd1g de ned as follows. D will actually be partitioned in two di erent ways, depending on the occurrences of the di erences v=2, v=3, and v=6 in D (as will be seen, this actually relates to whether or not a single copy of the di erence v=3 needs to be set aside so as to be paired with a single copy of the di erence v=6). First, suppose that fv=2;v=3;v=6g Dnfd1;d2g, mD(v=2) mD(v=3), (3.2) and mD(v=6) >mD(v=2) min(fmD(v=2);mD(v=3)g); so in Condition (B), = 1. Let D1 consist of z1 = mD(v=3) 1 copies of both v=2 and v=3. Let D4 contain mD(v=2) z1 copies of v=2 and mD(v=2) z1 di erences in 4 = Dn(D1[(mD(v=2) z1)fv=2g[mD(v=4)fv=4g[fd1;v=3g); choose these di erences 39 in D4 so that d2 2D4 only if D1 [D4 contains all of the di erences in D besides mD(v=4)fv=4g[fd1;v=3g(i.e. only ifjD1j+jD4j=jDn(mD(v=4)fv=4g[fd1;v=3g)j). Notice that D1[D4 contains z1 +mD(v=2) z1 = mD(v=2) copies of v=2 (that is, all the copies of v=2 in D). Also notice that by Condition (B) it follows that j 4j=jDnfd1gj mD(v=2) z1 mD(v=4) 1 2mD(v=2) +mD(v=4) + 1 mD(v=2) z1 mD(v=4) 1 = mD(v=2) z1 0 so 4 is large enough for D4 to be well de ned. Let D2 contain 1 copy of both v=6 and v=3. Notice that D1[D2 contains all copies of v=3 in D. If 2v=52Dn(D1[D2[D4) then let D5 contain mDn(D1[D2[D4)(v=5) copies of v=5 and a single copy of d2 and otherwise, let D5 = ?. Let D6 contain all of the remaining di erences in D (i.e. D6 = Dn(D1[D2[D4[D5[fd1g)). Second, suppose that fv=2;v=3;v=6g6 Dnfd1;d2g, mD(v=2) mdnD4(v=6), and by Condition (C) j 3j= ( jDnfd1gj mD(v=2) mD(v=3) mD(v=6) mD(2v=5) if D3 6= ?, 0 if D3 = ? ( 2mD(v=3) +mD(2v=5) mD(v=2) mD(v=3) mD(v=6) mD(2v=5) if D3 6= ?, 0 if D3 = ? = ( mD(v=3) mD(v=2) mD(v=6) if D3 6= ?, 0 if D3 = ? = ( mD(v=3) min(fmD(v=2);mD(v=3)g) min(fmD(v=3) z2;mD(v=6) if D3 6= ?, 0 if D3 = ? = ( mD(v=3) z2 min(fmD(v=3) z2;mD(v=6) if D3 6= ?, 0 if D3 = ?. Then there are enough di erences in Dn(D1[D2[D4) to construct D3 as described. If 2v=52Dn(D1[D2[D3[D4) then let D5 contain mDn(D1[D2[D3[D4)(v=5) copies of v=5 and a single copy of d2 and otherwise, let D5 = ?. Let D6 contain all of the remaining di erences, i.e. D6 = Dn(D1[D2[D3[D4[D5[fd1g). Form a sequence S = (s1;s2;:::;sjD6j+5), the elements of which form a partition of Dnfd1gwhere sk = Dk for k2f1;2;3;4;5gand s6;s7;:::;sjD6j+5 are sets of size 1 such that SjD6j+5k=6 sk = D6; by choosing the copies of the di erence 2 in D6 to appear as early as possible in this ordering, we can assume that if sjD6j+5 =f2g then D6 =jD6jf2g. (3.7) Then by Lemmas 3.3.1-3.3.5 for eachi2Zv we can form closed trailsTi(jD1j=2fv=2;v=3g), Ti(jD2j=2fv=3;v=6g), Ti(D3;v=3), Ti(D4;v=2), and Ti(D5;v=5) respectively in each of which every set of 3 consecutive edges induces a path. Let d3, d4, and d5 be v=3, v=2, and v=5 respectively. So for each i2Zv de ne the concatenation i = Ti(jD1j=2fv=2;v=3g)Ti(jD2j=2fv=3;v=6g) 5Y k=3 Ti(Dk;dk) !0 @ jD6j+5Y k=6 Ti(sk) 1 A 41 of these trails. Note that some of the trails being concatenated may be empty. It will be important later to note that if d2Dnfd1g and gcd(fd;vg) = 1 then E(Gv(fdg)) 0; (3.8) this follows by applying Condition (v) of Lemmas 3.3.3{3.3.5 to Ti(Dk;dk) for k = 3, 4, and 5 respectively, and the fact that Gv(fdg) is connected (so Ti(fdg) is empty if i> 0). To check that i has the property that no 3 consecutive edges form a cycle of length 2 or 3 consider the following. So the concatenation of each pair of trails making up i must be considered, but this is done in Lemma 3.3.6 in all cases except one. The one case not considered is when Ti(jD1j=2fv=2;v=3g) is followed in the concatenation by Ti(fv=6g) (this could happen if Dk = ? for 2 k 5). If this case did occur, a 3- cycle would necessarily be formed by 3 consecutive edges (such as (i+v=3;i;i+v=6;i+ v=3)), but by (3.4), (3.5), and (3.8) the concatenation Ti(jD1j=2fv=2;v=3g)Ti(fv=6g) will never occur in i. If we are in Case B then this is clearly so since by (3.5) one of the trails Ti(jD1j=2fv=2;v=2g) or Ti(fv=6g) is empty. Otherwise, since the value of w is the same in Lemmas 3.3.1 and 3.3.2, if Ti(jD1j=2fv=2;v=3g) 6= ? then Ti(jD2j=2fv=3;v=6g) 6= ?. If v=6 2 Dn(D1 [D4) then since D2 6= ? (by (3.6) if we are in Case A), the concatenation of Ti(jD1j=2fv=2;v=3g)Ti(fv=6g) will never occur in i under the set of assumptions in (3.2), nor under the set of assump- tions in (3.3). In other words, in such a situation i is formed by rst concatenat- ing Ti(jD1j=2fv=2;v=3g) with Ti(jD2j=2fv=3;v=6g) which is then concatenated with Ti(fv=6g). Thus by Lemma 3.3.6 every set of 3 consecutive edges in i induces a path. It is critical to note that for all i 1 we still have the choice available (as de- scribed in Lemmas 3.3.4 to 3.3.5) for the rst two edges in the rst component trail in i. The nal step in forming the required closed trail is to use the edges in Gv(fd1g) to connect the trails i, i2Zv. In so doing, we need to make sure that we maintain the property that every set of 3 consecutive edges induces a path. To do so, it turns out that even more exibility is required since 0 and d1 may need to be replaced with the reverse trails 0 and d1 respectively de ned formally in the next paragraph. This choice is only needed for 0 and d1 and not for i if i62f0;d1g; 0 is unusual because from (3.8), if there is an edge of di erence d where gcd(fd;vg) = 1, then this edge could only be found in 0. Let fi;i + fi;1g and fi + fi;1;i + fi;1 + fi;2g be the rst and second edges of i respectively. Similarly, letfi fi; 1 fi; 2;i fi; 1gandfi fi; 1;igbe the second- to-last and last edges of i respectively. Let i denote the closed trail formed by mapping each edge fj1;j2g in the closed trail i to the edge f j1 + 2i; j2 + 2ig in i . (Informally, i is formed from i by also starting at vertex i but proceeding in the reverse direction around the v vertices.) So clearly i has the property that each set of 3 consecutive edges induces a path. 42 We are now ready to de ne the required trail . If d1 2f f0; 1; (f0; 1 +f0; 2)g, or (Pi) if both f0; 1 = 2d1 and d1 = ? (Pii) (i.e. d1 is one of the second-to-last or third-to-last vertices in 0 or 2d1 is the second- to-last vertex in 0), then begin with 0 = 0 and otherwise begin with 0 = 0. (Piii) Extend the trail by concatenating 0 with the trail (0;d1) of length 1. Recursively de ne i for all i 1 as follows: For all i+d1 0 if i+d1 6= ?, i 6= ?, and d1 +fi+d1;1 2f0; f i; 1g (Piv) where fi;i f i; 1g is the last edge of i then i+d1 = i+d1 and otherwise i+d1 = i+d1. For all i2Zv let fi;i + f i;1g, fi + f i;1;i+f i;1 +f i;2g, fi f i; 1 f i; 2;i f i; 1g, and fi f i; 1;ig be the rst, second, second-to-last, and last edges of i . Then de ne = v 1Y i=0 id1(id1;(i+ 1)d1) : It now requires some e ort to show that all sets of 3 consecutive edges that contain the edge fid1;(i+ 1)d1g induce a path, especially in the case when i = 0. If 0(0;d1) contains 3 consecutive edges that form a cycle then d1 must be one of the last 3 vertices of 0, so d1 2f0; f0; 1; (f0; 1 + f0; 2)g, in which case 0 = 0 since clearly d1 6= 0. To see that not both 0(0;d1) and 0 (0;d1) can contain 3 consecutive edges that form a cycle, suppose that d1 2f f0; 1; (f0; 1 + f0; 2)g\ ff0; 1;f0; 1+f0; 2g. First note that if d1 = (f0; 1+f0; 2) then d1 6= f0; 1+f0; 2 and so d1 = f0; 1. Similarly if d1 = f0; 1 then d1 = f0; 1 +f0; 2. Therefore in either case the last two edges of 0 and 0 have di erence d1 and 2d1. But by Lemmas 3.3.1{3.3.5 the last two edges of 0 are either both edges of the same di erence or one of the two edges has di erence v=5 or v=2. Since d1 62fv=2;v=5g, it is impossible for both 0 and 0 to have the vertex d1 in the last three vertices of either trail. So 0 has been chosen such that every 3 consecutive edges in 0 (0;d1) induces a path. To see that 0 (0;d1) d1 when d1 6= ? does not contain 3 consecutive edges that form a cycle, consider the following. First note that since gcd(fd1;vg) = 1 by Condition (A), if d = d1 and d 2 Dnfd1g (that is, d is another copy of d1 in D) then E(Gv(fdg)) E( 0 ), so neither the second vertex of d1 nor the second vertex of d1 equal 0 (the last vertex of 0 ). Second, note that if Td1(D4;v=2) is the rst trail in d1 then by Lemma 3.3.4(ii), the preamble in Lemma 3.3.6, and since mD(v=2)fv=2g D1[D4, we can choose the rst edge of Td1(D4;v=2) to not have di erence v=2. Therefore if d1 +fd1;1 = f 0; 1 (so d1 = d1) then d1 fd1;1 6= f 0; 1 43 (for otherwise subtracting this equality from the rst implies that 2fd1;1 = 0, so fd1;1 = v=2), so the second vertex of d1 is not f 0; 1. To nish showing that each set of 3 consecutive edges in 0 (0;d1) d1 induces a path, we must show that the third vertex of d1, namely d1 + f d1;1 + f d1;2, is not v. Since d1 > 0, we need only show that the third vertex of d1, namely d1 + f d1;1 + f d1;2, is not 0. This requires considering several cases, most of which rely on the claim that gcd(ff d1;1;f d1;2;vg) 6= 1 (later we will show that if f d1;1 6= f d1;2 then gcd(ff d1;1;f d1;2g)6= 1). If f d1;1 = f d1;2 (that is, the rst two edges of d1 have the same di erence) then d1 +f d1;1 +f d1;2 6= 0, for otherwise d1 = v f d1;1 f d1;2 = v 2f d1;1 contradicting the facts that gcd(fv;f d1g) 6= 1 (by (3.8)), and gcd(fv;d1g) = 1 (by Condition (A)). So we can assume that the rst two edges of d1 have di erent di erences: f d1;1 6= f d1;2. Then the rst trail in d1 cannot be Td1(fdg) for any di erence d2D6 and cannot be Td1(D5;v=5) by Lemma 3.3.5 (since in such cases the rst two edges have the same di erences). So the rst trail in d1 must be one of the following: Td1(jD1j=2fv=2;v=3g), Td1(jD2j=2fv=3;v=6g), Td1(D3;v=3), or Td1(D4;v=2). If the rst trail of d1 is Td1(D3;v=3) or Td1(D4;v=2) then d1 + f d1;1 + f d1;2 6= 0 since otherwise gcd(fv;d1g) = 1 would mean that gcd(ff d1;1;f d1;2g) = 1 which contradicts Lemma 3.3.3(v) or 3.3.4(v) respectively (since then gcd(fd;d0;vg) = 1 where d0 = v=3 or v=2 respectively and ff d1;1;f d1;2g = fd;d0g, so these edges would be in 0 instead of d1). If the rst trail of d1 is Td1(jD1j=2fv=2;v=3g) or Td1(jD2j=2fv=3;v=6g) then d1 + f d1;1 + f d1;2 6= 0 since otherwise by the descriptions of the rst two edges of the trails constructed in Lemmas 3.3.1 and 3.3.2, d1 = v=6 so by Condition (A), v = 6, and so these edges would be in 0 instead of in d1. So each set of 3 consecutive edges in 0 (0;d1) d1 induce a path. It remains to show that in each of the following trails T every set of 3 consecutive edges induces a path: if i 0 then T = (i;i+d1;i+ 2d1;i+ 3d1); if i> 0, i+d1 6= ?, and i 6= ? then T = i (i;i+d1) i+d1; if i 0, i+d1 = ?, and i+2d1 6= ? then T = (i;i + d1;i + 2d1) i+2d1 (by (A) and the de nition of this only happens if d1 = 4, so v 5 (mod 10)); and if i 0, i 6= ?, i+d1 = ? then T = i (i;i+d1;i+ 2d1). We consider each of the four remaining cases in turn. First since v> 3, it is clear that (i;i+d1;i+ 2d1;i+ 3d1) is a path. Second suppose that i> 0, i+d1 6= ?, and i 6= ?. We only need to consider the sets of 3 consecutive edges in i (i;i + d1) i+d1 which contain fi;i + d1g. So we need to show that: (a) i+d1 6= i f i; 1, (b) i6= i+d1 +f i+d1;1, (c) i+d1 6= i f i; 1 f i; 2, (d) i f i; 1 6= i + d1 + f i+d1;1, and (e) i 6= i + d1 + f i+d1;1 + f i+d1;2. By (3.8) and since i > 0, i + d1 6= i f i; 1 and i 6= i + d1 + f i+d1;1, so (a) and (b) are true. To see (d), rst we use the exibility in the component trails (see preamble of Lemma 3.3.6) to ensure that i+d1 does not begin with an edge of di erence v=2. This follows by condition (ii) in Lemmas 3.3.4 and 3.3.5, opting to choose the rst edge in Ti+d1(D4;v=2) to not have di erence v=2 if it is the rst trail in i+d1. Therefore 44 by (Piv), if i f i; 1 = i+d1 +fi+d1;1 then i+d1 = i+d1 so i f i; 1 6= i+d1 fi+d1;1 (for otherwise subtracting this equality from the rst implies that 2fi+d1;1 = 0, so fi+d1;1 = v=2). Similarly by (Piv), if i f i; 1 = i + d1 fi+d1;1 then i+d1 = i+d1 so i f i; 1 6= i + d1 + fi+d1;1. So (d) is true regardless of which of the two values, fi+d1;1, f i+d1;1 takes on. We now turn to showing (c) is true. If f i; 1 = f i; 2 then i + d1 6= i f i; 1 f i; 2 for otherwise d1 = f i; 1 f i; 2 contradicting that gcd(fv;f i; 1g)6= 1 (by (3.8)) and gcd(fv;d1g) = 1 (by (A)). So we can assume that f i; 1 6= f i; 2. Notice that the last trail in i cannot be Ti(fdg) for any di erence d2D6 and cannot be Ti(jD2j=2fv=3;v=6g) or Ti(D3;v=3) by Lemmas 3.3.2 and 3.3.3 (since in such cases the last two edges have the same di erence). So the last trail in i must be one of the following: Ti(jD1j=2fv=2;v=3g), Ti(D4;v=2), or Ti(D5;v=5). If the last trail of i is Ti(D4;v=2) or Ti(D5;v=5) then i + d1 6= i f i; 1 f i; 2 since otherwise gcd(fv;d1g) = 1 would mean that gcd(fv;f i; 1;f i; 2g) = 1 which contradicts Lemma 3.3.4(v) or Lemma 3.3.5(v) respectively since i > 0. If the last trail of i is Ti(jD1j=2fv=2;v=3g) then i+d1 6= i f i; 1 f i; 2 since otherwise d1 = v=6 since f i; 1 + f i; 2 2fv=2 v=3g which implies v = 6 by Condition (A) and so these edges would be in 0 instead of i . This shows that (c) is true. Lastly, we focus on showing (e) is true. Since i+d1 > 0, we need only show that the third vertex of i+d1, namely i+d1 +f i+d1;1 +f i+d1;2, is not i. This requires considering several cases, most of which rely on the claim that gcd(ff i+d1;1;f i+d1;2;vg) 6= 1 (later we will show that if f i+d1;1 6= f i+d1;2 then gcd(ff i+d1;1;f i+d1;2g) 6= 1). If f i+d1;1 = f i+d1;2 (that is, the rst two edges of i+d1 have the same di erence) then i+d1 +f i+d1;1 +f i+d1;2 6= i, for otherwise i+d1 = i+v f i+d1;1 f i+d1;2 = i+v 2f i+d1;1 contradicting the facts that gcd(fv;f i+d1g) 6= 1 (by (3.8)), and gcd(fv;d1g) = 1 (by Condition (A)). So we can assume that the rst two edges of i+d1 have di erent di erences: f i+d1;1 6= f i+d1;2. Then the rst trail in i+d1 cannot be Ti+d1(fdg) for any di erence d 2 D6 and cannot be Ti+d1(D5;v=5) by Lemma 3.3.5 (since in such cases the rst two edges have the same di erences). So the rst trail in i+d1 must be one of the following: Ti+d1(jD1j=2fv=2;v=3g), Ti+d1(jD2j=2fv=3;v=6g), Ti+d1(D3;v=3), or Ti+d1(D4;v=2). If the rst trail of i+d1 is Ti+d1(D3;v=3) or Ti+d1(D4;v=2) then i+d1+f i+d1;1+f i+d1;2 6= i since otherwise gcd(fv;d1g) = 1 would mean that gcd(ff i+d1;1;f i+d1;2g) = 1 which contradicts Lemma 3.3.3(v) or 3.3.4(v) respectively (since then gcd(fd;d0;vg) = 1 where d0 = v=3 or v=2 respectively and ff i+d1;1;f i+d1;2g = fd;d0g, so these edges would be in 0 instead of i+d1). If the rst trail of i+d1 is Ti+d1(jD1j=2fv=2;v=3g) or Ti+d1(jD2j=2fv=3;v=6g) then i + d1 + f i+d1;1 + f i+d1;2 6= i since otherwise by the descriptions of the rst two edges of the trails constructed in Lemmas 3.3.1 and 3.3.2, d1 = v=6 so by Condition (A), v = 6, and so these edges would be in 0 instead of in i+d1. So each set of 3 consecutive edges in (i;i + d1) i+d1 and 0 (0;d1) d1 induce a path. So every set of 3 consecutive edges in i (i;i + d1) i+d1 induces a path when i> 0. Third, suppose that i 0, i+d1 = ?, and i+2d1 6= ?, so v 5 (mod 10). We will show that (i;i + d1;i + 2d1;i + 2d1 + f i+2d1;1) is a path; that is we show that i 6= i + 2d1 + f i+2d1;1. This follows since d1 = 4 and v 5 (mod 10), so 45 gcd(f2d1;vg) = 1 and by (3.8), gcd(ffi+2d1;1;vg)6= 1 since i+ 2d1 > 0. Finally, suppose that i 0, i 6= ?, and i+d1 = ?. We consider the sets of 3 consecutive edges in i (i;i + d1;i + 2d1) that contain the edge fi;i + d1g. We will break this into 2 cases: v 5 (mod 10) and v6 5 (mod 10). Case 1: Suppose v 5 (mod 10); then d1 = 4. We need to show that i + 4 6= i (f i; 1 +f i; 2), i f i; 1 6= i+ 4, and i f i; 1 6= i+ 8. By (3.8) and since v is odd, if f i; 1 = 4 or 8 then i = 0. By (Pi), if f0; 1 = 4 then 0 = 0 so f 0; 1 = 4, and if f0; 1 = 4 then 0 = 0 so f 0; 1 = 4; so in any case f 0; 1 6= 4 (since v 6= 8). Similarly, by (Pii), if f0; 1 = 8 then 0 = 0 so f 0; 1 = 8, and if f0; 1 = 8 then 0 = 0 so f 0; 1 = 8; so in any case f 0; 1 6= 8 (since v6= 16). If f i; 1 f i; 2 = 4 and the last two edges of i have the same di erence, then since v is odd this di erence is 2, so by (3.8), i = 0. So by (Pi), if f0; 1 f0; 2 = 4 and the last two edges of i have the same di erence then 0 = 0 so f 0; 1 f 0; 2 = 4, and if f0; 1 f0; 2 = 4 and the last two edges of i have the same di erence then 0 = 0 so f 0; 1 f 0; 2 = 4. Therefore in any case f 0; 1 f 0; 2 6= 4. If f i; 1 f i; 2 = 4 and the last two edges of i have di erent di erences then since v is odd, the last trail in i must be Ti(D5;v=5) (see Lemmas 3.3.1-3.3.5). But then by the de nition of D5, since D5 6= ?, it follows that 2v=5 2D6, which contradicts Ti(D5;v=5) being the last trail in i (since the number of components in Gv(D5) is at most the number of components in Gv(f2v=5g), so Ti(D5;v=5) 6= ? implies Ti(D6)6= ?). Thus each set of 3 consecutive edges in i (i;i+ 4;i+ 8) induces a path. Case 2: Suppose v6 5 (mod 10); then d1 = 1. We need to show that i f i; 1 f i; 2 6= i + 1, i f i; 1 6= i + 1, and i f i; 1 6= i + 2; this is done by contradiction. First suppose that either f i; 1 = 1 or f i; 1 = 2 and v is odd; so by (3.8) it follows that i = 0. Then by (Pi), if f0; 1 = 1 then 0 = 0 so f 0; 1 = 1, and by (Piii) if f0; 1 = 1 then 0 = 0 so f 0; 1 = 1; so in any case f 0; 1 6= 1. Similarly, by (Pii), if f0; 1 = 2 then 0 = 0 so f 0; 1 = 2, and by (Piii) if f0; 1 = 2 then 0 = 0 so f 0; 1 = 2; so in any case f 0; 1 6= 2. Next suppose that f i; 1 f i; 2 = 1 and the last two edges of i have the same di erence. Then v is odd and this di erence is (v 1)=2, so by (3.8) and since gcd(f(v 1)=2;vg) = 1, i = 0. By (Pi), if f0; 1 f0; 2 = 1 and the last two edges of i have the same di erence then 0 = 0 so f 0; 1 f 0; 2 = 1, and by (Piii) if f0; 1 f0; 2 = 1 and the last two edges of i have the same di erence then 0 = 0 so f 0; 1 f 0; 2 = 1; so in any case f 0; 1 f 0; 2 6= 1. Now suppose that f i; 1 f i; 2 = 1 and the last two edges of i have a di erent di erence. Then by Lemmas 3.3.1-3.3.5, the last trail in i must be one of the following trails: Ti(jD1j=2fv=2;v=3g), Ti(D4;v=2), or Ti(D5;v=5). As described at the end of Case 1, Ti(D5;v=5) cannot be the last trail in i (since 2v=562D6, so D5 = ?, eliminating this case). If Ti(jD1j=2fv=2;v=3g) is the last trail in i then f i; 1 f i; 2 6= 1 since otherwiseff i; 1;f i; 2g=fv=2; v=3gand so v = 6 and i = 0, and thus by (Pi) we reach a contradiction (since if f0; 1 f0; 2 = 1 or 1 then 0 = 0 or 0 respectively and so in any case f 0; 1 f 0; 2 = 1). If Ti(D4;v=2) is the last trail in i , then f i; 1 f i; 2 6= 1 since otherwise ff i; 1;f i; 2g=fv=2;dg where d2D4nmD4(v=2)fv=2gand gcd(fd;v=2;vg) = 1, so i = 0 and thus by (Pi) we 46 reach a contradiction (since if f 0; 1 f 0; 2 = 1 or 1 then 0 = 0 or 0 respectively and so f 0; 1 f 0; 2 = 1). Finally suppose that f i; 1 = 2 and v is even. The last trail in i must be one of the following: Ti(jD1j=2fv=2;v=3g), Ti(jD2j=2fv=3;v=6g), Ti(D3;v=3), Ti(D4;v=2), Ti(D5;v=5), and Ti(f2g). If Ti(jD2j=2fv=3;v=6g) or Ti(D3;v=3) is the last trail in i then by Lemma 3.3.2 or 3.3.3 respectively, the last edge has di erence v=3 = 2, so v = 6 and i = 0, and thus by (Pii) and (Piii) we reach a contradiction (since if f0; 1 = 2 or 2 then 0 = 0 or 0 respectively and so in any case f 0; 1 6= 2). Similarly, if Ti(jD1j=2fv=2;v=3g) is the last trail in i then by Lemma 3.3.1(ii), f i; 1 = v=2 = 2 and so v = 4, thus v=3 62 D, a contradiction. As previously described, if Ti(D5;v=5) is the last trail in i then 2v=562D6, so D5 = ?, eliminating this case. We now address when the last trail of i is Ti(f2g) or Ti(D4;v=2), still assuming that f i; 1 = 2 (so the last edge of i has di erence 2) and v is even. By (3.8) and Lemma 3.3.4(vii) respectively, it follows that i 1 (to apply Lemma 3.3.4(vii) note that gcd(fv;v=2;2g) 2f1;2g). Suppose Ti(D4;v=2) is the last trail in i and i = 0. Then by (Pii), if f0; 1 = 2 then 0 = 0 so f 0; 1 = 2 and by (Piii) if f0; 1 = 2 then 0 = 0 so f 0; 1 = 2; in any case f 0; 1 6= 2. If Ti(f2g) is the last trail in i then i = 1 (to see that i6= 0, note that if i = 0 then since v is even i+1 would contain edges of di erence 2 thus contradicting i+1 = ?). So in all cases we can now assume that i = 1. If T1(f2g) is the last trail in 1 , then by (3.7), mD6(2)f2g= D6. Furthermore, if T1(D4;v=2) is the last trail in 1 and if D4 contains a di erence d not inf2;v=2gthen by Lemma 3.3.4(vi) we avoid this case (since then the last edge in i would have di erence d 6= 2); so in this situation we can assume that D4 = mD4(2)f2g[mD4(v=2)fv=2g. We are now in the case where j = ? for all j 2, and the last trail in 1 is either T1(D4;v=2) or T1(f2g) where D4 = mD4(2)f2g[mD4(v=2)fv=2g or D6 = mD6(2)f2g respectively. This situation is most easily handled by altering the de nitions of 1 and v 1 by changing 1 and v 1. The only change is that one of three things is done to avoid the new 1 ending on an edge of di erence 2: T1(D4;v=2) jD6j+5Y k=6 T1(f2g) or T1(D4;v=2) or jD6j+5Y k=6 T1(f2g) is detached (3.9) from the end of 1 and moved to v 1 as described below. This will ensure that 1 (as newly de ned) does not end on an edge of di erence 2. We will then need to check that the altering of these trails does not create a 2-cycle or 3-cycle. For any trail T, let (T) be formed by mapping each vertex ?2Zv in the trail to the vertex ?+v 2 modulo v. Let T0v 1(D4;v=2) = ( (T1(D4;v=2)) if D4 = mD4(2)f2g[mD4(v=2)fv=2g, and ? otherwise. 47 So if T0v 1(D4;v=2)6= ? then it is a closed trail that begins on vertex v 1 and satis es E(T0v 1(D4;v=2)) = E(T1(D4;v=2)). To see this equality, notice that E(T1(D4;v=2)) is the set of edges in the component of Gv((jD4j=2)f2;v=2g) that contains vertex 1; since v is even, this component also contains the vertex v 1. Similarly de ne T0v 1(f2g) = ( (T1(f2g)) if 22D6, and ? otherwise: Clearly E(T1(f2g)) = E(T0v 1(f2g)) and T0v 1(f2g) starts and ends on vertex v 1. Since preserves the distance between consecutive vertices in the trails T1(D4;v=2) and T1(f2g), each set of 3 consecutive edges in T0v 1(D4;v=2) and T0v 1(f2g) induces a path. Also, preserves the exibility to choose the rst 2 edges in T0v 1(D4;v=2) as stated in Lemma 3.3.4(ii) and the exibility in our choice of the direction of the rst edge in T0v 1(f2g). Let T01(D4;v=2) = ( ? if D4 = mD4(2)f2g[mD4(v=2)fv=2g, and T1(D4;v=2) otherwise. We are now ready to rede ne 1 = T1(jD1j=2fv=2;v=3g)T1(jD2j=2fv=3;v=6g)T1(D3;v=3)T01(D4;v=2) (notice that T1(D5;v=5) = ? since 2v=562D6) and rede ne v 1 = T0v 1(D4;v=2) 0 @ jD6j+5Y k=6 T0v 1(f2g) 1 A: As described in (Piv), for all j 0 if j+1 6= ?, j 6= ?, and 1+fj+1;1 2f0;f j; 1gthen we still de ne j+1 = j+1 and otherwise j+1 = j+1. Since j = ? for 2 j v 2 and since v> 3 in this lemma, j = j for 2 j v 1. Then since d1 = 1 we de ne = v 1Y j=0 j (j;j + 1) = 0 (0;1) 1 (1;2;3;:::;v 1) v 1(v 1;0): In view of (3.9) it remains to check there are no 2-cycles or 3-cycles in the following trails: 1 (1;2;3) and (v 3;v 2;v 1) v 1(v 1;0). Note that since v > 3 in this lemma we know that there are at least 2 edges of di erence 1 between 1 and v 1. Since 1 cannot end on an edge of di erence 2 by (3.9) (recall that 1 does not contain the trail T1(f2g) and if T01(D4;v=2)6= ? then D4 contains a di erence not in f2;v=2gand by Lemma 3.3.4(vi) we let it be d so that we avoid this case), following the original argument shows that each set of 3 consecutive edges in 1 (1;2;3) induces a path. By exercising the choice we have in the rst two edges of T0v 1(D4;v=2) and T0v 1(f2g), we can ensure that the rst edge of v 1 is fv 1;1g (an edge of 48 di erence 2); so f v 1;1 = 2. It remains to show that: v 3 6= v 1 + f v 1;1 = 1; v 2 6= v 1 + f v 1;1 = 1 (this situation cannot occur since v > 3); v 2 6= v 1+f v 1;1 +f v 1;2 = 1+f v 1;2; v 1 f v 1; 1 6= 0; and v 1 f v 1; 2 f v 1; 1 6= 0. If v = 4 then by Lemma 3.3.4(v) all edges would occur in 0 , contradicting i = 1 so the rst situation cannot occur. By Lemma 3.3.4 and the de nition of T0v 1(f2g) the second edge of v 1 is either f1;3g or f1;v=2 + 1g. Then v 2 6= 1 + f v 1;2 since otherwise v = 5 (a contradiction since v6 5 (mod 10)) or v = 6 (a contradiction since 2 = v=3 and v=362D4) respectively, so the third situation is resolved. Since each edge in v 1 is an edge of di erence 2 or v=2, it follows that v 1 f v 1; 1 6= 0. Also since each edge in v 1 is an of di erence 2 or v=2, it follows that v 1 f v 1; 2 f v 1; 1 6= 0 since otherwise v = 6, and so 2 = v=3, a contradiction since v=362D4. Thus is a closed trail such that every set of 3 consecutive edges in induce a path. The following lemma makes use of the trail decomposition formed in Lemma 3.3.7 to construct a 5{CS using a speci ed number of 5-cycles of Type A, B and C. This lemma will be useful in using up all of the di erences needed to cover the 2v( +m) mixed edges in ( + m)Kv+u Kv. De ne degH(v) to be the degree of v in the multigraph of H. For any two vertex disjoint graphsG1 andG2, de neG1_tG2 to be the multigraph with vertex set V(G1_tG2) = V(G1)[V(G2) and edge set E(G1_tG2) = E(G1)[ E(G2)[(tffg1;g2gjg1 2V(G1);g2 2V(G2)g). Lemma 3.3.8. Suppose that: (a) the conditions of Lemma 3.2.1 are satis ed; (b) there exist sets 1 and 2 of di erences such that 1[ 2 D(v)m; (c) D = 1 satis es the conditions of Lemma 3.3.7; (d) j 1j+j 2j= d; and (e) j 2j= (c a 2b)=v. Then there exists a 5{CS of Gv( 1[ 2)_ +m ( +m)K2. Remark. Since v divides c a 2b by Lemma 3.2.1(vii) and c a 2b 0 by Lemma 3.2.1(vi), j 2j is a non-negative integer. Proof. De ne the required 5{CS (Zv[f11;12g;B) by following the approach de- scribed at the end of Section 3.2. The set B will contain a, b, and c 5-cycles of Types A, B, and C respectively, thereby exhausting all the pure edges (as will be seen). By Lemma 3.2.1(iii), 2a + 3b + c = vd = v(j 1j+j 2j). Edges in Gv( 1) will be used to construct b paths of length 3 and 2b paths of length 1 (that are combined into b=2 trails of length 10), and a paths of length 2 and a paths of length 1 (that are combined into a paths of length 3); the remaining c a 2b ( 0 by Lemma 3.2.1(vi)) paths of length 1 will occur in Gv( 2). SojE(Gv( 1))j= 3b+ 2a+ 2b+a = 3a+ 5b and since Gv( 1) is regular, each vertex has degree 2(3a + 5b)=v. Notice that by 49 Lemma 3.2.1(iii,vii), 3a+ 5b is divisible by v. By Lemma 3.3.7 there exists a closed trail T = (g0;g1;:::;gvj 1j = g0) of Gv( 1) such that every 3 consecutive edges induces a path. The number of edges in T is vd (c a 2b) = 5b+ 3a (by Lemma 3.2.1(iii)). Arbitrarily break T into a set T1 of b=2 trails that are each of length 10 and a set T2 of a paths that are each of length 3. Form a set of 5-cycles B1 = St2T1[T2 B1(t) where B1(gi;gi+1;gi+2;gi+3) =f(gi;gi+1;gi+2;12;11);(gi+2;gi+3;12;gi+1;11)g and B1(gi;gi+1;:::;gi+10) =f(gi;gi+1;12;gi+2;11);(gi+1;gi+2;gi+3;gi+4;11); (gi+4;gi+5;11;gi+3;12);(gi+5;gi+6;11;gi+7;12); (gi+6;gi+7;gi+8;gi+9;12);(gi+9;gi+10;12;gi+8;11)g Notice that for each t2T1[T2, each vertex gj in t is joined to11 and12 in the 5-cycles in B1(t) with degt(gj)=2 edges except for the rst vertex and the last vertex in t if they are di erent, in which case they have odd degree in t, so the rst is joined with one less edge to 12 than to 11 and the last is joined with one less edge to 11 than to12. Therefore, since T is a closed trail, each vertex z in Zv is joined to each of 11 and 12 with degT(z)=2 = (3a+ 5b)=v edges in 5-cycles in B1. Finally, let B2 = f(z;z + d;12;z + d + 1;11) jd2 2;z 2 Zvg. Then each vertex in Zv is joined to each of11 and12 with 2(c a 2b)=v edges in 5-cycles in B2. Then each vertex z2Zv is joined to each of11 and12 with degT(z)=2 = (3a+ 5b)=v edges in cycles in B1 and 2(c a 2b)=v edges in cycles in B2. So each z2Zv is joined to each of11 and12 with ((3a+5b)+2(c a 2b))=v = (a+b+2c)=v = +m by Lemma 3.2.1(iv). Also, each of the a trails of length 3 give rise to a edges joining 11 to 12 in B1, so 11 and 12 are joined by a = + m edges as required. Since clearly the edges of Gv( 1[ 2) occur in T, (Zv[f11;12g;B = B1[B2) is a 5{CS of Gv( 1[ 2)_ +m ( +m)K2. 3.4 The small cases for m As in Chapter 2, we embark on a proof of the main result by beginning with a section which will prove the necessary conditions in Lemma 2.1.2 are su cient when u = 2 and m is small. Lemma 3.4.1. Let v = 10k, and m be integers satisfying Conditions (a,b,d) of Lemma 2.1.2 with u = 2. If m = 2 or if m2f4;6;8g and + m = 10, then any 5{CS of Kv can be enclosed in a 5{CS of ( +m)Kv+2. Proof. Let (V = Z10k;A) be a 5{CS of Kv and let V [U be the vertex set of ( + m)Kv+2 where U =f11;12g. Since (V;A) exists, it follows by Theorem 1.2.2 that is even. So m is even by Lemma 2.1.2(a). By Lemma 2.1.2(b) + m 0 (mod 5). Therefore + m 0 (mod 10). Thinking of v=2 as half a di erence, we begin by choosing v edges to place in cycles containing only pure edges (edges 50 between vertices only in V or only in U) using di erences in Dv(m) where is de ned in Equation (3.1). Suppose m = 2. Then mKv = 2Kv contains edges of each di erence in D(v)2. Care must be taken with edges of di erence v=2 in E(Kv) since there are only v=2 of them. To explicitly describe the 5-cycles containing all the edges of di erences (yet to be chosen), we make use of Skolem and hooked Skolem sequences. By Theorem 1.1.1 or 1.1.2, let P0 =f(x0i;y0i)j1 i k 2;y0i >x0ig correspond to a Skolem sequence or hooked Skolem sequence of order k 2 with k 2 0 or 1 (mod 4) or k 2 2 or 3 (mod 4) respectively; so each element inf1;2;:::;2k 4g orf1;2;:::;2k 3gnf2k 4grespectively occurs in exactly one element of P0. Now de ne P = f(xi = x0i + 3;yi = y0i + 3) j (x0i;y0i) 2P0g if k 2 0 or 1 (mod 4) and P =f(xi = x0i + 4;yi = y0i + 4)j(x0i;y0i)2P0g if k 2 2 or 3 (mod 4). Then with ci = 8> >>>< >>>> : (0;xi;xi yi;3k;5k + 1 +i) if 1 i k 2, (0;3;4k + 2;k + 2;5k + 1) if i = k 1, (0;2k + 1;4k + 1;2k;5k) if i = k and k 2 0;1 (mod 4), and (0;4;2k + 4;5k + 4;5k) if i = k and k 2 2;3 (mod 4), (3.10) (where arithmetic is done modulov) form the set of 5-cyclesB0 = c00i 1 = cij1 i k where computations are done modulo v. Table 3.1 lists the di erences of edges that occur in cycles in B0 when is as big as possible (from Lemma 3.2.1 this happens when is as small as possible and not 0, namely when = 8, and so when = 10k 11; notice that when = 0 a 5{CS of Kv can be enclosed in a 5{CS of ( + m)Kv+u by Theorem 1.2.2). Edges Di erenceswhenk 2 0;1 (mod 4) Di erenceswhenk 2 2;3 (mod 4) f0;xig;fxi;xi yig 4;5;:::;2k 1 5;6;:::;2k 1;2k+1 fxi yi;3kg 3k+1;3k+2;:::;4k 2 3k+1;3k+2;:::;4k 2 f3k;5k+1+ig 2k+2;2k+3;:::;3k 1 2k+2;2k+3;:::;3k 1 f5k+1+i;0g 5k 2;5k 3;:::;4k+1 5k 2;5k 3;:::;4k+1 ci ifi=k 1 3;3k;4k 1;4k 1;5k 1 3;3k;4k 1;4k 1;5k 1 ci ifi=k 2k;2k+1;2k+1;3k;5k 4;4;2k;3k;5k Table 3.1: Edges of di erences in B0 when is as large as possible, v 0 (mod 10), and m = 2 Let B00 = 2B0 be the multiset consisting of 2 copies of each 5-cycle in B0. De ne B =fc00i +jji2Z =5;c00i (mod k) 2B00;j2Zvg[E where E = 8 >>> >>> < >>> >>> : ? if 0 (mod 5), 2 if 1 (mod 5), 1[ 2 if 2 (mod 5), 3 if 3 (mod 5), and 2[ 3 if 4 (mod 5). 51 Notice that ck 1 and ck will only be chosen once in B. Fortunately when is as small as possible ( is as large as possible) = 10k 11 and so E = ? allowing the di erences 3 and 2k to be used in ck 1. Let D be the set of di erences not used in forming B. Notice that because m = 2, f1;2g D. Partition D into two sets 1 and 2 so thatf1;2g 1 and 1 contains as many di erences that are not v=2, v=3, v=4, v=5, or 2v=5 as possible. When is as small as possible, it is clear that Conditions (A-D) of Lemma 3.3.7 are satis ed. Whenever increases will decrease by 10 and so 10 more di erences (at most 2 copies of the same di erence) will be contained in D. So there are still enough di erent di erences for any value ensuring 1 still satis es Conditions (A-D) of Lemma 3.3.7. So by Lemma 3.3.8, there exists a 5{CS (V [U;C) of Gv(D)_ +m ( +m)K2 which covers each mixed edge 2v( + m) times. Thus, (Z10k[f11;12g;A[B[C) is a 5{CS(v + 2; + 2) that encloses the given 5{CS (Zv;A). Let m 2f4;6;8g and + m = 10, so d = + m. Now let P0 = f(xi;yi) j 1 i k 2;yi > xig be the collection of pairs from a Skolem sequence or hooked Skolem sequence of order k 2 for the set f1;2;:::;2k 4g or f1;2;:::;2k 3g if k 2 0 or 1 (mod 4) or k 2 2 or 3 (mod 4) respectively. So each element in f1;2;:::;2k 4g or f1;2;:::;2k 3gnf2k 4g occurs in exactly one element of P0. Now de ne P = f(xi = x0i + 3;yi = y0i + 3) j (x0i;y0i) 2P0g when using Skolem sequences and P = f(xi = x0i + 4;yi = y0i + 4) j (x0i;y0i) 2 P0g. Then with ci as de ned in Equation (3.10) form the set of 5-cycles B0 = 2fci + j jj 2Zv;1 i k 2;(xi;yi) 2Pg[fci + jjj2Zv;i2fk 1;kgg where computations are done modulo v. Let P =f(xi;yi)j1 i k 1;yi >xigbe the collection of pairs from a Skolem sequence or hooked Skolem sequence of order k 1 for the setf1;2;:::;2k 2g orf1;2;:::;2k 3gif k 1 0 or 1 (mod 4) or k 1 2 or 3 (mod 4) respectively. Then with c0i = ( (0;xi;xi yi;3k;5k +i) if 1 i k 1, and (0;2k;6k;9k;5k) if i = k, for the set of 5-cycles B00 = 2fc0i +jjj2Zv;1 i k 1;(xi;yi)2P g[fc0k +jj j2Zvg. Table 3.2 lists the di erences of edges that occur in cycles in B00 when is as large as possible (from Lemma 3.2.1 this happens when is as small as possible and not 0; notice that when = 0 a 5{CS of Kv can be enclosed in a 5{CS of ( +m)Kv+u by Theorem 1.2.2). Edges Di erenceswhenk 1 0;1 (mod 4) Di erenceswhenk 1 2;3 (mod 4) f0;xig;fxi;xi yig 1;2;:::;2k 2 1;2;:::;2k 3;2k 1 fxi yi;3kg 3k+1;3k+2;:::;4k 1 3k+1;3k+2;:::;4k 1 f3k;5k+ig 2k+1;2k+3;:::;3k 1 2k+1;2k+3;:::;3k 1 f5k+i;0g 5k 1;5k 2;:::;4k+1 5k 1;5k 2;:::;4k+1 c0i ifi=k 2k;3k;4k;4k;5k 2k;3k;4k;4k;5k Table 3.2: Edges of di erences in B00 when is as large as possible, v 0 (mod 10), and m2f4;6;8g 52 Then ((m 2)=2)B00[B0 contains (m 2)(2k 1)=2 + 2k 2 = mk m=2 1 5- cycles, but we needb =5c= mk 3 of them. Hence we need 1 or 2 more 5-cycles when m = 6 or m = 8 respectively. Let c001 = (0;2k;4k;6k;3k) and c002 = (0;2k;4k;7k;3k). Then let E0 contain 1 copy of c01 if m = 6 or 8 and 1 copy of c02 if m = 8. Notice that the 5-cycles in E0 contain at most m copies of di erences of edges not used in cycles in ((m 2)=2)B00[B0. Form the set of 5-cycles B = ((m 2)=2)B00[B0[fc00i +jjj2Zv;c00i 2E0 g[E : Since +m = 10, it follows that (m(v 1)=2 ) = +m = 10. Let D be the set of di erences not used in B. Notice that D contains at least (m 2)=2 copies of f2k;3k;2k 1gwhenk 1 0 or 1 (mod 4) or (m 2)=2 copies off2k;3k;2k 2gwhen k 1 2 or 3 (mod 4). Partition D into two sets 1 and 2 so that f1;2g 1 and 1 contains as many di erences that are not v=2, v=3, v=4, v=5, or 2v=5 as possible. In this way, Conditions (A-D) of Lemma 3.3.7 are satis ed for 1. So by Lemma 3.3.8 there exists a 5{CS (V [U;C) of Gv(D)_ +m ( +m)K2 ensuring we cover each mixed edge 2v( + m) times. Therefore (Zv[f11;12g;A[B[C) is a 5{CS(v + 2; +m) with m2f4;6;8g and +m = 10. The proof of the next several results follows that of Lemma 3.4.1 closely, but are su ciently di erent and important that they are described in detail. Lemma 3.4.2. Let v = 10k + 5 and assume Conditions (a,b,d) of Lemma 2.1.2 are satis ed. If m = 1 or if m2f2;3;4g and + m = 5, then any 5{CS of Kv can be enclosed in a 5{CS of ( +m)Kv+2. Proof. Let (V = Z10k+5;A) be a 5{CS of Kv and let U = f11;12g. Since (V;A) exists, + m 0 (mod 5) by Lemma 2.1.2(a). As in Lemma 3.2.1, the number of edges we must place in 5-cycles contained completely in mKv is m(v 1) 2 2a+ 3b+c v v = v: Since this is divisible by v, our plan is again to create 5-cycles in mKv using all the edges of specially chosen di erences. By Lemma 3.3.8, is a non-negative integer. Suppose m = 1. Then mKv = Kv contains edges of each di erence in D(v) = f1;:::;5k+2g. As in Lemma 3.4.1, we will use Skolem and hooked Skolem sequences to explicitly describe the 5-cycles containing all the edges of di erences (yet to be chosen). We begin with the case where k 2. Let P0 =f(x0i;y0i)j0 i k 3;y0i >x0ig be the collection of pairs from a Skolem sequence or hooked Skolem sequence of order k 2 from the set f1;2;:::;2k 4g or f1;2;:::;2k 3g if k 2 0 or 1 (mod 4) or k 2 2 or 3 (mod 4) respectively (this exists by Theorems 1.1.1 and 1.1.2 since k 3). So each element inf1;2;:::;2k 4gorf1;2;:::;2k 3gnf2k 4goccurs in exactly one element of P0. Now de ne P =f(xi = x0i + 4;yi = y0i + 4)j(x0i;y0i)2P0g 53 when using Skolem sequences and P =f(xi = x0i+5;yi = y0i+5)j(x0i;y0i)2P0gwhen using hooked Skolem sequences. Notice that because = 5k+2 d = 5k+2 ( +m) or 0 (depending on d) and + m 0 (mod 5), it follows that 0 or 2 (mod 5). Then with ci = ( (0;xi;xi yi;4k + 2;7k + 3 i) if 0 i k 3 and; (0;3k + 1;6k + 3;k + 2;5k + 3) if i = k 2, (3.11) we form the set of 5-cycles B = ci (mod k 1) +jji2Zb =5c;j2Zv [E where the computations are done modulo v, k 2, and where E = ? or 1[ 2 if 0 or 2 (mod 5) respectively. Table 3.3 lists the di erences of edges that occur in cycles in BnE if is as big as possible (from Lemma 3.2.1 this happens when is as small as possible, namely when = 4 and so = 5k 3). By design, the edges of di erences Edges Di erenceswhenk 2 0;1 (mod 4) Di erenceswhenk 2 2;3 (mod 4) f0;xig;fxi;xi yig 5;6;:::;2k 6;7;:::;2k;2k+2 fxi yi;4k+2g 4k+3;4k+4;:::;5k 4k+3;4k+4;:::;5k f4k+2;7k+3 ig 3k;3k 1;:::;2k+3 3k;3k 1;:::;2k+3 f7k+3 i;0g 3k+3;3k+4;:::;4k 3k+3;3k+4;:::;4k ci ifi=k 2 3k+1;3k+2;4k+1;5k+1;5k+2 3k+1;3k+2;4k+1;5k+1;5k+2 Table 3.3: Edges of di erences in BnE when is as large as possible and v 5 (mod 10) v=5 and 2v=5 do not occur in 5-cycles in BnE , hence are available to form the 5-cycles in E . If k = 0 then v = 5 and it is easy to see how to form the set 5-cycles B using di erences so that B contains only 5-cycles with 5 pure edges. If k = 1 then 6 , so form the set of 5-cycles B =b =5cf(0;1;3;6;10) +jjj2Zvg[E . Let D be the set of di erences not used in B. From Table 3.3 we knowf2;4g2D. Partition D into two sets 1 and 2 so that f2;4g 1 and 1 contains as many di erences that are not v=3, v=5, or 2v=5 as possible. If is as small as possible ( is as large as possible) then = 5k 3 and so 1;3 2D. From this, it is clear that Conditions (A-D) in Lemma 3.3.7 are satis ed for 1 when is as small as possible. As increases ( decreases) the di erences used to construct ci are added to D. In this manner, it is clear that 1 still satis es Conditions (A-D) of Lemma 3.3.7. So by Lemma 3.3.8 we can form a 5{CS (V [U;C) of Gv(D)_ +m ( +m)K2 ensuring we cover each mixed edge 2v( +m) times. Thus, (Z10k+5[f11;12g;A[B[C) is a 5{CS(v + 2; + 1) that encloses the given 5{CS (Zv;A). Let m2f2;3;4g and +m = 5. Now let P0 =f(xi;yi)j0 i k 3;yi >xig be the collection of pairs from a Skolem sequence or hooked Skolem sequence of order k 2 for the set f1;2;:::;2k 4g or f1;2;:::;2k 3g if k 2 0 or 1 (mod 4) or k 2 2 or 3 (mod 4) respectively. So each element inf1;2;:::;2k 4g or f1;2;:::;2k 3gnf2k 4g occurs in exactly one element of P0. Now de ne P = f(xi = x0i + 4;yi = y0i + 4) j (x0i;y0i) 2 P0g when using Skolem sequences and 54 P =f(xi = x0i + 5;yi = y0i + 5)j(x0i;y0i)2P0g when using hooked Skolem sequences. De ne the set B0 =fciji2Zk 1;(xi;yi)2Pg. Then we form the set of 5-cycles B =fci (mod k 1) ji2Zb =5cg[(m 1)Gv( 1)[(m 1)Gv( 2)[(m 1)Gv( 3) where computations are done modulo v and ci is de ned in Equation (3.11). Since b =5c= mk 1 and B0 contains mk m 5-cycles, the extra m 1 copies of Gv( 1)[ Gv( 2)[Gv( 3) ensures we have enough pure 5-cycles in B. Notice that regardless of our choice of m, +m = 5 and so (m(v 1)=2 ) = +m = 5. Let D be the set of di erences not used in B. There are m copies of both 4 and 2k+ 2 in D when k 2 0 or 1 (mod 10) and m copies of both 4 and 5 when k 2 2 or 3 (mod 4). Partition D into two sets 1 and 2 so thatf4;2k+2g 1 or f4;5g 1 if v 0 or 1 (mod 4) or v 2 or 3 (mod 4) respectively and 1 contains as many di erences that are not v=3, v=5, or 2v=5 as possible. It is clear that 1 satis es Conditions (A-D) of Lemma 3.3.7. By Lemma 3.3.8 there exists a 5{CS (V [U;C) of Gv(D)_ +m ( + m)K2 ensuring we cover each mixed edge 2v( +m) times. Therefore (Zv[f11;12g;A[B[C) is a 5{CS(v+ 2; +m) with m2f2;3;4g and +m = 5. Lemma 3.4.3. Let v 1;3; or 9 (mod 10) and assume Conditions (a,b,d) of Lemma 2.1.2 are satis ed. If m = 1 or if m 2f2;3;4g, + m = 5 and v 1 (mod 10), then any 5{CS of Kv can be enclosed in a 5{CS of ( +m)Kv+2. Proof. Let (V = Z10k+?;A) be a 5{CS of Kv and let U = f11;12g. Since (V;A) exists, + m 0 (mod 5) when v 1 (mod 10) and 0 (mod 5) when v 3;9 (mod 10) by Lemma 2.1.2(a-b). As in Lemma 3.2.1, the number of edges we must place in 5-cycles contained completely in mKv is m(v 1) 2 2a+ 3b+c v v = v: Since this is divisible by v, our plan is again to create 5-cycles in mKv using all the edges of specially chosen di erences. Suppose m = 1. Then mKv = Kv contains edges of each di erence in D(v) = f1;:::;5k + (? 1)=2g. As in Lemma 3.4.1, we will use Skolem and hooked Skolem sequences to explicitly describe the 5-cycles containing all the edges of di erences (yet to be chosen). If ? = 1, let P0 = f(x0i;y0i) j 1 i k 2;y0i > x0ig be the collection of pairs from a Skolem sequence or hooked Skolem sequence of order k 2 from the set f1;2;:::;2k 4g or f1;2;:::;2k 3g if k 2 0 or 1 (mod 4) or k 2 2 or 3 (mod 4) respectively. If ? 2f3;9g let P0 = f(x0i;y0i) j 1 i k 1;y0i > x0ig be the collection of pairs from a Skolem sequence or hooked Skolem sequence of order k 1 from the set f1;2;:::;2k 2g or f1;2;:::;2k 1g if k 1 0 or 1 (mod 4) or k 1 2 or 3 (mod 4) respectively. So each element in f1;2;:::;2k 4g or f1;2;:::;2k 3gnf2k 4g occurs in exactly one element of P0 when ? = 1. When ?2f3;9g, each element inf1;2;:::;2k 2gorf1;2;:::;2k 1gnf2k 4goccurs in 55 exactly one element of P0. Now de ne P =f(xi = x0i + 4;yi = y0i + 4)j(x0i;y0i)2P0g if ? = 1 or P =f(xi = x0i + 3;yi = y0i + 3)j(x0i;y0i)2P0g if ?2f3;9g. Then with ci = 8> >>>> >>> >>< >>> >>>> >>> : (0;xi;xi yi;3k;5k + 2 +i) if 1 i b =5c 1 and ? = 1, (0;xi;xi yi;3k + 1 +?=3;8k 2 +? i) if 1 i b =5c 1 and ?2f3;9g, (0;2k + 1;6k;10k;5k + 1) if i =b =5c, k 2 0;1 (mod 4) and ? = 1, (0;4;2k + 4;2;5k + 1) if i =b =5c, k 2 2;3 (mod 4), and ? = 1, (0;xi;xi yi;3k + 1 +?=3;8k 2 +? i) if i =b =5c and ? = 3, (0;2k + 2;5k + 4;k;4k + 3) if i =b =5c, k 1 0;1 (mod 4), and ? = 9, and (0;2k + 1;5k + 4;2k + 2;6k + 5) if i =b =5c, k 1 2;3 (mod 4), and ? = 9, (3.12) we form the set of 5-cycles B = fci +jj1 i b =5c;j2Zv;(xi;yi)2Pg where the computations are done modulo v. By Lemma 3.2.1, 0 (mod 5). Tables 3.4 and 3.5 list the di erences of edges that occur in cycles in B if is as big as possible (from Lemma 3.2.1 this happens when is as small as possible, namely when = 4 if ? = 1 and = 5 if ?2f3;9g and so = 5k 5 if ?2f1;3g and = 5k if ? = 9). Edges Di erenceswhenk 2 0;1 (mod 4) Di erenceswhenk 2 2;3 (mod 4) f0;xig;fxi;xi yig 5;6;:::;2k 5;6;:::;2k 1;2k+1 fxi yi;3kg 3k+1;3k+2;:::;4k 2 3k+1;3k+2;:::;4k 2 f3k;5k+2+ig 2k+3;2k+4;:::;3k 2k+3;2k+4;:::;3k f5k+2+i;0g 5k 2;5k 3;:::;4k+1 5k 2;5k 3;:::;4k+1 ci ifi=b =5c 2k+1;4k 1;4k;5k 1;5k 4;2k;2k+2;5k 1;5k Table 3.4: Edges of di erences in B when is as large as possible for ? = 1 Edges Di erenceswhenk 1 0;1 (mod4) Di erenceswhenk 1 2;3 (mod4) f0;xig;fxi;xi yig 4;5;:::;2k+1 4;5;:::;2k;2k+2fx i yi;3k+?=3g 3k+1+?=3;3k+2+?=3;:::;4k 1+?=3 3k+1+?=3;3k+2+?=3;:::;4k 1+?=3f3k+?=3;8k 2+? ig 5k 2+2?=3;5k 3+2?=3;:::;4k+2?=3 5k 2+2?=3;5k 3+2?=3;:::;4k+2?=3 f8k 2+? i;0g 2k+3;2k+4;:::;3k+1 2k+3;2k+4;:::;3k+1c i ifi=b =5cand?=9 2k+2;3k+2;3k+3;4k+3;4k+4 2k+1;3k+2;3k+3;4k+3;4k+4 Table 3.5: Edges of di erences in B when is as large as possible for ?2f3;9g Let D be the set of di erences not used in B. When is as large as possible ( is as small as possible) D = 8 >>> >>> < >>> >>> : f1;2;3;2k + 2g if v 1 (mod 10) and k 0;1 (mod 4), f1;2;3;4k 1;4kg if v 1 (mod 10) and k 2;3 (mod 4), f1;2;3;2k + 2;5k + 1g if v 3 (mod 10), f1;2;3;4k + 5g if v 9 (mod 10) and k 0;1 (mod 4), and f1;2;3;4k + 5g if v 9 (mod 10) and k 2;3 (mod 4). 56 Partition D into two sets 1 and 2 so thatf1;2;3g 1 and 1 contains as many di erences that are notv=3 as possible. It is clear that 1 satis es Conditions (A-D) of Lemma 3.3.7 when is as small as possible. As increases, the di erences represented in ci are added to D. So it is clear that Conditions (A-D) of Lemma 3.3.7 will still be satis ed and so by Lemma 3.3.8 there exists a 5{CS (V [U;C) of Gv(D)_ +m ( + m)K2 ensuring we cover each mixed edge 2v( + m) times. Thus, (Z10k+?[ f11;12g;A[B[C) is a 5{CS(v + 2; + 1) that encloses the given 5{CS (Zv;A). Let v 1 (mod 10), m2f2;3;4g, and +m = 5. As before, let P0 =f(x0i;y0i)j 1 i k 2;y0i > x0ig be the collection of pairs from a Skolem sequence or hooked Skolem sequence of order k 2 from the set f1;2;:::;2k 4g or f1;2;:::;2k 3g if k 2 0 or 1 (mod 4) or k 2 2 or 3 (mod 4) respectively. Now de ne P = f(xi = x0i + 4;yi = y0i + 4)j(x0i;y0i)2P0g. Then with ci de ned as in Equation (3.12) we form the set of 5-cycles B0 =fcij1 i k 1;(xi;yi)2Pgwhere computations are done modulo v. Let B00 = mB0. Then B00 contains m(k 1) 5-cycles, but we need b =5c= mk 1 of them. Hence we need m 1 more 5-cycles. Let c0i = 8 >>> < >>> : (0;1;2k + 3;2k + 5;3) if i = 1 and k 0;1 (mod 4), (0;1;5;7;3) if i = 2 and k 0;1 (mod 4), (0;1;4k;4k + 2;3) if i = 1 and k 2;3 (mod 4), and (0;1;4k + 1;4k + 3;3) if i = 2 and k 2;3 (mod 4). Then let E0 contain 1, 1, or 2 copies of c01 if m = 2; 3, or 4 respectively, and contain 1 or 2 copies of c02 if m = 3 or 4 respectively. Notice that the cycles in E0 contain at most m copies of edges not used in cycles in B00. Then we form the set of 5-cycles B =fci +jj1 i b =5c;ci (mod k 1) 2B00;j2Zvg[fc0i +jjj2Zv;c0i2E0 g: Notice that regardless of our choice of m, + m = 5. So (m(v 1)=2 ) = +m = 5. Let D be the set of di erences not used in B. It is clear that D contains 1;2; and 3. Partition D into two sets 1 and 2 so that f1;2;3g 1 and 1 contains as many di erences that are not v=3 as possible. Since v=5;2v=5;v=262D, it is clear that 1 satis es Conditions (A-D) of Lemma 3.3.7 and by Lemma 3.3.8 there exists a 5{CS (V[U;C) of Gv(D)_ +m( +m)K2 ensuring we cover each mixed edge 2v( +m) times. Therefore (Zv[f11;12g;A[B[C) is a 5{CS(v+ 2; +m) with m2f2;3;4g and +m = 5. Lemma 3.4.4. Let v 4;6; or 8 (mod 10) and assume Conditions (a,b,d) of Lemma 2.1.2 are satis ed. If m = 2 or if m 2f4;6;8g, + m = 10, and v 6 (mod 10), then any 5{CS of Kv can be enclosed in a 5{CS of ( +m)Kv+2. Proof. Let (V = Zv;A) be a 5{CS of Kv and let U =f11;12g. Since (V;A) exists, m 0 (mod 2) by Lemma 2.1.2(a). As in Lemma 3.2.1, the number of edges we must place in 5-cycles contained completely in mKv is m(v 1) 2 2a+ 3b+c v v = v: 57 Since this is divisible by v, our plan is again to create 5-cycles in mKv using all the edges of specially chosen di erences. Suppose m = 2. Then mKv = 2Kv contains edges of each di erence in D(v)2. Care must be taken with edges of di erence v=2 in E(Kv) since there are only v=2 of them. As in Lemma 3.4.1, we will use Skolem and hooked Skolem sequences to explicitly describe the 5-cycles containing all the edges of di erences (yet to be chosen). Let P0 =f(x0i;y0i)j1 i k 1;y0i >x0igbe the collection of pairs from a Skolem sequence or hooked Skolem sequence of order k 1 from the setf1;2;:::;2k 2gor f1;2;:::;2k 1g if k 1 0 or 1 (mod 4) or k 1 2 or 3 (mod 4) respectively. So each element inf1;2;:::;2k 2gorf1;2;:::;2k 1gnf2k 2goccurs in exactly one element of P0. Now de ne P =f(xi = x0i + 3;yi = y0i + 3)j(x0i;y0i)2P0g. Then with ci = ( (0;xi;xi yi;3k + 1;5k + 3 +i) if 1 i k 1 and ?2f4;6g, (0;xi;xi yi;3k + 3;5k + 5 +i) if 1 i k 1 and ? = 8, (3.13) we form the set of 5-cycles B0 = c00i 1 = cij1 i k 1 where the computations are done modulo v. Notice that based on our choice of d, 0 (mod 5). Tables 3.6 and 3.7 list the di erences of edges that occur in cycles in B if is as big as possible (from Lemma 3.2.1 this happens when is as small as possible, namely when = 10 if v 4;8 (mod 10) or = 8 if v 6 (mod 10)). Edges Di erenceswhenk 1 0;1 (mod 4) Di erenceswhenk 1 2;3 (mod 4) f0;xig;fxi;xi yig 4;5;:::;2k+1 4;5;:::;2k;2k+2 fxi yi;3k+1g 3k+2;3k+3;:::;4k 3k+2;3k+3;:::;4k f3k+1;5k+3+ig 2k+3;2k+4;:::;3k+1 2k+3;2k+4;:::;3k+1 f5k+3+i;0g 5k 4+?;5k 5+?;:::;4k 2+? 5k 4+?;5k 5+?;:::;4k 2+? Table 3.6: Edges of di erences in B0 when is as large as possible for ?2f4;6g Edges Di erenceswhenk 1 0;1 (mod 4) Di erenceswhenk 1 2;3 (mod 4) f0;xig;fxi;xi yig 4;5;:::;2k+1 4;5;:::;2k;2k+2 fxi yi;3k+3g 3k+4;3k+5;:::;4k+2 3k+4;3k+5;:::;4k+2 f3k+3;5k+5+ig 2k+3;2k+4;:::;3k 2k+3;2k+4;:::;3k f5k+5+i;0g 5k+2;5k+1;:::;4k+4 5k+2;5k+1;:::;4k+4 Table 3.7: Edges of di erences in B when is as large as possible for ? = 8 Let c00k 1 = (0;1;3;4k + 4;4k + 1) or (0;1;3;3k + 4;3k + 1) if ? 2 f4;6g or ? = 8 respectively. Now let B00 = 2B0[fc00k 1g so that we form the set of 5-cycles B =fc00i +jji2Z =5;c00i (mod k) 2B00;j2Zvg. Let D be the set of di erences not used in B. It is clear that 1;2; and 3 are contained in D. Partition D into two sets 1 and 2 so that f1;2;3g 1 and 1 58 contains as many di erences that are not v=2, v=3, or v=4 as possible. Since v=5 and 2v=5 are not in D, it follows that 1 satis es Conditions (A-D) of Lemma 3.3.7 and so by Lemma 3.3.8 there exists a 5{CS (V[U;C) of Gv(D)_ +m( +m)K2 ensuring we cover each mixed edge 2v( +m) times. Thus, (Z10k+?[f11;12g;A[B[C) is a 5{CS(v + 2; + 2) that encloses the given 5{CS (Zv;A). Let ? = 6, m2f4;6;8g, and +m = 10. Let P0 =f(x0i;y0i)j1 i k 1;y0i > x0ig be the collection of pairs from a Skolem sequence or hooked Skolem sequence of order k 1 from the set f1;2;:::;2k 2g or f1;2;:::;2k 1g if k 1 0 or 1 (mod 4) or k 1 2 or 3 (mod 4) respectively. Now de ne P =f(xi = x0i + 3;yi = y0i + 3) j (x0i;y0i) 2P0g. Then with ci de ned as in Equation (3.13) we form the set of 5-cycles B0 = fc00i 1 = ci j 1 i k 1;(xi;yi) 2Pg where computations are done modulo v. Let B00 = mB0 be the multiset consisting of m copies each 5-cycle in B0. Then B00 contains m(k 1) 5-cycles, but we need b =5c = mk 2 + m=2 of them. Hence we need 3m=2 2 more 5-cycles. Let c01 = (0;1;3;4k + 5;4k + 2), c02 = (0;2k + 1;4k + 2;8k + 5;4k + 3), c03 = (0;2k + 2;4k + 4;8k + 6;4k + 3), c04 = (0;2k+1;6k+3;k;5k+3), and c05 = (0;1;3;4k+4;4k+1). If k 1 0 or 1 (mod 4), then let E0 : contain 1, 2, or 2 copies of c01 if m = 4; 6, or 8 respectively, contain 1, 2, or 4 copies of c03 if m = 4, 6, or 8 respectively, and contain m=2 copies of c05. If k 1 2 or 3 (mod 4), then let E0 : contain 0, 1, or 2 copies of c01 if m = 4; 6, or 8 respectively, contain 1, 2, or 2 copies of c02 if m = 4, 6, or 8 respectively, contain 1, 1, and 2 copies of c04 if m = 4, 6, or 8 respectively, and contain m=2 copies of c05. Notice that the cycles in E0 contain at most m copies of edges not used in cycles in B00. Then B =fci +jj1 i k 1;ci (mod k) 2B00;j2Zvg[fc0i +jjj2Zv;c0i2E0 g: Notice that regardless of our choice of m, + m = 10. So (m(v 1)=2 ) = +m = 10. Let D be the set of di erences not used in B. By examining the remaining di erences we know di erences 1 and 2 appear in D and when k 0 or 1 (mod 4), D has at most 1 copy of v=2. Partition D into two sets 1 and 2 so that f1;2g 1 and 1 contains as many di erences that are not v=2, v=3, or v=4 as possible. Based on the remaining di erences it is clear that v=3, v=6, 2v=5; and v=5 are not in D. Thus 1 satis es Conditions (A-D) of Lemma 3.3.7 and by Lemma 3.3.8 there exists a 5{CS (V [U;C) of Gv(D)_ +m ( + m)K2 ensuring we cover each mixed edge 2v( +m) times. Therefore (Zv[f11;12g;A[B[C) is a 5{CS(v+ 2; +m) with m2f4;6;8g and +m = 10. 59 Lemma 3.4.5. Let v 2 (mod 10) and assume Conditions (a,b,d) of Lemma 2.1.2 are satis ed. If m = 10 then any 5{CS of Kv can be enclosed in a 5{CS of ( + m)Kv+2. Proof. Let (V = Z10k+2;A) be a 5{CS of Kv and let U = f11;12g. Since (V;A) exists, m 0 (mod 10). As in Lemma 3.2.1, the number of edges we must place in 5-cycles contained completely in mKv is m(v 1) 2 2a+ 3b+c v v = v: Since this is divisible by v, our plan is again to create 5-cycles in mKv using all the edges of specially chosen di erences. Suppose m = 10. Then mKv = Kv contains edges of each di erence in D(v)10. Care must be taken with edges of di erence v=2 in E(Kv) since there are only v=2 of them. As in Lemma 3.4.1, we will use Skolem and hooked Skolem sequences to explicitly describe the 5-cycles containing all the edges of di erences (yet to be chosen). Let P0 =f(x0i;y0i)j1 i k 2;y0i >x0igbe the collection of pairs from a Skolem sequence or hooked Skolem sequence of order k 2 from the setf1;2;:::;2k 4gor f1;2;:::;2k 3g if k 2 0 or 1 (mod 4) or k 2 2 or 3 (mod 4) respectively. So each element inf1;2;:::;2k 4gorf1;2;:::;2k 3gnf2k 4goccurs in exactly one element of P0. Now de ne P =f(xi = x0i + 4;yi = y0i + 4)j(x0i;y0i)2P0g. Then with c0i = 8 >>> < >>> : (0;4;4k + 3;8k + 3;4k + 2) if i = 1, (0;1;3;3k + 3;3k) if i = 2, (0;1;3;2k + 4;2k + 1) if i = 3 and k 2 0;1 (mod 4), and (0;1;3;2k + 3;2k) if i = 3 and k 2 2;3 (mod 4), we form the set of 5-cycles B0 =fci 1 = (0;xi;xi yi;3k;5k + 1 +i)j1 i k 2;(xi;yi)2Pg and let E0 contain 10 copies of c01, 5 copies of c02, and 2 copies of c03. Notice that based on our choice of d, 0 (mod 5). Table 3.8 lists the di erences of edges that occur in cycles in B0[E0 if is as big as possible (from Lemma 3.2.1 this happens when is as small as possible and not 0, namely when = 10 and so = 50k 15). Then form the set of 5-cycles B =fci +jji2Zz1;ci (mod k 1) 2B0;j2Zvg[z2fc+jjj2 Zv;c2E0 g where z1 = min(f =5;m(k 2)g), z2 = max(f0; =5 m(k 2)g), and the computations are done modulo v. Let D be the set of di erences not used in B. There are 3 copies of 1, 2, and 3 in D when is as small as possible ( is as large as possible. Partition D into two sets 1 and 2 so that f1;2;3g 1 and 1 contains as many di erences that are not 60 Edges Di erenceswhenk 2 0;1 (mod 4) Di erenceswhenk 2 2;3 (mod 4) f0;xig;fxi;xi yig 5;6;:::;2k 5;6;:::;2k 1;2k+1 fxi yi;3kg 3k+1;3k+2;:::;4k 2 3k+1;3k+2;:::;4k 2 f3k;5k+1+ig 2k+2;2k+3;:::;3k 1 2k+2;2k+3;:::;3k 1 f5k+1+i;0g 5k;5k 1;:::;4k+3 5k;5k 1;:::;4k+3 c0i ifi=1 4;4k 1;4k;4k+1;4k+2 4;4k 1;4k;4k+1;4k+2 c0i ifi=2 1;2;3;3k;3k 1;2;3;3k;3k c0i ifi=3 1;2;3;2k+1;2k+1 1;2;3;2k;2k Table 3.8: Edges of di erences in B0[E0 when is as large as possible for ? = 2 v=2, v=3, or v=4 as possible. As increases, the di erences from ci are added to D. In this manner, it is clear that 1 will satisfy Conditions (A-D) of Lemma 3.3.7 and by Lemma 3.3.8 there exists a 5{CS (V [U;C) of Gv(D)_ +m ( + m)K2 ensuring we cover each mixed edge 2v( +m) times. Thus, (Z10k+2[f11;12g;A[B[C) is a 5{CS(v + 2; + 10) that encloses the given 5{CS (Zv;A). Lemma 3.4.6. Let v 7 (mod 10) and assume Conditions (a,b,d) of Lemma 2.1.2 are satis ed. If m = 5, then any 5{CS of Kv can be enclosed in a 5{CS of ( + m)Kv+2. Proof. Let (V = Z10k+7;A) be a 5{CS of Kv and let U = f11;12g. Since (V;A) exists, +m 0 (mod 5). As in Lemma 3.2.1 in Lemma 3.4.1, the number of edges we must place in 5-cycles contained completely in mKv is m(v 1) 2 2a+ 3b+c v v = v: Since this is divisible by v, our plan is again to create 5-cycles in mKv using all the edges of specially chosen di erences. Suppose m = 5. Then mKv = Kv contains edges of each di erence in D(v)5. As in Lemma 3.4.1, we will use Skolem and hooked Skolem sequences to explicitly describe the 5-cycles containing all the edges of di erences (yet to be chosen). Let P0 =f(x0i;y0i)j1 i k 1;y0i >x0igbe the collection of pairs from a Skolem sequence or hooked Skolem sequence of order k 1 from the setf1;2;:::;2k 2gor f1;2;:::;2k 1g if k 1 0 or 1 (mod 4) or k 1 2 or 3 (mod 4) respectively. So each element inf1;2;:::;2k 2gorf1;2;:::;2k 1gnf2k 2goccurs in exactly one element of P0. Now de ne P =f(xi = x0i + 3;yi = y0i + 3)j(x0i;y0i)2P0g. Then with c0i = 8 >>> >>> < >>> >>> : (0;2k + 2;5k + 4;k + 1;5k + 3) if i = 1 and k 1 0;1 (mod 4), (0;1;2;5;3) if i = 2 and k 1 0;1 (mod 4), (0;1;2k + 2;7k + 5;4k + 3) if i = 1 and k 1 2;3 (mod 4), (0;2;4;1;4k + 3) if i = 2 and k 1 2;3 (mod 4), and (0;2;2k + 3;2k + 1;5k + 3) if i = 3 and k 1 2;3 (mod 4), 61 we form the set of 5-cycles B0 =fci 1 = (0;xi;xi yi;3k + 2;5k + 4 +i)j1 i k 1;(xi;yi)2Pg and let E0 contain 5 copies of c01 and 1 copy of c02 if k 1 0 or 1 (mod 4), and contain 4 copies of c01, 1 copy of c02 and 1 copy of c03 if k 1 2 or 3 (mod 4). Notice that based on our choice of d, 0 (mod 5). Table 3.9 lists the di erences of edges that occur in cycles in B0[E0 if is as big as possible (from Lemma 3.2.1 this happens when is as small as possible, namely when = 5 and so = 25k + 5). Edges Di erenceswhenk 1 0;1 (mod 4) Di erenceswhenk 1 2;3 (mod 4) f0;xig;fxi;xi yig 4;5;:::;2k+1 4;5;:::;2k;2k+2 fxi yi;3k+2g 3k+3;3k+4;:::;4k+1 3k+3;3k+4;:::;4k+1 f3k+2;5k+4+ig 2k+3;2k+4;:::;3k+1 2k+3;2k+4;:::;3k+1 f5k+4+i;0g 5k+2;5k+1;:::;4k+4 5k+2;5k+1;:::;4k+4 c0i ifi=1 2k+2;3k+2;4k+2;4k+3;5k+3 1;2k+1;3k+2;4k+3;5k+3 c0i ifi=2 1;1;2;3;3 2;2;3;4k+2;4k+3 c0i ifi=3 2;2;2k+1;3k+2;5k+3 Table 3.9: Edges of di erences in B0nE0 when is as large as possible for ? = 7 De ne B = fci + j ji2Zz1;ci (mod k 1) 2B0;j 2Zvg[z2fc + j jj 2Zv;c2 E0 g where z1 = min(f =5;m(k 1)g), z2 = max(f0; =5 m(k 1)g), and the computations are done modulo v. Let D be the set of di erences not used in B. By examining Table 3.9, we see that 1, 2, and 3 are contained in D and v=2;v=4;v=5;2v=5;v=6 62D. Partition D into two sets 1 and 2 so that f1;2;3g 1 and 1 contains as many di erences that are not v=3 as possible. Thus 1 satis es Conditions (A-D) of Lemma 3.3.7 and by Lemma 3.3.8 there exists a 5{CS of Gv(D)_ +m ( + m)K2 ensuring we cover each mixed edge 2v( + m) times. Thus, (Z10k+7[f11;12g;A[B[C) is a 5{CS(v + 2; + 5) that encloses the given 5{CS (Zv;A). We can gather results from Lemmas 3.4.1, 3.4.2, 3.4.3, 3.4.4, 3.4.5, and 3.4.6 into the following corollary. Corollary 3.4.7. Let v, m and be integers satisfying Conditions (a,b,d) of Lemma 2.1.2 with u = 2. Let v = 10k +? with ?2f0;1;:::;9g. If: m = 1 when ?2f1;3;5;9g, m = 2 when ?2f0;4;6;8g, m = 5 when ? = 7, m = 10 when ? = 2, m2f2;3;4g, +m = 5, and ?2f1;5g, or m2f4;6;8g, +m = 10, and ?2f0;6g, then any 5{CS of Kv can be enclosed in a 5{CS of ( +m)Kv+2. 62 3.5 The Main Result The following lemma will be useful in constructing the enclosings when is as large as possible. Lemma 3.5.1. Let v and m be integers satisfying conditions (a), (b), and (d) of Lemma 2.1.2 with u = 2 and let = max(v;m). Then a 5{CS of Kv can be enclosed in a 5{CS of ( +m)Kv+2. Proof. Let (V = Zv;A) be a 5{CS of Kv. Since = max(v;m), +m m(v 1)=2 and so it follows that d = m(v 1)=2 by de nition and so = 0 from Equation (3.1). Partition D = D(v)m into two sets 1 and 2 so that f1;2g 1, 1 contains as many di erences that are not v=2, v=3, v=4, v=5, or 2v=5 as possible. So Conditions (A-D) of Lemma 3.3.7 hold for 1 and therefore by Lemma 3.3.8 a 5{CS of Kv can be enclosed in a 5{CS of ( +m)Kv+2 when = max(v;m). In the following theorem, Corollary 3.4.7 is used as a basis for an inductive argument to settle the enclosing problem when u = 2. Theorem 3.5.2. A 5{CS of Kv can be enclosed in a 5{CS of ( +m)Kv+2 if and only if (a) ( +m)u+m(v 1) 0 (mod 2), (b) u2 ( +m) +m v2 +vu( +m) 0 (mod 5), (c) m v2 2( +m) 12(v 1)( +m) 0. Proof. The necessity follows from Lemma 2.1.2(a,b,d), so we now prove the su ciency. Since we are assuming that a 5{CS of Kv exists, it follows by Theorem 1.2.2 that v62f2;3;4g, and by Condition (c) that v6= 1, so we know that v 5. If = 0 then by Condition (a) m(v + 1) 0 (mod 2) and by Condition (b) m(v + 2)(v + 1) 0 (mod 5), so by Theorem 1.2.2 there exists a 5{CS of mKv+2 as required; so we can assume that 1. Let (V;A) be a 5{CS of Kv. If v 0;4;6; or 8 (mod 10), v 2 (mod 10), or v 7 (mod 10), then it follows from Theorem 1.2.2 that m 0 (mod 2), m 0 (mod 10), and +m 0 (mod 5) respectively; in any other case m can potentially take on any positive integral value. To re ect this situation, let t(v) = 8> >>< >>>: 1 if v 1;3;5;9 (mod 10), 2 if v 0;4;6;8 (mod 10), 5 if v 7 (mod 10), and 10 if v 2 (mod 10). We often simply write t instead of t(v) when the value of v is clear. For any choice of v and m, let max(v;m) be the second largest integer satisfying Conditions (a-c), and let +min(v;m) be the second smallest integer satisfying Conditions (a-c). 63 We will rst establish that for any given v, the di erence between consecutive values of that satisfy Conditions (a) and (b) is a constant; call this di erence di (v). Secondly, for all m 1 and v 5, we settle the enclosing problem for both the smallest and the largest values of satisfying Conditions (a-c). Finally for all m 1 and v 5 it will be shown that for all satisfying Conditions (a-c) there exist non-negative integers 1, 2 with 1 + 2 = and positive integers m1;m2 with m1 + m2 = m such that for 1 i 2 there exists a 5{CS of iKv that can be enclosed in a 5{CS of ( i +mi)Kv+2. So the union of these two enclosings completes the proof. We turn to the rst step of the proof. For any given v and m, the di erence be- tween consecutive values of that satisfy Conditions (a) and (b) is a constant; namely di (v;m). Also by Conditions (a) and (b) and by Theorem 1.2.2, 0 (mod 2) if v is even and (2v + 1) di (v;m) 0 (mod 5). Therefore di (v;m) 0 (mod 5) and di (v;m) 0 (mod 10) if v is odd and even respectively. Since di (v;m) must be the smallest such value, if v is odd then di (v;m) = 5, and if v is even then di (v;m) = 10. Notice that if m1 6= m2 then di (v;m1) = di (v;m2). Therefore we de ne di (v) = di (v;m). We now turn to the second step in the proof; establishing the existence of the enclosing for the smallest and largest values of given v and m. Beginning with the smallest value, Tables 3.10 and 3.11 list the values of min(v;m), and were formed using Theorem 1.2.2 and Corollary 3.4.7. Three cases are considered in turn based on the value of v. m (mod 5t) v (mod 10) 0 t 2t 3t 4t 0,6 0 8 6 4 2 1,5 0 4 3 2 1 Table 3.10: Checking min(v;m) when v 0;1;5 or 6 (mod 10): each cell contains min(v;m) v (mod 10) m 2 3 4 7 8 9 any m 0 0 0 0 0 0 Table 3.11: Checking min(v;m) when v6 0;1;5 or 6 (mod 10): each cell contains min(v;m) Let v 0;1;5; or 6 (mod 10). The proof is by induction on m. By Corol- lary 3.4.7 if m 4t then any 5{CS of min(v;m)Kv can be enclosed in a 5{CS of ( min(v;m) + m)Kv+2. If m = 5t, by Table 2.8 min(v;10) = 0, so this enclosing has been established by Theorem 1.2.2 and we say there exists a 5{CS (V[f11;12g;B2) 64 of (5t)Kv+2. Suppose that for some m 6t and for all s with 1 sx0ig be the collection of pairs from a Skolem sequence or hooked Skolem sequence of order k 1 for the set f1;2;:::;2k 2g or f1;2;:::;2k 1g, if k 1 0 or 1 (mod 4) or k 1 2 or 3 (mod 4) respectively (see Theorems 1.1.1 and 1.1.2). So each element in f1;2;:::;2k 2gorf1;2;:::;2k 1gnf2k 2goccurs in exactly one element of P0. Now de ne P =f(xi = x0i + 2;yi = y0i + 2)j(x0i;y0i)2P0g. Then let B0 =fci 1 = (0;xi;xi yi;3k;5k + 1 +i)j1 i k 1;(xi;yi)2Pg (4.1) where computations are done modulo v. So for m = 1, form the set of 5-cycles B = fci + j ji2Z =5;ci 2B0;j2Zvg. Table 4.1 lists the di erences of the edges that occur in 5-cycles in B0 when is as large as possible. When is as large as possible ( is as small as possible), =5 = k 2 or k 1 and jB0j= k 2 or k 1 if ? = 2 or 3 respectively. So B0 is large enough to construct the required 5-cycles. Edges Di erenceswhenk 1 0;1 (mod 4) Di erenceswhenk 1 2;3 (mod 4) f0;xig;fxi;xi yig 3;4;:::;2k 3;4;:::;2k 1;2k+1 fxi yi;3kg 3k+1;3k+2;:::;4k 1 3k+1;3k+2;:::;4k 1 f3k;5k+1+ig 2k+2;2k+3;:::;3k 2k+2;2k+3;:::;3k f5k+1+i;0g 5k 2+?;5k 3+?;:::;4k+? 5k 2+?;5k 3+?;:::;4k+? Table 4.1: Edges of di erences in B0 when is as large as possible for ?2f2;3gand m = 1 If m = 2, = 2, and ? = 2, then =5 = 2k 1 and j2B0j= 2k 2, so we must create one more 5-cycle constructed from di erences. To account for this, form the 70 set of 5-cycles B = 2fci +jji2Zk 1;j2Zv;ci2B0g[fc+jjj2Zvg where B0 is de ned in Equation (4.1) and c = ( (0;1;2;2k + 3;2k + 1) if k 1 0;1 (mod 4), and (0;2k;2k + 1;1;2) if k 1 2;3 (mod 4). The 5-cycle c uses the di erences 1, 1, 2, 2k + 1, and 2k + 1 if k 1 0;1 (mod 4) and the di erences 1, 1, 2, 2k, and 2k if k 1 2;3 (mod 4). If m = 4, = 2, and ? = 3, then =5 = 4k 1 when is as large as possible and j4B0j = 4k 4, so we must construct three more 5-cycles using di erences. In this case form the set of 5-cycles B = 4fci +jji2Zk 1;j2Zv;ci2B0g[fc0i (mod 2) +jj j2Zv;i2Z3g where B0 is de ned in Equation (4.1) and c0i = 8 >< >: (0;1;2k + 2;4k + 3;4k + 1) if i = 0 and k 1 0;1 (mod 4), (0;1;4k + 2;2k + 2;2) if i = 0 and k 1 2;3 (mod 4), and (0;1;2;4k + 3;4k + 1) if i = 1. (4.2) Notice that c00 is repeated twice in B so that if k 1 0 or 1 (mod 4) thenfc0i (mod 2) j i2Z3guses three copies of the di erence 2 and four copies of each of the di erences 1;2k+ 1; and 4k+ 1 and if k 1 2 or 3 (mod 4) thenfc0i (mod 2) ji2Z3guses three copies of the di erence 2 and four copies of each of the di erences 1;2k; and 4k + 1. If m = 7, = 1, and ? = 3, then =5 = 7k 1, and j7B0j = 7k 7, and so we need to construct six more 5-cycles using di erences. Under these conditions form the set of 5-cycles B = 7fci +jji2Zk 1;j2Zv;ci2B0g[3fc00 +jjj2Zvg[fc01 +jjj2Zvg [2fc02 +jjj2Zvg where B0 is de ned in Equation (4.1), c00 and c01 are de ned as in Equation (4.2), and c02 = (0;1;4k + 3;8k + 4;4k + 2). The 5-cycles c00;c01 and c02 in B use four copies of di erence 2, six copies of the di erence 4k+ 2, seven copies of both of the di erences 1 and 4k + 1, and six copies of the di erence 2k + 1 or the di erence 2k if k 0 or 1 (mod 4) or k 2; or 3 (mod 4) respectively. Now suppose ?2f7;8g. Let P =f(xi;yi)j1 i k;yi >xig be the collection of pairs from a Skolem sequence or hooked Skolem sequence of order k for the set f1;2;:::;2kg or f1;2;:::;2k + 1g, if k 0 or 1 (mod 4) or k 2 or 3 (mod 4) respectively. De ne B0 =fci 1 = (0;xi;xi yi;3k + 2;5k + 4 +i)j1 i k;(xi;yi)2Pg (4.3) where computations are done modulov. So form = 1 or (m; ;?)2f(2;6;8);(3;4;8)g, form the set of 5-cycles B =fci +jji2Z =5;ci (mod k) 2B0;j2Zvg. Table 4.2 lists the di erences of edges that occur in cycles in B when is as large as possible ( 71 is as small as possible). Since jmB0j = mk and =5 is k, k 2, 2k 1, or 3k when (m; ;?) is (1;1;7), (1;8;8), (2;6;8), or (3;4;8) respectively (note that if m = 1 and is as large as possible then = 1 or 8 when ? = 7 or 8 respectively), there are enough 5-cycles in mB0 to construct all of the 5-cycles with only pure edges when m = 1 or (m; ;?)2f(2;6;8);(3;4;8)g. Edges Di erenceswhenk 0;1 (mod 4) Di erenceswhenk 2;3 (mod 4) f0;xig;fxi;xi yig 1;2;:::;2k 1;2;:::;2k 1;2k+1 fxi yi;3k+2g 3k+3;3k+4;:::;4k+2 3k+3;3k+4;:::;4k+2 f3k+2;5k+4+ig 2k+3;2k+4;:::;3k+2 2k+3;2k+4;:::;3k+2 f5k+4+i;0g 5k 5+?;5k 6+?;:::;4k 4+? 5k 5+?;5k 6+?;:::;4k 4+? Table 4.2: Edges of di erences in B0 when is as large as possible for ?2f7;8gand m = 1 Now suppose m = 4, = 2, and ? = 8. Since =5 = 4k + 1 and j4B0j= 4k, we need to construct one more 5-cycle constructed from di erences. So we form the set of 5-cycles B = 4fci+jji2Zk;j2Zv;ci2B0g[f(0;4k+3;2k+1;6k+4;8k+6)+jjj2Zvg where B0 is de ned in Equation (4.3) and computations are done modulo v and (0;4k + 3;2k + 1;6k + 4;8k + 6) uses the di erences 2k + 2, 2k + 2, 2k + 2, 4k + 3, and 4k + 3. To de ne C, let ?2f2;3;7;8g. By Lemma 4.2.1, if v is odd or both v and m are even then 3 divides (m(v 1)=2 ) and if v is even and m is odd then 3 divides (m(v 1)=2 3=2). So form a partition P0 from the di erences not used to form B into (m(v 1)=2 )=3 sets of size 3 (not multisets) when either v is odd or both v and m are even, and form a partition P0 from the di erences not used to form B into (m(v 1)=2 3=2)=3 sets of size 3 (not multisets) and one setfd;v=2gof size 2 with d6= v=2 when v is even and m is odd; this ensures that d1 < >: ? if = 0, f(0;1;4;2;6) +jjj2Zvg if = 5, and f(0;1;4;2;6) +jjj2Zvg[f(0;1;4;2;6) +jjj2Zvg if = 10, and let = ?;f1;2;3;4;6g, or f1;1;2;2;3;3;4;4;6;6g when = 0;5; or 10 respec- tively. By Lemma 4.2.1, jD(v) 2n j 0 (mod 3). Notice that if v = 7, m = 2, and max(7;2) = 2, then = 0 and if v = 8 and m = 2 then there are no 5{CSs of ( +m)Kv+1 Kv by Lemma 4.1.1(a-d), so these 5-cycles in B can be constructed. Form C using Equation (4.4) when either v is odd or both v and m are even and using Equation (4.5) when v is even and m is odd. Thus (Zv[f1g;B[C) is a 5{CS of ( + 2)Kv+1 Kv for v 2;3;7; or 8 (mod 10) and = max(v;m). Let m = 3 and = max(v;3) = v 4. It follows that = 0 for all k, so de ne B = ?. Form C using Equation (4.4) when either v is odd or both v and m are even and using Equation (4.5) when v is even and m is odd. Therefore (Zv[f1g;B[C) is a 5{CS of ( +3)Kv+1 Kv for v 2;3;7; or 8 (mod 10) with = max(v;3). 4.3 5{CSs of ( +m)Kv+1 Kv: The Main Result In the following theorem, Lemma 4.2.3 is used as a basis for an inductive argu- ment to settle the problem of constructing a 5{CS of ( +m)Kv+1 Kv. Theorem 4.3.1. Let m 1. There exists a 5{CS of ( +m)Kv+1 Kv if and only if (a) ( +m) +m(v 1) 0 (mod 2), (b) v( +m) 0 (mod 2), (c) m v2 +v( +m) 0 (mod 5), and (d) m(v 1) 3( +m). Proof. The necessity follows from Lemma 4.1.1, so we now prove the su ciency. If = 0 then by Condition (a), mv 0 (mod 2) and by Condition (c), mv(v+1)=2 0 (mod 5); so by Theorem 1.2.2 there exists a 5{CS of mKv+1. So we can also assume that 1. By Condition (d), v62f1;2;3;4g, so we know v 5. By Theorem 2.3.2, there exists a 5{CS of ( + m)Kv+1 Kv for v6 2;3;7 or 8 (mod 10), and so we can assume v 2;3;7 or 8 (mod 10). Let V be the vertex set of Kv and U contains the other vertex in ( +m)Kv+1. First we establish that for any given v, the di erence between consecutive val- ues of that satisfy Conditions (a-c) is a constant; call this di erence di (v). Lemma 4.2.2 establishes this claim and shows that di (v) = 10. Secondly, for all m 1 and v 5, we will show there exists a 5{CS of ( + m)Kv+1 Kv for both 73 the smallest and the largest values of satisfying all of the conditions. Finally for all m 1 and v 5 it will be shown that for all satisfying Conditions (a-d) there exist non-negative integers 1, 2 with 1 + 2 = and positive integers m1;m2 with m1 + m2 = m such that there exists a 5{CS of ( i + mi)Kv+1 iKv for i2f1;2g. So the union of these two 5{CSs completes the proof. We turn to the second step in the proof; establishing the existence of the 5{CS for the smallest and largest values of given v and m. Beginning with the smallest value, Table 4.3 lists the values of min(v;m) using Theorem 1.2.2 and Lemma 4.2.3. Four cases are considered in turn based on the value of v. m (mod 10) v (mod 10) 1 2 3 4 5 6 7 8 9 0 2 6 2 8 4 0 6 2 8 4 0 3 3 6 9 2 5 8 1 4 7 0 7 1 2 3 4 5 6 7 8 9 0 8 8 6 4 2 0 8 6 4 2 0 Table 4.3: List of min(v;m) values Suppose v 2 (mod 10). By Lemma 4.2.3 a 5{CS of ( min(v;m) + m)Kv+1 ( min(v;m))Kv exists for m = 1 and 2. From examining Table 4.3 it is easy to see that the union of ( min(v;m0) +m0)Kv+1 ( min(v;m0))Kv and ( min(v;m00) +m00)Kv+1 ( min(v;m00))Kv where m0 = 1 and m00 = 2 or m0 = 2 and m00 = 2 form a 5{CS of ( min(v;m) + m)Kv+1 ( min(v;m))Kv where m = 3 or 4 respectively. Now we can form a 5{CS of ( min(v;5) + 5)Kv+1 ( min(v;5))Kv by taking the union of ( min(v;2) + 2)Kv+1 ( min(v;2))Kv and ( min(v;3) + 3)Kv+1 ( min(v;3))Kv: We will revisit what happens when m > 5 after we examine when v 8 (mod 10) and m 5 Suppose v 8 (mod 10). It follows by Lemma 4.2.3 that a 5{CS of ( min(v;m)+ m)Kv+1 ( min(v;m))Kv exists for m 4. By Theorem 2.3.2, there exists a 5{CS of ( min(v;5) + 5)Kv+1 ( min(v;5))Kv: Now suppose v 2 or 8 (mod 10). By using the 5{CS of 5Kv+1 (which exists by Theorem 1.2.2) we will generate the remaining 5{CS for m 6 when = min(v;m) using induction on m. Suppose for some m 6 and for all s with 1 s < m 74 there exists a 5{CS of (( min(v;s) +s)Kv+1 ( min(v;s))Kv. Since min(v;m 5) = min(v;m) and there exists a 5{CS (V [U;B1) of ( min(v;m 5) +m 5)Kv+1 ( min(v;m 5))Kv and a 5{CS (V[U;B2) of 5Kv+1, it follows that there exists a 5{CS (V[U;B1[B2) of (( min(v;m 5) +m 5) + 5)Kv+1 ( min(v;m 5))Kv = ( min(v;m) +m)Kv+1 ( min(v;m))Kv: Suppose v 3 (mod 10). By Lemma 4.2.3 we have established the existence of a 5{CS of ( min(v;m) + m)Kv+1 ( min(v;m))Kv for m2f1;4;7g. So by taking the union of particular copies of these 5{CSs, we can form a 5{CS of ( min(v;m) + m)Kv+1 ( min(v;m))Kv for m 2 f2;5;8g. Since we can build a 5{CS of ( + m)Kv+1 Kv in the case when is as small as possible and m2f1;2;4;5;7;8g, we can form a 5{CS of ( min(v;m) + m)Kv+1 ( min(v;m))Kv for m2f3;6;9;10g by taking the union of 2 particular copies of the 5{CSs we have already constructed. We will revisit what happens when m> 10 after we examine when m 10 and v 7 (mod 10). Suppose v 7 (mod 10). Then by Lemma 4.2.3, we can form a 5{CS of ( min(v;1) + 1)Kv+1 ( min(v;1))Kv. So by using successive copies of this 5{CS, we can form a 5{CS of ( min(v;m) +m)Kv+1 ( min(v;m))Kv for 2 m 10. Now suppose v 3 or 7 (mod 10). We will use induction on m in this proof to construct the remaining 5{CSs. As before, we use the existence of a 5{CS of 10Kv+1 (which exists by Theorem 1.2.2) and a 5{CS of ( min(v;m)+m)Kv+1 ( min(v;m))Kv for m 10 to assist constructing larger 5{CSs. So suppose for some m 11 and for all s with 1 s < m, there exists a 5{CS of ( min(v;s) + s)Kv+1 ( min(v;s))Kv. Since there exists a 5{CS (V [U;B1) of ( min(v;m 10) +m 10)Kv+1 ( min(v;m 10))Kv; since there exists a 5{CS (V[U;B2) of 10Kv+1, and since min(v;m 10) = min(v;m), it follows that there exists a 5{CS (V [U;B1 [B2) of ( min(v;m) + m)Kv+1 ( min(v;m))Kv: We now turn to constructing a 5{CS of ( +m)Kv+1 Kv where = max(v;m). The proof of this case will be done using induction on m. By Lemma 4.2.3, there exists a 5{CS of ( max(v;m)+m)Kv+1 ( max(v;m))Kv for m2f1;2;3g. Suppose for some m 4 and for all s with 1 s 1, and 2 f min(v;m); max(v;m)g. It is left to show that there exists a 5{CS of ( +m)Kv+1 Kv for m > 1 and min(v;m) < < max(v;m). Tables 4.4 and 4.5 were formed using Theorem 1.2.2 and Lemma 4.2.3. These tables will be instrumental in showing that we can use smaller 5{CSs to form larger 5{CSs. Suppose for some m > 1 and for all s with 1 s 0 and u(u 2)=4 b3 if 7u 6(2 +v) 0, a2 = ( 0 if 7u 6(2 +v) > 0 and u( 7u+ 6(2 +v))=20 +b3 if 7u 6(2 +v) 0, b1 = ( u(2v +u+ 4)=40 b3=2 if 7u 6(2 +v) > 0 and u(2u v 2)=10 b3 if 7u 6(2 +v) 0, (5.4) b2 = ( u(7u 6(2 +v))=40 b3=2 if 7u 6(2 +v) > 0 and 0 if 7u 6(2 +v) 0, b3 = ( u=2 if u 0 (mod 4) and 0 otherwise. For the rest of the chapter, let a1, a2, b1, b2, and b3 be de ned as in (5.4). The following lemma will be useful for showing that a1, a2, b1, and b2 satisfy the conditions that will become vital in Lemma 5.3.2. Lemma 5.3.1. Suppose that 5 (mod 10), that v=2 + 1 u < 3v + 1, and that , v, and u satisfy Condition (d) of Lemma 5.2.1. Then (A) a1, a2, b1, and b2 are non-negative, (B) a1, a2, b1, and b2 are each divisible by u=2, and (C) a1=(u=2) and a2=(u=2) are even. Proof. Let = 10k3+5 so then by Lemma 5.2.1(d) we can let u = 2k1 and v = 2k2+1. First suppose that 7u 6(2 + v) > 0. Then a1 0 since u < 3v + 1 in this lemma, and a2 = 0. By de nition, b1 = u(2v +u+ 4)40 b32 u(2v +u+ 4)40 u4 = u( (2v +u+ 4) 10)40 0: 83 V A1 U0 U1 V A2 U0 U1 V B1 U0 U1 V B2 U0 U1 V B3 U0 U1 Figure 5.2: Possible 5-cycle Types when 5 (mod 10) and u< 3v + 1 Since u> (6v + 12)=7 and (6v + 13)=7 is never an even integer, u (6v + 14)=7 and so b2 u( (7u 6(2 +v)) 10)40 (6v + 14)( ((6v + 14) 6(2 +v)) 10)280 = (3v + 7)( 5)70 0: So Condition (A) is satis ed. By de nition a1 = 2k1(3k2 k1 + 2)(2k3 + 1); b1 = k1(2k2 +k1 + 3)(2k3 + 1)=2 b3=2;and b2 = k1(7k1 6k2 9)(2k3 + 1)=2 b3=2: Clearly, a1 and a2 = 0 are divisible by u=2 = k1 and both a1=(u=2) = 2a1=u = a1=k1 and 2a2=u are even, so (C) is satis ed. If b3 = 0 then k1 is odd and so 2b1=u = b1=k1 and 2b2=u = b2=k1 are integers. If b3 = u=2 then u 0 (mod 4) and k1 is even, so 2b1=u = (2v +u+ 4)20 b3u = (2k2 +k1 + 3)(2k3 + 1)2 12 = 1 +k2 + 3k3 + 2k2k3 + k1(2k3 + 1)2 84 and 2b2=u = (7u 6(2 +v))20 b3u = (7k1 6k2 9)(2k3 + 1)2 12 = k1(14k3 + 7)2 9k3 3k2(2k3 + 1) 5: So it follows that 2b1=u and 2b2=u are integers and thus Condition (B) is satis ed. Finally, suppose that 7u 6(2 + v) 0. It is clear by (5.4) that a1, a2, and b2 are non-negative. Since v is odd, u6= v=2 + 1 and thus u v=2 + 3=2. So if b3 = u=2 then b1 (v + 3)(2(v=2 + 3=2) v 2)20 v + 34 = ( 5)(v + 3)20 0; and so b1 is non-negative. If b3 = 0 then it is clear that b1 is non-negative. Since u=2 = k1 and since a1 = 5k1(k1 1)(2k3 + 1) b3; a2 = k1(6k2 7k1 + 9)(2k3 + 1) +b3; and b1 = k1(4k1 2k2 3)(2k3 + 1) b3; it follows that Condition (B) is satis ed. If b3 = u=2 then k1 is even and so 2a1=u = a1=k1 = 5(k1 1)(2k3 + 1) 1 is even. If b3 = 0 then k1 is odd and so 2a1=u = 5(k1 1)(2k3+1) is even. If b3 = u=2 then k1 is even and so 2a2=u = (6k2+9 7k1)(2k3+1)+1 is even. If b3 = 0 then k1 is odd and so 2a2=u = (6k2 + 9 7k1)(2k3 + 1) is even; thus Condition (C) is satis ed. The next lemma will cover one of the cases of Theorem 5.4.1 using a slightly di erent technique to construct the 5-cycles from the methods used so far. Lemma 5.3.2. Suppose that 5 (mod 10), that v=2 + 1 u < 3v + 1, and that , v, and u satisfy Condition (d) of Lemma 5.2.1. Then there exists a 5{CS of Kv+u Kv. Proof. By Lemma 5.2.1(d), u is even and v is odd. Let U = Zu=2 Z2 be the vertex set of Ku. Let V = f1i j i 2 Zvg be the vertex set of Kv. For i 2 Z2 let Di = D(u=2) nSi where Si =fu=4g if u 0 (mod 4) and Si = ? if u 2 (mod 4). Let D2 = Zu=2 nS2 where S2 = 2fu=4g if u 0 (mod 4) and S2 = ? if u 2 (mod 4). Note that D0[S0, D1[S1, and D2[S2 represent all of the Type 0, 1 and 2 di erences respectively in Ku and will be used to keep track of the edges in Ku as we decompose the edges of Kv+u Kv into 5-cycles. The aim of this construction will be to form a1, a2, b1, b2, and b3 5-cycles of Type A1,A2,B1,B2, andB3 respectively which will be shown to decompose Kv+u Kv 85 into 5-cycles. By Lemma 5.3.1, a1, a2, b1, b2, and b3 are non-negative integers. For each i2Z2a1=u+2a2=u de ne si = 8 >< >: (i;i+ 1) if i is even and i 0 and v 2b2=u 2 (u 2) 2 2b3 u + ( 7u+6(2+v)) 10 + 2b3 u if 7u 6(2 +v) 0, = (2u v 2)=5 2b3=u = (2=u)( u(2u v 2)=10 b3) = 8< : 2 u u((7u 6v 12)+(2v+u+4)) 40 b3 (use this expression if 7u 6(2 +v) > 0) 2 u u(2u v 2) 10 b3 + 0 (use this expression if if 7u 6(2 +v) 0), = 2b1=u+ 2b2=u =jTj: If r = 2a1=u + 2a2=u and r < v( 1)=2, then clearly at most 1 ordered pairs in fsiji2Z2a1=u+2a2=ug contain x for all x2Zv. Suppose that r = v( 1)=2 so that r 2a1=u+ 2a2=u. If we can show that v=2 > 2a1=u+ 2a2=u r then for all x2Zv, 1 ordered pairs in fsiji2Zrg contain x and at most 1 ordered pair in fsiji2Z2a1=u+2a2=unZrgcontain x (to be precise, n(x) = if x 2(2a1=u+2a2=u r) and n(x) = 1 otherwise); so it follows that for all x2Zv 1, n(x) 0 and that n(v 1) 2b3=u 0. So if r = v( 1)=2 then v 2 +r 2a1 u 2a2 u = v 2 2a1 u 2a2 u = 8 < : v 2 (3v u+1) 5 + 2(0) u if 7u 6(2 +v) > 0 and v 2 (u 2) 2 2b3 u + (6(v+2) 7u) 10 + 2b3 u if 7u 6(2 +v) 0, = (5 v 2 (3v u+1) 10 if 7u 6(2 +v) > 0 and5 v 5 (u 2) (6v+12 7u) 10 if 7u 6(2 +v) 0, = (2u v 2)10 > 0; The last inequality follows from u v=2 + 1 and v is odd. Therefore n(x) 0 if x2Zv 1 and n(v 1) 2b3=u 0. We will now de ne the sets of 5-cycles that will form our desired 5{CS. Let p1 = p3 = 1 and p2 = 0 if Ti T0 and p1 = 0 and p2 = p3 = 1 if Ti T00. Then de ne C0 =f(1t1;(0;i);(qi;i+ 1);1t2;(qi + 1;i+ 1)) + (j;j)ji2Z2a2=u; f(si) =f(0;i);(qi;i+ 1)g;j2Zu=2;si = (t1;t2)g; C1 =f(1t1;(0;t);(qi;t);1t2;(0;t+ 1)) + (j;j)ji2ZrnZ2a2=u; f(si) =f(0;t);(qi;t)g;j2Zu=2;si = (t1;t2)g; C2 =f(12i;(0;t);(qi;t);12i+1;(0;t+ 1)) + (j;j)ji2Z2a1=u+2a2=u r; 87 f(si) =f(0;t);(qi;t)g;j2Zu=2g; C3 =f(1i;(0;0);(d1;p1);(d1 d2;p2);(d1 d2 +d3;p3)) + (j;j)ji2Zv; fd1;d2;d3g2Ti;j2Zu=2; if Ti T0 then d2 is uniqueg; and C4 = 8 >< >: ? if b3 = 0, and f((0;0);(v=4;0);(0;1);1v 1;(v=4;1)) + (j;j)jj2Zu=2g if b3 = u=2, [f((0;1);(v=4;1);(0;0);1v 1;(v=4;0)) + (j;j)jj2Zu=2g where calculations are done modulo v (including indicies). So C0 is a set of TypeA2 5-cycles, C1[C2 is a set of Type A1 5-cycles, C3 is a set of Type B1 and B2 5-cycles (depending on whether Ti T0 or Ti T00 respectively), and C4 is a set of Type B3 5-cycles. Since every di erence in D0 [S0, D1 [S1, and D2 [S2 represents every edge in Ku, it follows that C0 [C1 [C2 [C3 [C4 decomposes the edges in Ku into 5-cycles. It remains to show that each vertex in U is joined to each vertex in V times. By Lemma 5.3.1, 2a2=u is even, so by de nition of si, each 1i in V is adjacent to every vertex in U the same number of times, though 1i may not be joined to every vertex in U the same number of times as 1j. To be precise, 1i is adjacent to every vertex in U n(i) times. Since jTij = n(i) for i < v 1 and jTv 1j = n(v 1) 2b3=u, it follows that in C3,1i is adjacent to each vertex in U n(i) times for i xig be the collection of pairs from a Skolem sequence or hooked Skolem sequence of order k for the setf1;2;:::;2kgorf1;2;:::;2k+1gif k 0 or 1 (mod 4) or k 2 or 3 (mod 4) respectively (see Theorems 1.1.1 and 1.1.2). If ? = 8 then let t1 = 1 and let t1 = 0 otherwise. If ? = 9 then let t2 = 1 and let t2 = 0 otherwise. Then let B0 =fci 1 = (0;xi;xi yi;3k 1+b?=2c t1;5k+i+b?=2c+t2)j1 i k;(xi;yi)2Pg: Table 5.1 lists the di erences of edges that occur in 5-cycles in B0 when is as large as possible ( is as small as possible). Notice that jB0j= k =5 = (10k+? 3v 89 1)=10 if ? 7 or v 3. If v = 2 and ?2f8;9g, then =10 and =5 more 5-cycles using di erences need to be constructed when ? = 8 and 9 respectively. To account for this, form the set of 5-cycles B =fci+jjj2Zu;i2Zt01;ci (mod k) 2B0g[t02fc+jjj2Zug where t01 = min(f k; =5g), t02 = max(f0; =5 kg) and c = 8 >< >: (0;2k + 1;4k + 2;6k + 4;4k + 3) if ? = 8 and k 0;1 (mod 4), (0;2k;6k + 3;4k + 3;6k + 5) if ? = 8 and k 2;3 (mod 4), and (0;2k + 2;4k + 4;6k + 6;3k + 3) if ? = 9. Since v 2 and 5 k = (u 3v 1) 10 k = k + ?10 k (3v + 1)10 = (? 3v 1)10 ; it follows that the number of times c is copied is no more than =10 or =5 times if ? = 8 or 9 respectively. So we have enough copies of the di erences to construct c. Suppose ? = 0. Let P0 = f(x0i;y0i) j 0 i k 3;y0i > x0ig be the collection of pairs from a Skolem sequence or hooked Skolem sequence of order k 2 for the set f1;2;:::;2k 4g or f1;2;:::;2k 3g if k 2 0 or 1 (mod 4) or k 2 2 or 3 (mod 4) respectively. If k 2 0 or 1 (mod 4) then name the Skolem pairs so that (x0k 3;y0k 3) contains 2k 3. De ne P = f(xi = x0i + 3;yi = y0i + 3) j (x0i;y0i) 2P0g; notice that 2k 2fxk 3;yk 3g when k 2 0 or 1 (mod 4). To simplify how the 5-cycles are de ned, let z =b =2c. Then with c0i = (0;xi;xi yi;3k;5k + 2 +i) and ci = 8 >>>> >>> >>>> >>> >>< >>>> >>> >>>> >>> >>: (0;1;3;2k + 4;2k + 1) if i = 1 and k 2 0;1 (mod 4), (0;1;3;3k + 3;3k) if i = 1 and k 2 2;3 (mod 4), (0;3k;6k;k + 1;5k + 1) if i = 2 and k 2 0;1 (mod 4), (0;2k;6k 1;k;5k 1) if i = 2 and k 2 2;3 (mod 4), (0;1;2;5;3) if 3 i z + 1, (0;2;2k + 3;7k + 2;5k + 1) if z + 2 i 2z and k 2 0;1 (mod 4), (0;2;2k + 2;7k + 1;5k + 1) if z + 2 i 2z and k 2 2;3 (mod 4), (0;3k;6k;2k + 1;6k + 1) if 2z + 1 i 3z 1, and c0i 3z (mod k 2) if 3z i (k 2) + 3z 1, form the set of 5-cycles B0 = fc00i 1 = ci j 1 i (k 2) + 3z 1;(xi;yi) 2Pg. Notice that when = 2, ci will never be any of the following 5-cycles: (0;1;2;5;3), (0;2;2k+3;7k+2;5k+1), (0;2;2k+2;7k+1;5k+1), or (0;3k;6k;2k+1;6k+1). So when k> 2 we form the set of 5-cycles B =fc00i +jji2Zb =5c;j2Zu;c00i 2B0g[E 90 Edges Di erences when k 0;1 (mo d4) Di erences when k 2;3 (mo d4) f0; xig ;fx i;x i yig 1;2 ;:: :;2 k 1;2 ;:: :;2 k 1;2 k+ 1 fxi y i;3 k 1+ b?= 2c t1g if? 6=8 3k +b ?=2 c;3 k+ 1+ b?= 2c; ::: ;4k 1 +b ?=2 c 3k +b ?=2 c;3 k+ 1+ b?= 2c; ::: ;4k 1 +b ?=2 c fxi y i;3 k 1+ b?= 2c t1g if? =8 3k +3 ;3k +4 ;:: :;4 k+ 2 3k +3 ;3k +4 ;:: :;4 k+ 2 f3k 1 +b ?=2 c t1;5 k+ i+ b?= 2c+ t2g if? 7 2k +2 ;2k +3 ;:: :;3 k+ 1 2k +2 ;2k +3 ;:: :;3 k+ 1 f3k 1 +b ?=2 c t1;5 k+ i+ b?= 2c+ t2g if? 8 2k +3 ;2k +4 ;:: :;3 k+ 2 2k +3 ;2k +4 ;:: :;3 k+ 2 f5k +i +b ?=2 c+ t2;0 gif ?6= 9 5k 1 +d ?=2 e;5 k 2+ d?= 2e; ::: ;4k +d ?=2 e 5k 1 +d ?=2 e;5 k 2+ d?= 2e; ::: ;4k +d ?=2 e f5k +i +b ?=2 c+ t2;0 gif ?= 9 5k +3 ;5k +2 ;:: :;4 k+ 4 5k +3 ;5k +2 ;:: :;4 k+ 4 Table 5.1: Edges of di erences in B0 when is as large as possible for ? 4and ?6= 5 91 where computations are done modulo u and where E = 8 >>> >>> < >>> >>> : ? if 0 (mod 5), 2 if 1 (mod 5), 1[ 2 if 2 (mod 5), 3 if 3 (mod 5), and 2[ 3 if 4 (mod 5). Since 5 = (10k 3v 1) 2 10 = k (3v + 1) + 2 10 k 7 10 ; sincejB0j= 2k 2 if = 2, and sincejB0j= (k 2)+3z (k 2)+3( =2 1=2) = k =2 3=2 if > 2, it follows that b( )=5c jB0j, so we have enough 5- cycles to construct the Type C 5-cycles. Notice that if v = 2 and < 8, then 6 2 (mod 5). Fortunately, when is as large as possible then either 6 2 (mod 5) or d =5exig be the collection of pairs from a Skolem sequence or hooked Skolem sequence of order k 1 for the set f1;2;:::;2k 2g or f1;2;:::;2k 1g if k 1 0 or 1 (mod 4) or k 1 2 or 3 (mod 4) respectively. Then let B0 =fci 1 = (0;xi;xi yi;3k;5k +i)j1 i k 1;(xi;yi)2Pg: Table 5.3 lists the di erences of edges that occur in cycles in B0 when is as large as possible ( is as small as possible). Since =5 < k and jB0j= (k 1) we need to form more 5-cycles constructed from di erences. (Note that by Conditions (b-d), must be even since u is odd.) To account for these 5-cycles, form the set of 5-cycles B =fci+jji2Zx1;j2Zu;ci (mod k 1) 2B0g[x2fc00+jjj2Zug[x3fc01+jjj2Zug where x1 = min(f =5; (k 1)g), x2 = max(f0;b( =5 (k 1))=2cg), x3 = max(f0;d( =5 (k 1))=2eg), and where c0i = 8 >>> < >>> : (0;2k + 1;4k;2k;6k); if ? = 1, k 0;1 (mod 4), and i2Z2, (0;2k 2;4k 2;2k;4k) if ? = 1, k 2;3 (mod 4), and i = 0, (0;2k + 1;4k + 2;8k + 2;4k + 1) if ? = 1, k 2;3 (mod 4), and i = 1, and (0;2k;4k + 1;1;4k + 2) if ? = 3 and i2Z2. Since v 2 and 5 (k 1) 2 = (u 3v 1) 10 (k 1) 2 = k + (? 3v 1)10 k2 2 = k2 + (? 3v 6)10 < k2 there are enough copies of the di erences to construct c0i. Suppose ? = 2. Let P0 = f(x0i;y0i) j 0 i k 2;y0i > x0ig be the collection of pairs from a Skolem sequence of order k 1 for the set f1;2;:::;2k 2g or 93 Edges Di erenceswhenk 1 0;1 (mod 4) Di erenceswhenk 1 2;3 (mod 4) f0;xig;fxi;xi yig 1;2;:::;2k 2 1;2;:::;2k 3;2k 1 fxi yi;3kg 3k+1;3k+2;:::;4k 1 3k+1;3k+2;:::;4k 1 f3k;5k+ig 2k+2;2k+3;:::;3k 2k+2;2k+3;:::;3k f5k+i;0g 5k 1+d?=2e;5k 2+d?=2e;:::; 5k 1+d?=2e;5k 2+d?=2e;:::;4k+1+d?=2e 4k+1+d?=2e Table 5.3: Edges of di erences in B0 when is as large as possible for ?2f1;3g f1;2;:::;2k 1g if k 1 0 or 1 (mod 4) or k 1 2 or 3 (mod 4) respectively. De ne P =f(xi = x0i + 1;yi = y0i + 1)j(x0i;y0i)2P0g. Then with ci = 8> >>< >>>: (0;xi;xi yi;3k + 1;5k +i+ 1) if 0 i k 2, (0;1;3k + 1;7k + 2;4k + 1) if i = k 1 and k 1 0;1 (mod 4), (0;1;2k + 1;5k + 1;2k) if i = k and k 1 0;1 (mod 4), and (0;1;2k;6k + 1;3k + 1) if i = k 1 and k 1 2;3 (mod 4), let B0 =fc0i = ci (mod k 1) ji2Z (k 1);(xi;yi)2Pg [fc0i = ck 1 j (k 1) i (k 1) +b =2c 1g [fc0i = ckj (k 1) +b =2c i (k 1) + 2b =2c 1g if k 1 0 or 1 (mod 4) or let B0 =fc0i = ci (mod k 1) ji2Z (k 1);(xi;yi)2Pg[fc0i = ck 1 j (k 1) i kg if k 1 2 or 3 (mod 4). Since jB0j (k 1) + 2b =2c 1 k 2 and =5 k =2 we have enough 5-cycles to form the appropriate number of 5-cycles of Type C. Table 5.4 lists the di erences of edges that occur in 5-cycles in B0 when is as large as possible ( is as small as possible). Then form the set of 5-cycles B =fc0i + jji2Z =5;j2Zu;c0i2B0g. If k = 0 then it is impossible to construct a 5-cycle. Edges Di erenceswhenk 1 0;1 (mod 4) Di erenceswhenk 1 2;3 (mod 4) f0;xig;fxi;xi yig 2;3;:::;2k 1 2;3;:::;2k 2;2k fxi yi;3k+1g 3k+2;3k+3;:::;4k 3k+2;3k+3;:::;4k f3k+1;5k+i+1g 2k+1;2k+2;:::;3k 1 2k+1;2k+2;:::;3k 1 f5k+i+1;0g 5k;5k 1;:::;4k+2 5k;5k 1;:::;4k+2 ci ifi=k 1;3k;3k+1;4k+1;4k+1 1;2k 1;3k;3k+1;4k+1 ci ifi=k+1 1;2k;2k;3k;3k+1 Table 5.4: Edges of di erences in B0 when is as large as possible for ? = 2 Suppose ? = 5. Let P0 = f(x0i;y0i) j 1 i k 2;y0i > x0ig be the collection of 94 pairs from a Skolem sequence or hooked Skolem sequence of order k 2 for the set f1;2;:::;2k 4g or f1;2;:::;2k 3g if k 2 0 or 1 (mod 4) or k 2 2 or 3 (mod 4) respectively. De ne P =f(xi = x0i + 3;yi = y0i + 3)j(x0i;y0i)2P0g. Let ci = ( (0;xi;xi yi;4k + 2;7k + 3 i) if 1 i k 2, and (0;3k + 1;6k + 3;k + 2;5k + 3) if i = k 1, and B0 = fc0i 1 = ci j 1 i k 1;(xi;yi) 2 Pg. Table 5.4 lists the di erences of edges that occur in cycles in B0 when is as large as possible ( is as small as possible). Let S be de ned as in Equation (5.5) and let w1 = min(f (k 1);b =5cg) and w2 = max(f0;b =5c (k 1)g). So when k 1 we form the set of 5-cycles B =fc0i +jji2Zw1;j2Zu;c0i (mod k) 2B0g[w2fs+jjs2S;j2Zug[E where computations are done modulo u. Table 5.5 lists di erences of edges in the 5-cycles in B0 when is as large as possible. Since b =5c< k and since j 5 k (k 1) = (u 3v 1) 10 (k 1) = k + 4 3v10 + k = + 4 3v 10 1; it follows that E can be constructed and there are enough copies of the di erences 1, 2, 3, u=5, and 2u=5 in S. If k = 0 then let ci = (0;1;2;3;4) for 0 i b =2c 1 and let ci = (0;2;4;1;3) for i >b =2c 1, and so we can form the set of 5-cycles B =fci +jji2Zb =5c;j2Zv. Edges Di erenceswhenk 2 0;1 (mod 4) Di erenceswhenk 2 2;3 (mod 4) f0;xig;fxi;xi yig 4;5;:::;2k 1 4;5;:::;2k 2;2k fxi yi;4k+2g 4k+3;4k+4;:::;5k 4k+3;4k+4;:::;5k f4k+2;7k+3 ig 3k;3k 1;:::;2k+3 3k;3k 1;:::;2k+3 f7k+3 i;0g 3k+3;3k+4;:::;4k 3k+3;3k+4;:::;4k ci ifi=k 1 3k+1;3k+2;4k+1;5k+1;5k+2 3k+1;3k+2;4k+1;5k+1;5k+2 Table 5.5: Edges of di erences in B0 when is as large as possible for ? = 5 We will now construct the TypeB 5-cycles. By Lemma 5.2.2, (u 1)=2 or (u 1)=2 3v=2 is divisible by 3 when is even or odd respectively. We can form a partition P0 of the remaining di erences after constructing B into (u 1)=2 sets of size 3 when is even or into v sets fd;u=2g of size 2 with d 6= u=2 and (u 1)=2 3v=2 sets of size 3 when is odd; make sure that at most one copy of v=2 is in each set of size 3 and that there is at least one unique element in each set of size 3. These last conditions are easily met based on the di erences used to construct 95 each B. Since v in this lemma, there are enough copies of the di erence u=2 to construct the desired partition. Letfd1;i;d2;i;d3;igandfdi;u=2gdenote the ith set in P0 and let p be the number of sets of size 3 in P0. If is even then de ne C =f(d1;i;0;d3;i;d2;i +d3;i;1i (mod v)) +jjfd1;i;d2;i;d3;ig2P0 (5.6) with d1;i d2;i d3;i;j2Zug (5.7) and de ne C =f(d1;i;0;d3;i;d2;i +d3;i;1i (mod v)) +jjfd1;i;d2;i;d3;ig2P0 with d1;i d2;i d3;i;j2Zug [f(di;0;u=2;u=2 +di;1i+p (mod v)) +jjfu=2;dig2P0;j2Zu=2g when is odd. This ensures the elements of C are indeed 5-cycles. Then (Zu[ f10;:::;1v 1g;B[C) is a 5{CS of Kv+u Kv when u 3v + 1. Finally suppose u< 3v+1. If is odd then by Lemmas 5.1.1 and 5.3.2 there is a 5{CS of Kv+u Kv. So let be even. Remember that if 2;4;6; or 8 (mod 10) and u 0 (mod 5) then u v=2 + 5. So u6= 5 when 2;4;6; or 8 (mod 10). By Lemma 5.2.2, a and b are non-negative integers, u divides a, and either u divides b when u is odd or u=2 divides b when u is even. If u = 1 or 2, then it is impossible to form any 5-cycles. If u = 3 then v = 2;3; or 4. Since only Type A 5-cycles can be formed when u = 3, since there are 3 pure edges in Kv+3 Kv, and since there are 6 or 9 mixed edges when v = 2 or 3 respectively, it follows that there are not enough mixed edges to form all of the required 5-cycles, so a 5{CS cannot be formed under these conditions. When u = 3 and v = 4, de ne C =f(0;10;2;11;1) +jjj2Z3g and C0 =f(0;12;2;13;1) +jjj2Z3g: So then (Zu[f10;11;12;13g; C[ C0) is a 5{CS of K7 K4 when u< 3v+1. Suppose u2f4;5g. Then form a partition P0 of 3b=u of the di erences in D(u) into b=u sets of size 3 such that each set in P0 is f1;1;2g. Let fd1;i;d2;i;d3;ig denote the ith set of size 3 in P0 and let D = fd1;d2;:::;dsg be the remaining di erences after forming the partition P0. De ne C as in Equation (5.6) and B =f(0;di;12i 2+jP0j (mod v);di + 1;12i 1+jP0j (mod v)) +jjdi2D;j2Zug: Then (Zu[f10;11;:::;1vg;B[C) is a 5{CS of Kv+4 Kv. Suppose u = 6. Then form a partition P0 = P1[P2 of 3b=u of the di erences in D(u) into b=u sets of size 3 such that P0 does not containf2;2;2gorf3;3;3gand P2 only contains copies off1;2;3g. It is easy to ensure that P0 does not containf2;2;2g or f3;3;3g since every di erence in D(u) is available when P0 is constructed. Let fd1;i;d2;i;d3;ig denote the ith set of size 3 and D = fd1;d2;:::;dsg be the remaining 96 di erences after forming the partition P0. De ne C1 =f(0;d2;i;d1;i +d2;i;d1;i +d2;i +d3;i;1i (mod v)) +jjfd1;i;d2;i;d3;ig2P1;j2Zu; d1;i d2;i d3;ig; C2 =f(d1;i;0;d3;i;d2;i +d3;i;1i+jP1j (mod v)) +jjfd1;i;d2;i;d3;ig2P2;j2Zu;g; and B =f(0;di;12i 2+jP0j (mod v);di + 1;12i 1+jP0j (mod v)) +jjdi2D;j2Zug: Then C = C1 [C2 and so (Zu [f10;11;:::;1vg;B[C1 [C2) is a 5{CS of Kv+6 Kv. Let u 7. Let P contain the di erences used to construct E . Form a partition P0 of 3b=u di erences from D(u) nP into b=u sets of size 3 so that each set contains at most one copy of v=2 and at least one unique element. We can guarantee that such a partition can be constructed since u 7 and every di erence in D(u) nP is available at this point. Notice that 3b=u is no larger than D(u) nP . De ne C =f(d1;i;0;d3;i;d2;i +d3;i;1i (mod v)) +jjfd1;i;d2;i;d3;ig2P0 with d1;i d2;i d3;i;j2Zug[ where calculations are performed modulo u. Thus C is a set of 5-cycles. Let D = fd1;d2;:::;dsg be the remaining di erences in D(u) after partitioning 3b=u + of the di erences into P0. Then de ne B =f(0;di;12i 2+jP0j (mod v);di + 1;12i 1+jP0j (mod v)) +jjdi2D;j2Zug[E : Then (Zu[f10;:::;1v 1g;B[C) is a 5{CS of Kv+u Kv for u< 3v + 1. 97 Chapter 6 Conclusion/Future Work As a result of the work in this dissertation, we have come up with some notable conjectures that will be investigated in the future. Conjecture 6.1.1. Suppose there exists a 5{CS of Kv. If the necessary conditions in Lemma 2.1.2 are satis ed then a 5{CS of Kv can be enclosed in a 5{CS of ( +m)Kv+u when u 3. Conjecture 6.1.2. If the necessary conditions in Lemma 4.1.1 are satis ed then there exists a 5{CS of ( +m)Kv+u Kv for m 1 and u 2 Conjecture 6.1.3. Suppose there exists a 5{CS of Kv F where F is a 1-factor. Then a 5{CS of Kv F can be enclosed in a 5{CS of ( +m)Kv+u if and only if 1. ( +m)u+m(v 1) 1 0 (mod 2), 2. u2 ( +m) +m v2 +vu( +m) +v=2 0 (mod 5), 3. if u = 1, then (m(v 1) + 1) 3( +m), 4. if u = 2, then m v2 +v=2 2( +m) (v 1)( +m)=2 0, and 5. if u 3, then dvu( + m)=4e+ 2 v(m(v 1) + 1)=2 + ( + m)u(u 1)=2 where = 0 or 1 if vu( +m) 0 or 2 (mod 4) respectively. Conjecture 6.1.4. Suppose there exists a 5{CS of Kv. Then a 5{CS of Kv can be enclosed in a 5{CS of ( +m)Kv+u F where F is a 1-factor if and only if 1. ( +m)u+m(v 1) 1 0 (mod 2), 2. u2 ( +m) +m v2 +vu( +m) (v +u)=2 0 (mod 5), 3. if u = 1, then (m(v 1) 1) 3( +m), 4. if u = 2, then m v2 v=2 2( +m) (v 1)( +m)=2 0, and 5. if u 3, then dvu( + m)=4e+ 2 v(m(v 1) 1)=2 + ( + m)u(u 1)=2 where = 0 or 1 if vu( +m) 0 or 2 (mod 4) respectively. Conjecture 6.1.5. There exists a 5{CS of ( + m)Kv+u Kv F where F is a 1-factor if and only if 1. ( +m)u+m(v 1) 1 0 (mod 2), 2. ( +m)(v +u 1) 1 0 (mod 2), 3. u2 ( +m) +m v2 +vu( +m) (v +u)=2 0 (mod 5), 4. if u = 1, then (m(v 1) 1) 3( +m), 5. if u = 2, then m v2 v=2 2( +m) (v 1)( +m)=2 0, and 98 6. if u 3, then dvu( + m)=4e+ 2 v(m(v 1) 1)=2 + ( + m)u(u 1)=2 where = 0 or 1 if vu( +m) 0 or 2 (mod 4) respectively. Conjecture 6.1.6. If the necessary conditions in Lemma 2.1.2 are satis ed then a t{CS of Kv can be enclosed in a t{CS of ( +m)Kv+u when t> 5 is odd. Since it was shown in Chapter 4 when a 5{CS of ( + m)Kv+1 Kv exists by using the construction in Chapter 2, we believe that a proof of Conjecture 6.1.2 when u = 2 can be found by using the construction in Chapter 3. This will soon be investigated. The di culty in extending our work from Chapters 2 and 3 to u 3 in Con- jecture 6.1.1 can be seen from the extra work in Section 3.3 to prove Theorem 3.5.2. A trail with a very special property was constructed so as to form a 5{CS subgraph that contains all of the mixed edges of a given multiset of di erences. Unless an- other method is developed to obtain such a trail we believe that it will be extremely di cult to use the methods presented in this dissertation to solve Conjecture 6.1.1 when u = 3 or 4. There may be some hope when u 5 since Theorem 5.4.1 can be used to construct some 5{CSs of ( + m)Kv+u Kv. If there exists a 5{CS of ( + m)Kv+u ( + m)Kv+u and there exists a 5{CS of mKv, then there exists a 5{CS of ( + m)Kv+u Kv. By checking the conditions in Theorem 1.2.2 and Theorem 5.4.1, if v 1 (mod 10) or + m 0 (mod 10) then there exists a 5{CS of ( +m)Kv+u Kv. Also, if 1;3;7; or 9 (mod 10) and one of the following is true if: +m 0 (mod 5), +m 2;4;6; or 8 (mod 10) and u 0 or 1 (mod 5), or +m 1;3;7; or 9 (mod 10) and u 6 (mod 10), then there exists a 5{CS of ( + m)Kv+u Kv. Once 6 0;1;3;7; or 9 (mod 10) then the cases settled using this approach become very sparse. There may be other hope in nishing the u 5 case in Conjecture 6.1.1 since the types of 5-cycles based on the number of pure edges and mixed edges are equal for every u 5. A visual representation of these 5-cycles is given in Figure 6.1. The same comments made for Conjecture 6.1.1 can be said for Conjecture 6.1.2 since the work on the enclosing problem in this dissertation was used to construct a 5{CS of ( +m)Kv+u Kv. Following the two parts of the Alspach Conjecture stated in Section 1.2, there is a second version of the enclosing problem as described in Conjectures 6.1.3 and 6.1.4. Since having a 5{CS of Kv F or a 5{CS of ( +m)Kv+u F are di erent problems, there are two conjectures that involve a 1-regular graph as opposed to the one conjecture that involves a 1-regular graph in the Alspach Conjecture. Both of these conjectures can be extended by removing the condition that a 5{CS of Kv F or a 5{CS of Kv exists respectively. Removing this condition in Conjecture 6.1.4 will give us Conjecture 6.1.5 while removing this condition from Conjecture 6.1.3 will 99 give us Conjecture 6.1.2. Another avenue to take this research is to consider enclosing problems for t{CSs for t> 7 and t odd, as seen in Conjecture 6.1.6. Conjectures 6.1.3-6.1.5 can also be generalized to t{CSs. As long as a t-cycle can be constructed using di erences, the arguments described in this dissertation could be transferred to create constructions of other t{CSs. The hitch in this idea is that we have not explored whether a t-cycle can be constructed using Skolem sequences. There may also be options other than Skolem sequences to build the t-cycles using di erences. This too will be investigated soon. 100 V U V U V U V U V U V U V U V U Figure 6.1: All typ es of 5-cycles based on the num ber of pure and mixed edges 101 Bibliography [1] Jaromir Abrham and Anton Kotzig, Skolem sequences and additive permutations, Discrete Math. 37 (1981), no. 2-3, 143{146. [2] B. Alspach, Research problem 3, Discrete Math. 36 (1981), 333. [3] Brian Alspach and Heather Gavlas, Cycle decompositions of Kn and Kn I, J. Combin. Theory Ser. B 81 (2001), no. 1, 77{99. [4] J. Asplund, M. Keranen, and C. Rodger, Enclosings of -fold 5-cycle systems for u = 1, preprint. [5] C. A. Baker, Extended Skolem sequences, J. Combin. Des. 3 (1995), no. 5, 363{ 379. [6] J.-C. Bermond, O. Favaron, and M. Mah eo, Hamiltonian decomposition of Cayley graphs of degree 4, J. Combin. Theory Ser. B 46 (1989), no. 2, 142{153. MR 992988 (90g:05126) [7] J.-C. Bermond, C. Huang, and D. Sotteau, Balanced cycle and circuit designs: even cases, Ars Combin. 5 (1978), 293{318. [8] J.-C. Bermond and D. Sotteau, Cycle and circuit designs odd case, Contributions to graph theory and its applications (Internat. Colloq., Oberhof, 1977) (German), Tech. Hochschule Ilmenau, Ilmenau, 1977, pp. 11{32. [9] Darryn Bryant and Daniel Horsley, An asymptotic solution to the cycle decompo- sition problem for complete graphs, J. Combin. Theory Ser. A 117 (2010), no. 8, 1258{1284. [10] Darryn Bryant, Daniel Horsley, Barbara Maenhaut, and Benjamin R. Smith, Cycle decompositions of complete multigraphs, J. Combin. Des. 19 (2011), no. 1, 42{69. [11] Darryn E. Bryant, D. G. Ho man, and C. A. Rodger, 5-cycle systems with holes, Des. Codes Cryptogr. 8 (1996), no. 1-2, 103{108, Special issue dedicated to Hanfried Lenz. [12] Darryn E. Bryant and C. A. Rodger, The Doyen-Wilson theorem extended to 5-cycles, J. Combin. Theory Ser. A 68 (1994), no. 1, 218{225. 102 [13] , On the Doyen-Wilson theorem for m-cycle systems, J. Combin. Des. 2 (1994), no. 4, 253{271. [14] Darryn E. Bryant, C. A. Rodger, and Erin R. Spicer, Embeddings of m-cycle systems and incomplete m-cycle systems: m 14, Discrete Math. 171 (1997), no. 1-3, 55{75. [15] Charles J. Colbourn, Rose C. Hamm, and Alexander Rosa, Embedding, immers- ing, and enclosing, Proceedings of the sixteenth Southeastern international con- ference on combinatorics, graph theory and computing (Boca Raton, Fla., 1985). [16] Jean Doyen and Richard M. Wilson, Embeddings of Steiner triple systems, Dis- crete Math. 5 (1973), 229{239. [17] Haim Hanani, The existence and construction of balanced incomplete block de- signs, Ann. Math. Statist. 32 (1961), 361{386. [18] Charlotte Huang and Alexander Rosa, On the existence of balanced bipartite designs, Utilitas Math. 4 (1973), 55{75. [19] Spencer P. Hurd, Patrick Munson, and Dinesh G. Sarvate, Minimal enclosings of triple systems. I. Adding one point, Ars Combin. 68 (2003), 145{159. [20] Spencer P. Hurd and Dinesh G. Sarvate, Minimal enclosings of triple systems. II. Increasing the index by 1, Ars Combin. 68 (2003), 263{282. [21] Thomas P Kirkman, On a problem in combinations, Cambridge and Dublin Math. J 2 (1847), 191{204. [22] C. C. Lindner and C. A. Rodger, Design theory, second ed., Discrete Mathematics and its Applications (Boca Raton), CRC Press, Boca Raton, FL, 2009. [23] Eric Mendelsohn and Alexander Rosa, Embedding maximal packings of triples, Congr. Numer. 40 (1983), 235{247. [24] N. A. Newman and C. A. Rodger, Enclosings of -fold 4-cycle systems, Des. Codes Cryptogr. 55 (2010), no. 2-3, 297{310. [25] , Enclosings of -fold triple systems, Util. Math. 83 (2010), 149{158. [26] Edward S. O?Keefe, Veri cation of a conjecture of Th. Skolem, Math. Scand. 9 (1961), 80{82. [27] Alexander Rosa and Charlotte Huang, Another class of balanced graph designs: balanced circuit designs, Discrete Math. 12 (1975), 269{293. [28] Mateja Sajna, Cycle decompositions. III. Complete graphs and xed length cycles, J. Combin. Des. 10 (2002), no. 1, 27{78. 103 [29] James E. Simpson, Langford sequences: perfect and hooked, Discrete Math. 44 (1983), no. 1, 97{104. [30] Th. Skolem, On certain distributions of integers in pairs with given di erences, Math. Scand. 5 (1957), 57{68. [31] Douglas B. West, Introduction to graph theory, Prentice Hall Inc., Upper Saddle River, NJ, 1996. 104 Index ( +m)Kv+u Kv, 1 1-factor, 98 degH(v), 49 -fold k-cycle system, 2 _t, 49 k-cycle, 2 k-cycle system, 2 k{CS(v; ), 2 adjacent, 1 admissible, 7, 12, 19, 21, 28, 68, 69, 73 Alspach Conjecture, 6, 99 blocks, 2 closed trail system, 33{37 complete, 3 component, 37, 42, 44 connected, 2, 33, 42 cycle, 2 cycle system, 1, 9, 32, 78 decomposition, 2 degree, 2, 9, 10, 49, 50, 67, 79 Doyen-Wilson theorem, 8 edge, 1 embedded, 3, 7, 8, 78 enclosed, 3, 9, 98 rst He ter di erent problem, 6 graph, 1, 2, 4, 5, 9, 11 -fold complete, 1 complete, 1 multigraph, 1 regular, 2 simple, 1 Hamilton cycle, 2, 28 hook, 4 immersed, 3 incident, 1, 28 multigraph, 1, 28, 49 path, 2, 16, 28, 33{39, 41{46, 48{50 regular, 2 second He ter di erence problem, 6 Skolem pairs, 4, 13, 90 Skolem sequence, 4, 13, 15, 17, 18, 20, 22, 51{55, 57{61, 70, 71, 89, 90, 93, 95 extended, 4 hooked, 4, 13, 15, 17, 18, 20, 22, 51{ 55, 57{61, 70, 71, 89, 90, 93, 95 Steiner triple system, 2{5, 8 cyclic, 5 subgraph, 1, 99 trail, 2, 28, 33, 34, 36{39, 42{50, 99 closed, 2, 28, 33{36, 38, 39, 41, 42, 48{50 vertex, ii, 1{5, 9{13, 28, 33{38, 42{45, 47{ 51, 67{69, 73, 78, 79, 82, 85, 86, 88, 89 105