Maximal Sets of Hamilton Cycles in Complete Multipartite Graphs by Abigail Allen Noble A dissertation submitted to the Graduate Faculty of Auburn University in partial ful llment of the requirements for the Degree of Doctor of Philosophy Auburn, Alabama August 4, 2012 Keywords: Hamilton cycles, complete multipartite graphs Copyright 2012 by Abigail Allen Noble Approved by Chris Rodger, Chair, Don Logan Endowed Chair of Mathematics, Associate Dean for Research and Graduate Studies Dean Ho man, Professor of Mathematics and Statistics Peter Johnson, Professor of Mathematics and Statistics Abstract A set of S edge-disjoint hamilton cycles in a graph G is said to be maximal if the hamilton cycles in S form a subgraph of G such that G E(S) has no hamilton cycle. The set of integers m for which a graph G contains a maximal set of m edge-disjoint hamilton cycles has previously been determined whenever G is a complete graph, a complete bipartite graph, and in many cases when G is a complete multipartite graph. In this dissertation, some of the remaining open cases regarding complete multipartite graphs will be resolved. ii Acknowledgments I?d like to thank my adviser, Chris Rodger, for his guidance and help during my graduate studies, my family and friends for their love and support throughout my life, and Matt for his constant encouragement and faith in me. I couldn?t have done this without you guys. iii Table of Contents Abstract . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ii Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iii List of Figures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . v List of Tables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . vii 1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.1 De nitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.2 History . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.3 The Technique of Amalgamations . . . . . . . . . . . . . . . . . . . . . . . . 3 2 The p 1 (mod 4) Case . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 2.2 p 1 (mod 4) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 3 The p 3 (mod 4) Case . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 3.2 Small Cases p = 7 and p = 11 . . . . . . . . . . . . . . . . . . . . . . . . . . 11 3.3 p 7 (mod 8), p 31 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46 iv List of Figures 2.1 View of K4x+13 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 2.2 Type 2 and 3 Edges . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 3.1 Setup of three sections with edge cut depicted . . . . . . . . . . . . . . . . . . 12 3.2 Special edges in E(S) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 3.3 The Amalgamated H of G; the size of the vertex u represents the value of f(u). 13 3.4 Ci = Pi[Qi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 3.5 Setup of three sections with edge cut depicted . . . . . . . . . . . . . . . . . . 17 3.6 Special edges in E(S) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 3.7 The Amalgamated H of G; the size of the vertex u represents the value of f(u). 18 3.8 Ci = Pi[Qi; cycles 1-4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 3.9 Ci = Pi[Qi; cycles 5-8 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 3.10 F =fFiji2Z5g . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 3.11 G =fGiji2Z5g . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26 3.12 Fi[Gi;1 i 4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 3.13 Set up of K7+8 3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28 v 3.14 Type 3 Edges . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28 3.15 The Amalgamated Graph H; the size of the vertex indicated its amalgamation number . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 3.16 Column View of Amalgamated Graph . . . . . . . . . . . . . . . . . . . . . . . 30 3.17 Hamilton Cycles H(0;0;c), 1 c 5 . . . . . . . . . . . . . . . . . . . . . . . . 31 3.18 Coloring Tc(x) with 6x+c . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33 3.19 Coloring H(i;j;c) with 6x+c . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34 3.20 Coloring H(i;i;c) with 6x+c . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36 vi List of Tables 3.1 Number of Edges used in H(i;j;c) with 0 c 5, broken down by color class . 38 3.2 Number of Edges used in H(i;i;c) with 1 c 5, broken down by color class . 38 3.3 Number of Edges used in Tc(x) with 0 c 5, broken down by color class . . . 39 3.4 Number of Edges used in H(0;0;c) with 1 c 5, broken down by color class . 39 vii Chapter 1 Introduction 1.1 De nitions The complete multipartite graph, Kpn is the graph with np vertices that have been par- titioned into p parts of size n such that an edge exists between vertices u and v if and only if u and v are in di erent parts. A hamilton cycle in a graph G is a spanning cycle of G. If S is a set of hamilton cycles, then let G(S) be the graph induced by the edges in cycles of S. We denote the edges in this graph by E(G(S)) or E(S). The set S is maximal in G if G E(S) has no hamilton cycle. 1.2 History Considerable research has come before this dissertation to nd maximal sets of hamilton cycles in certain graphs. Ho man, Rodger, and Rosa [7] found that there exists a maximal set S of m edge-disjoint hamilton cycles in Kn if and only if m2 nj n+3 4 k ; j n+3 4 k +1;:::; j n 1 2 ko . It was later shown by Bryant, El-Zanati, and Rodger [1] that there exists a maximal set S of m edge-disjoint hamilton cycles in Kn;n if and only if n4 n(p 1)4 if 1. n is odd and p 1 (mod 4), or 2. p = 2, or 1 3. n = 1, except possibly for the undecided case when n 3 is odd, p is odd and m (n+1)(p 1) 24 . Jarrell and Rodger [8] solved these open cases when n 5, and removed all but the smallest possible exceptional values when n = 3, showing that a maximal set of hamilton cycles of size m exists when n = 3 and l n(p 1) 4 m + 1 m j (n+1)(p 1) 2 4 k , with strict inequality for the lower bound of m when p 1 (mod 4). Together, these results mean that for each odd value of p, exactly one value of m remains in doubt (namely l n(p 1) 4 m + 1 for p 1 (mod 4) and l n(p 1) 4 m for p 3 (mod 4)) and even that is only in doubt in the case when n = 3. Naturally, each remaining case becomes more and more di cult. Indeed, for some time it was unclear whether the remaining values would be orders of maximal sets of hamilton cycles. To summarize, these existing results in the literature can be combined to produce the following theorem: Theorem 1.1 There exists a maximal set of m hamilton cycles in Kpn if and only if 1. l n(p 1) 4 m m j n(p 1) 2 k and 2. m> n(p 1)4 if (a) n is odd and p 1 (mod 4)), or (b) p = 2, or (c) n = 1, except possibly when n = 3, and m = l n(p 1) 4 m + 1 and p 1 (mod 4) or m = l n(p 1) 4 m and p 3 (mod 4). For this dissertation, the goal is to clear up most of these last remaining cases, namely those multipartite graphs where n = 3 and p is odd. We do so by splitting this into two cases, one in which n = 3 and p 1 (mod 4), and the other in which n = 3 and p 3 2 (mod 4). The former case is completely resolved in Chapter 2, while the latter is resolved in Chapter 3 when p 7 (mod 8) with two possible exceptions. The work of this dissertation culminates in the following state of knowledge: Theorem 1.2 There exists a maximal set of m hamilton cycles in Kpn if and only if 1. l n(p 1) 4 m m j n(p 1) 2 k and 2. m> n(p 1)4 if (a) n is odd and p 1 (mod 4)), or (b) p = 2, or (c) n = 1, except possibly when n = 3, m = l n(p 1) 4 m and either p 3 (mod 8), p 19 or p2f15;23g. 1.3 The Technique of Amalgamations The approach used to prove the theorems of this dissertation is that of amalgamations. An amalgamation of a graph G is a graph H formed by a homomorphism f : V(G)!V(H). So for each v2V(H), the vertices of f 1(v) can be thought of as being amalgamated into the single vertex v in H; for each v2V(H), (v) =jf 1(v)j is known as the amalgamation number of v. G is said to be a disentanglement of H. In most of our proofs, an amalgamated graph is constructed in which each color class is connected and each vertex v is incident with 2 (v) edges of each color, thus looking like what would be obtained by amalgamating a graph in which each color class is a hamilton cycle. For our purposes, the two following results will be essential. The rst result describes properties of a graph formed by amalgamating Kn. The second will be used to show that the amalgamated graph we construct can be disentangled (\pulled apart", if you will) to form a subgraph of Kp3 that has a hamilton decomposition. 3 Lemma 1.1 [10] Let G = Kn be an l-edge-colored graph, and let f : V(G) !V(H) be an amalgamating function with amalgamation numbers given by the function : V(H) !N. Then H satis es the following conditions for any vertices w;v2V(H): 1. d(w) = (w)(n 1), 2. m(w;v) = (w) (v) if w6= v 3. w is incident with (w)2 loops, and 4. dH(i)(w) = Pu2f 1(w)dG(i)(u) for 1 i l, where m(w;v) is the number of edges between vertex w and vertex v, Once our graph satis es the conditions of Lemma 1.1, the following theorem allows us to disentangle the graph in such a way that we preserve connectivity and evenly divide the edge ends among the (u) disentangled vertices in each color class. Theorem 1.3 [10] Let H be an l-edge-colored graph satisfying conditions (1)-(3) of Lemma 1.1 for the function : V(H) ! N. Then there exists a disentanglement G of H that satis es 1. G = Kn, 2. for any z2V(H);jdG(i)(v) dG(i)(u)j 1 for 1 i l and all u;v2f 1(z), 3. if dH(i)(z) (z) is an even integer for all z2V(H), then !(G(i)) = !(H(i)). where !(G) denotes the number of components for the graph G. Another important result that is invaluable in the main proof is the following theorem proved by Hilton [6]. A k-edge-coloring of G is said to be evenly equitable ifjdi(v) dj(v)j 2 for 1 i < j k and di(v) is even for 1 i k, where di(v) is the degree of v in the subgraph induced by the edges colored i. 4 Theorem 1.4 [6] For each k 1, each nite Eulerian graph has an evenly equitable edge- coloring with k colors. The use of the previous lemma and theorems and the technique of amalgamations have allowed for much more e cient and streamlined proofs in these types of edge coloring prob- lems. 5 Chapter 2 The p 1 (mod 4) Case 2.1 Introduction Our aim in this chapter is to solve half of the remaining open cases in Theorem 1.1; speci cally the case when n = 3, m = l n(p 1) 4 m + 1 and p 1 (mod 4). In the following, edge-colorings are used to represent the hamilton cycles, so let G(i) denote the subgraph of G induced by the edges colored i. 2.2 p 1 (mod 4) Theorem 2.1 For the complete multipartite graph Kpn, let p = 4x+1 for some integer x 2 and let n = 3. Then there exists a maximal set of m = l 3(p 1) 4 m + 1 = 3x + 1 edge disjoint hamilton cycles in Kpn. Proof We de ne the hamilton cycles on the vertex set Zp Z3 in which the parts are Pi =fig Z3 for each i2Zp. As we look at this problem, it is helpful to think of the parts of the graph arranged in p vertical columns with three vertices in each column; so each part has a top, a middle, and a bottom vertex as shown in Figure 2.1. Our goal is to choose the edges for our set S of hamilton cycles wisely so that we ensure that our set is maximal. In each case S is shown to be maximal because Kpn E(S) = G(S) has a cut vertex. We do this by splitting V(G) into 3 sections. We denote by G1 the subgraph induced by vertices in the rst 2x parts (part 0 to part 2x 1) together with the top vertex of the center part, which we call u. The subgraph induced by vertices in the last 2x parts (part 2x+ 1 to part 4x) together with the bottom vertex of the center part, which we will call w, is denoted by 6 G2. Finally, the middle vertex of the center part will be called v. The vertex v will serve as a cut vertex in G(S). v1 v v2 G1 G2 Figure 2.1: View of K4x+13 The edges we choose to make our set of hamilton cycles fall into the following three types and are pictured in Figure 2.2: Type 1: All edges in Kp3 that join vertices in G1 to vertices in G2 occur in E(S). Type 2: Precisely 2m edges joining vertices in V(G1SG2) to v occur in E(S). (Approximately half of these edges are incident with vertices in G1, while the others are incident with vertices in G2.) Type 3: Certain edges between two vertices in G1 or two vertices in G2 are nally chosen to make G(S) 2m-regular. v1 v2 G1 G2 v Figure 2.2: Type 2 and 3 Edges 7 As we select Type 2 edges, we note that v is not yet adjacent to any other vertices. Thus to produce m = 3x+ 1 hamilton cycles, we need the degree of v to be 2(3x+ 1) = 6x+ 2. If m is even, then 3x + 1 of the edges are chosen to join vertex v to vertices in G1, while the other 3x+ 1 are chosen to join vertex v and vertices in G2. If m is odd, then 3x of the edges join vertex v and vertices in G1, while the other 3x+ 2 join vertex v and vertices in G2. For the Type 3 edges, we carefully pick edges between two vertices in G1 or two vertices in G2 so that we build each vertex to degree 6x + 2. It turns out that the edges of Types 2 and 3 need not be precisely chosen if we use amalgamations to produce G. Instead we de ne H and let Theorem 1.3 produce G. The method used to construct the hamilton cycles is that of amalgamations. This technique has been used successfully in this setting (see [8] for example). The amalgamation used here is the graph homomorphism f : V(G)!V(H) = (Zpnf2xg)S(f2xg Z3) de ned as follows. For each i2Zpnf2xgand for each j2Z3, let f((i;j)) = i, and for each j2Z3 let f(2x;j) = (2x;j) = u;v; or w if j = 0;1; or 2 respectively. So, except for the part containing v, f amalgamates the vertices in each part into a single vertex in H with amalgamation number 3. The vertices in the part containing v are not amalgamated by f, so each vertex z has amalgamation number (z) = 1. So we will require that dH(i) = 6m = 6(3x + 1) for each i2Zpnf2xg and dH(i) = 2m = 2(3x+ 1) for each i2fu;v;wg. The subgraph B of H induced by the edges joining vertices in Z2x to vertices in Z4x+1n Z2x+1 is isomorphic to 9K2x;2x. Let " = 1 or 0 if m is odd or even respectively. Join v to vertices in Zx+1 " and Z2xnZx+1 " with 2 and 1 edges respectively, and join v to vertices in Z3x+1+"nZ2x+1 and Z4x+1nZ3x+1+" with 2 and 1 edges respectively; these produce Type 2 edges in G. Pair the vertices in Z2xnZx+1 " and pair the vertices in Z4x+1nZ3x+1+", and join each such pair with an edge; these produce the Type 3 edges in G. (Notice that each set has an even size by de nition of ".) Color the edges of H as follows. Since there exists a hamilton decomposition of K2x;2x, the edges of B can be partitioned into 9x sets, each of which induces a hamilton cycle of H. 8 Let B0, ..., B3x be 3x+ 1 of these 9x sets, and color the edges in Bi with i for each i2Zm. Let H1 = H Si2Z3x+1 Bi. Then dH1(i) = 4m and dH1(i;j) = 2m. We now give the subgraph H1 of H an evenly equitable edge coloring with the 3x + 1 colors in Z3x+1. Such a coloring exists by Theorem 1.4. Thus in H1 each color appears 4 times at each vertex z with (z) = 3 and twice at each vertex z where (z) = 1. So in H each color now appears 6 times at each vertex where = 3 and once where = 1. We are now assured that our color classes are connected and that each color appears on the appropriate number of edges, namely 2 (z), at each vertex z. The aim now is to disentangle our graph so that we can pick out our maximal set of hamilton cycles. To be able to apply Lemma 1.1 we still must add more edges to H to form H+ so that H+ satis es properties (1-4) of Lemma 1.1 (i.e. so that it is an amalgamation of K3p). So add edges to H so that between each pair of vertices x and y there are: exactly nine edges if jfx;yg\fu;v;wgj = 0; exactly three edges if jfx;yg\fu;v;wgj = 1; and exactly one edge if jfx;yg\fu;v;wgj= 2. Finally, add three loops to each vertex not in fu;v;wg. All these additional edges and loops are colored 0. It is straightforward to check that H+ satis es properties (1-4) of Lemma 1.1, so we can now apply Theorem 1.3 to H+ to produce G+, and edge-colored copy of K3p. Removing all edges in G+ corresponding to loops in H+ produces Kpn, and then removing all remaining edges colored 0 produces G. Each color class in G is 2-regular by property (2) of Theorem 1.3, and is connected by property (3), so is a hamilton cycle. Removing the edges in these hamilton cycles from Kpn in particular means that all Type 1 edges are removed, so produces a graph in which v is a cut vertex (it is actually the graph induced by the edges (not loops) colored 0 in G+). So the required maximal set of hamilton cycles has been produced. So this chapter culminates in the following state of knowledge: Theorem 2.2 There exists a maximal set of m hamilton cycles in Kpn if and only if 9 1. l n(p 1) 4 m m j n(p 1) 2 k and 2. m> n(p 1)4 if (a) n is odd and p 1 (mod 4)), or (b) p = 2, or (c) n = 1, except possibly when n = 3, p 3 (mod 4), and m = l n(p 1) 4 m . 10 Chapter 3 The p 3 (mod 4) Case 3.1 Introduction In this chapter, we will resolve some of the cases in which n = 3 and p 3 (mod 4). We begin in Section 3.2 by solving the two smallest cases individually, namely when p = 7 and when p = 11. Section 3.3 uses the solution for p = 7 outlined in Section 3.2 to provide two approaches when p 7 (mod 8). One approach is based on a conjecture that, while unproven in general, does provide a solution for the speci c case of K393 . The other approach uses theorems of Heinrich, Lindner, Rodger, and Burling (see [5] and [2]) that provide a solution when n = 3, p = 7 + 8 , and 3. 3.2 Small Cases p = 7 and p = 11 Theorem 3.1 There exists a maximal set of m = 5 edge disjoint hamilton cycles in K73. Proof We begin with the complete multipartite graph K73, which we?ll refer to as G through- out the proof. We view this complete multipartite graph as seven columns (parts named 0 to 6) and three rows (named 0, 1, and 2). Each vertex is then denoted as an ordered pair (i;j) where i2f0;1;2;3;4;5;6g (the part) and j2f0;1;2g (the row). We divide the vertices of the graph into three sections as follows: L0 = f(0;0);(0;1);(0;2);(1;0);(1;1);(2;0);(2;1);(3;0);(4;0);(5;0)g, R0 = f(1;2);(2;2);(3;2);(4;1);(4;2);(5;1);(5;2);(6;0);(6;1);(6;2)g, and v = (3;1). 11 L0 R0v 1 2 3 4 5 60 0 1 2 Figure 3.1: Setup of three sections with edge cut depicted The proof is driven by carefully choosing edges to include in the set of hamilton cycles, S, so that v is a cut vertex in G E(S). These edges in our hamilton cycles fall into three categories: all edges between vertices in section L0 and vertices in section R0; certain edges between v and vertices in section L0; and certain edges between v and vertices in section R0 (see Figure 3.2). Our plan is to make our edge set 10-regular considering only these types of edges; it will be shown that there exists a hamilton decomposition of the subgraph induced by these edges. The sections L0 and R0 are named to re ect the fact that the edges in S join vertices on the left of the line in Figure 3.2 to vertices on the right, and the subscript 0 is added in anticipation of the generalization presented in 3.3. L0 R0v Figure 3.2: Special edges in E(S) Next, we use the technique of amalgamations described in Chapter 1. Our amalgamation function f : V(G[E(S)])!V(H) is de ned as follows: 12 f(i;j) = 8 >>> >>>> >>> >>> >< >>>> >>> >>> >>>> : (0;0) if i = 0; (i;0) if 1 i 2;j 1; (i;0) if 3 i 5;j = 0; (i;1) if 1 i 3;j = 2; (i;1) if 4 i 5;j 1; (6;1) if i = 6; and since it plays a special role, we de ne f(3;1) = v. So, V(H) now looks like Figure 3.3. L0 R 0 (0 , 0) (1 , 0) (2 , 0) (3 , 0) (4 , 0) (5 , 0) (1 , 1) (2 , 1) (3 , 1) (4 , 1) (5 , 1) (6 , 1) v Figure 3.3: The Amalgamated H of G; the size of the vertex u represents the value of f(u). The critical part in the proof is to color the edges in H so that for 1 i 5 (i) for all u2V(H), dH(i)(u) = 2f(u) and (ii) each color class H(i) is connected. These conditions will allow us to disentangle H so that each color class is a hamilton cycle by properties 2 and 3 respectively of Theorem 1.3. Our coloring is as follows: First, each of the ve paths below are colored in a di erent color, namely colors 1-5. P1 = [(3;0);(6;1);(2;0);(5;1);(1;0);(4;1);(0;0);(3;1)] P2 = [(2;0);(1;1);(0;0);(3;1);(1;0);(2;1);(3;0);(5;1);(4;0);(6;1);(5;0);(4;1)] P3 = [(1;0);(4;1);(3;0);(6;1);(5;0);(1;1);(4;0);(2;1);(0;0);(3;1);(2;0);(5;1)] P4 = [(1;0);(4;1);(5;0);(2;1);(0;0);(1;1);(3;0);(6;1);(4;0);(3;1);(2;0);(5;1)] P5 = [(2;0);(1;1);(0;0);(2;1);(1;0);(3;1);(5;0);(6;1);(4;0);(5;1);(3;0);(4;1)] Each of these paths is then joined to a path created from the edges in Figure 3.2, namely 13 Q1 = [(3;1);(1;1);(2;1);v;(4;0);(5;0);(3;0)] Q2 = [(4;1);v;(2;0)] Q3 = [(5;1);v;(1;0)] Q4 = [(5;1);v;(1;0)] Q5 = [(4;1);v;(2;0)] This creates the following cycles Ci = Pi[Qi: C1 = ((3;0);(6;1);(2;0);(5;1);(1;0);(4;1);(0;0);(3;1);(1;1);(2;1);v;(4;0);(5;0)) C2 = ((2;0);(1;1);(0;0);(3;1);(1;0);(2;1);(3;0);(5;1);(4;0);(6;1);(5;0);(4;1);v) C3 = ((1;0);(4;1);(3;0);(6;1);(5;0);(1;1);(4;0);(2;1);(0;0);(3;1);(2;0);(5;1);v) C4 = ((1;0);(4;1);(5;0);(2;1);(0;0);(1;1);(3;0);(6;1);(4;0);(3;1);(2;0);(5;1);v) C5 = ((2;0);(1;1);(0;0);(2;1);(1;0);(3;1);(5;0);(6;1);(4;0);(5;1);(3;0);(4;1);v) Illustrations of these paths are given in Figure 3.4. 14 (0 , 0) (1 , 0) (2 , 0) (3 , 0) (4 , 0) (5 , 0) (1 , 1) (2 , 1) (3 , 1) (4 , 1) (5 , 1) (6 , 1) (0 , 0) (1 , 0) (2 , 0) (3 , 0) (4 , 0) (5 , 0) (1 , 1) (2 , 1) (3 , 1) (4 , 1) (5 , 1) (6 , 1) (0 , 0) (1 , 0) (2 , 0) (3 , 0) (4 , 0) (5 , 0) (1 , 1) (2 , 1) (3 , 1) (4 , 1) (5 , 1) (6 , 1) (0 , 0) (1 , 0) (2 , 0) (3 , 0) (4 , 0) (5 , 0) (1 , 1) (2 , 1) (3 , 1) (4 , 1) (5 , 1) (6 , 1) (0 , 0) (1 , 0) (2 , 0) (3 , 0) (4 , 0) (5 , 0) (1 , 1) (2 , 1) (3 , 1) (4 , 1) (5 , 1) (6 , 1) (0 , 0) (1 , 0) (2 , 0) (3 , 0) (4 , 0) (5 , 0) (1 , 1) (2 , 1) (3 , 1) (4 , 1) (5 , 1) (6 , 1) (0 , 0) (1 , 0) (2 , 0) (3 , 0) (4 , 0) (5 , 0) (1 , 1) (2 , 1) (3 , 1) (4 , 1) (5 , 1) (6 , 1) (0 , 0) (1 , 0) (2 , 0) (3 , 0) (4 , 0) (5 , 0) (1 , 1) (2 , 1) (3 , 1) (4 , 1) (5 , 1) (6 , 1) (0 , 0) (1 , 0) (2 , 0) (3 , 0) (4 , 0) (5 , 0) (1 , 1) (2 , 1) (3 , 1) (4 , 1) (5 , 1) (6 , 1) (0 , 0) (1 , 0) (2 , 0) (3 , 0) (4 , 0) (5 , 0) (1 , 1) (2 , 1) (3 , 1) (4 , 1) (5 , 1) (6 , 1) Figure 3.4: Ci = Pi[Qi 15 We have now colored most of the edges in E(S). Left to color are the edges between f(1;0);(2;0);(3;0)g2 L0 and f(4;1);(5;1);(6;1)g2 R0 that were not used in the cycles denoted by Ci above. Each vertex has degree ten, so we will give these edges an evenly equitable edge coloring with ve colors, namely 1-5. Now each of our ve colors appears at each vertex u a total 2f(u) more times and each color class is connected. The next goal is to disentangle the graph H. To be able to apply Lemma 1.1, we need to use the same technique as in the p 1 (mod 4) case which required adding edges to our graph H so that it is the amalgamation of the complete graph K3p. All of these additional edges and loops are colored 0. We call this new graph H+ and note that it now satis es the conditions of Lemma 1.1. Thus we apply Theorem 1.3 to H+ to produce G+, which is an edge-colored copy of K3p. We now remove all edges in G+ colored 0. Using Theorem 1.3, we see that each color class is 2-regular by (i) and connected by (ii), which implies that each color class is a hamilton cycle. We now consider G E(S). Note that all edges between vertices in L0 and R0 were in E(S), so we have that G E(S) has cut vertex v. So our set of hamilton cycles is maximal. Theorem 3.2 There exists a maximal set of m = 8 edge disjoint hamilton cycles in K113 . Proof We begin with the complete multipartite graphK113 , which we?ll refer to asGthrough- out the proof. This construction will be very similar to that of K73 from Section 3.1. We view this complete multipartite graph as eleven columns (parts named 0 to 10) and three rows (named 0, 1, and 2). Each vertex is then denoted as an ordered pair (i;j) where i2f0;1;2;3;4;5;6;7;8;9;10g (the part) and j2f0;1;2g (the row). We divide the vertices of the graph into three sections as follows: L0 = f(0;0);(0;1);(0;2);(1;0);(1;1);(2;0);(2;1);(3;0);(3;1);(4;0);(4;1);(5;0);(6;0); (7;0);(8;0);(9;0)g; 16 R0 = f(1;2);(2;2);(3;2);(4;2);(5;2);(6;0);(6;1);(7;0);(7;1);(8;0);(8;1);(9;0);(9;1); (10;0);(10;1);(10;2)g, and v = (5;1). L0 1 2 3 4 5 60 0 1 2 7 8 9 10 R0v Figure 3.5: Setup of three sections with edge cut depicted The proof is driven by carefully choosing edges to include in the set of hamilton cycles, S, so that v is a cut vertex in G E(S). These edges in our hamilton cycles fall into three categories: all edges between vertices in section L0 and vertices in section R0; certain edges between v and vertices in section L0; and certain edges between v and vertices in section R0 (see Figure 3.6). Our plan is to make our edge set 16-regular considering only these types of edges; it will be shown that there exists a hamilton decomposition of the subgraph induced by these edges. The sections L0 and R0 are named to re ect the fact that the edges in S join vertices on the left of the line in Figure 3.5 to vertices on the right, and the subscript 0 is added in anticipation of a general solution similar to when p 7 (mod 8). L0 R0v Figure 3.6: Special edges in E(S) Next, we use the technique of amalgamations described in Chapter 1. Our amalgamation function f : V(G[E(S)])!V(H) is de ned as follows: 17 f(i;j) = 8 >>> >>>> >>> >>> >< >>>> >>> >>> >>>> : (0;0) if i = 0; (i;0) if 1 i 4;j 1; (i;0) if 5 i 9;j = 0; (i;1) if 1 i 5;j = 2; (i;1) if 6 i 9;j 1; (10;1) if i = 10; and since it plays a special role, we de ne f(5;1) = v. So, V(H) now looks like Figure 3.7. L 0 R 0 (0 , 0) (1 , 0) (2 , 0) (3 , 0) (4 , 0) (5 , 0) (6 , 0) (7 , 0) (8 , 0) (9 , 0) (10 , 1)(1 , 1) (2 , 1) (3 , 1) (4 , 1) (5 , 1) (6 , 1) (7 , 1) (8 , 1) (9 , 1) v Figure 3.7: The Amalgamated H of G; the size of the vertex u represents the value of f(u). The critical part in the proof is to color the edges in H so that for 1 i 8 (i) for all u2V(H), dH(i)(u) = 2f(u) and (ii) each color class H(i) is connected. These conditions will allow us to disentangle H so that each color class is a hamilton cycle by properties 2 and 3 respectively of Theorem 1.3. Our coloring is as follows: First, each of the eight paths below are colored in a di erent color, namely colors 1-8. P1 = [(1;0);(4;1);(5;0);(3;1);(6;0);(2;1);(0;0);(1;1);(2;0);(5;1);(3;0);(6;1);(4;0); (7;1);(8;0);(10;1);(9;0);(8;1);(7;0);(9;1)] P2 = [(2;0);(4;1);(0;0);(3;1);(1;0);(5;1);(4;0);(1;1);(3;0);(2;1);(5;0);(9;1);(6;0); (10;1);(7;0);(6;1);(8;0);(7;1);(9;0);(8;1)] P3 = [(3;0);(1;1);(4;0);(2;1);(0;0);(3;1);(1;0);(4;1);(2;0);(6;1);(5;0);(8;1);(7;0); (9;1);(8;0);(5;1);(9;0);(10;1);(6;0);(7;1)] P4 = [(4;0);(3;1);(2;0);(5;1);(0;0);(1;1);(5;0);(7;1);(6;0);(8;1);(3;0);(9;1);(1;0); 18 (2;1);(7;0);(10;1);(8;0);(4;1);(9;0);(6;1)] P5 = [(4;0);(5;1);(3;0);(4;1);(0;0);(2;1);(8;0);(3;1);(9;0);(1;1);(7;0);(10;1);(5;0); (9;1);(6;0);(8;1);(2;0);(7;1);(1;0);(6;1)] P6 = [(3;0);(8;1);(5;0);(10;1);(6;0);(1;1);(8;0);(6;1);(9;0);(2;1);(1;0);(5;1);(0;0); (4;1);(7;0);(3;1);(2;0);(9;1);(4;0);(7;1)] P7 = [(1;0);(8;1);(2;0);(1;1);(0;0);(3;1);(4;0);(2;1);(3;0);(4;1);(6;0);(5;1);(7;0); (6;1);(5;0);(7;1);(9;0);(10;1);(8;0);(9;1)] P8 = [(5;0);(10;1);(4;0);(9;1);(3;0);(8;1);(2;0);(7;1);(1;0);(6;1);(0;0);(5;1)] Each of these paths is then joined to a path created from the edges in Figure 3.6, namely Q1 = [(9;1);v;(1;0)] Q2 = [(8;1);v;(2;0)] Q3 = [(7;1);v;(3;0)] Q4 = [(6;1);v;(4;0)] Q5 = [(6;1);v;(4;0)] Q6 = [(7;1);v;(3;0)] Q7 = [(9;1);v;(1;0)] Q8 = [(5;1);(4;1);(3;1);(2;1);(1;1);v;(9;0);(8;0);(7;0);(6;0);(5;0)] This creates the following cycles Ci = Pi[Qi: C1 = ((1;0);(4;1);(5;0);(3;1);(6;0);(2;1);(0;0);(1;1);(2;0);(5;1);(3;0);(6;1);(4;0); (7;1);(8;0);(10;1);(9;0);(8;1);(7;0);(9;1);v) C2 = ((2;0);(4;1);(0;0);(3;1);(1;0);(5;1);(4;0);(1;1);(3;0);(2;1);(5;0);(9;1);(6;0); (10;1);(7;0);(6;1);(8;0);(7;1);(9;0);(8;1);v) C3 = ((3;0);(1;1);(4;0);(2;1);(0;0);(3;1);(1;0);(4;1);(2;0);(6;1);(5;0);(8;1);(7;0); (9;1);(8;0);(5;1);(9;0);(10;1);(6;0);(7;1);v) C4 = ((4;0);(3;1);(2;0);(5;1);(0;0);(1;1);(5;0);(7;1);(6;0);(8;1);(3;0);(9;1);(1;0); 19 (2;1);(7;0);(10;1);(8;0);(4;1);(9;0);(6;1);v) C5 = ((4;0);(5;1);(3;0);(4;1);(0;0);(2;1);(8;0);(3;1);(9;0);(1;1);(7;0);(10;1);(5;0); (9;1);(6;0);(8;1);(2;0);(7;1);(1;0);(6;1);v) C6 = ((3;0);(8;1);(5;0);(10;1);(6;0);(1;1);(8;0);(6;1);(9;0);(2;1);(1;0);(5;1);(0;0); (4;1);(7;0);(3;1);(2;0);(9;1);(4;0);(7;1);v) C7 = ((1;0);(8;1);(2;0);(1;1);(0;0);(3;1);(4;0);(2;1);(3;0);(4;1);(6;0);(5;1);(7;0); (6;1);(5;0);(7;1);(9;0);(10;1);(8;0);(9;1);v) C8 = ((5;0);(10;1);(4;0);(9;1);(3;0);(8;1);(2;0);(7;1);(1;0);(6;1);(0;0);(5;1);(4;1); (3;1);(2;1);(1;1);v;(9;0);(8;0);(7;0);(6;0)) Illustrations of these paths are given in Figures 3.8 and 3.9. 20 L0 R0 (0, 0) (1, 0)(2, 0)(3, 0)(4, 0)(5, 0)(6, 0)(7, 0)(8, 0)(9, 0) (10, 1)(1, 1)(2, 1)(3, 1)(4, 1)(5, 1)(6, 1)(7, 1)(8, 1)(9, 1) L0 R0 (0, 0) (1, 0)(2, 0)(3, 0)(4, 0)(5, 0)(6, 0)(7, 0)(8, 0)(9, 0) (10, 1)(1, 1)(2, 1)(3, 1)(4, 1)(5, 1)(6, 1)(7, 1)(8, 1)(9, 1) L0 R0 (0, 0) (1, 0)(2, 0)(3, 0)(4, 0)(5, 0)(6, 0)(7, 0)(8, 0)(9, 0) (10, 1)(1, 1)(2, 1)(3, 1)(4, 1)(5, 1)(6, 1)(7, 1)(8, 1)(9, 1) L0 R0 (0, 0) (1, 0)(2, 0)(3, 0)(4, 0)(5, 0)(6, 0)(7, 0)(8, 0)(9, 0) (10, 1)(1, 1)(2, 1)(3, 1)(4, 1)(5, 1)(6, 1)(7, 1)(8, 1)(9, 1) L0 R0 (0, 0) (1, 0)(2, 0)(3, 0)(4, 0)(5, 0)(6, 0)(7, 0)(8, 0)(9, 0) (10, 1)(1, 1)(2, 1)(3, 1)(4, 1)(5, 1)(6, 1)(7, 1)(8, 1)(9, 1) L0 R0 (0, 0) (1, 0)(2, 0)(3, 0)(4, 0)(5, 0)(6, 0)(7, 0)(8, 0)(9, 0) (10, 1)(1, 1)(2, 1)(3, 1)(4, 1)(5, 1)(6, 1)(7, 1)(8, 1)(9, 1) L0 R0 (0, 0) (1, 0)(2, 0)(3, 0)(4, 0)(5, 0)(6, 0)(7, 0)(8, 0)(9, 0) (10, 1)(1, 1)(2, 1)(3, 1)(4, 1)(5, 1)(6, 1)(7, 1)(8, 1)(9, 1) L0 R0 (0, 0) (1, 0)(2, 0)(3, 0)(4, 0)(5, 0)(6, 0)(7, 0)(8, 0)(9, 0) (10, 1)(1, 1)(2, 1)(3, 1)(4, 1)(5, 1)(6, 1)(7, 1)(8, 1)(9, 1) Figure 3.8: Ci = Pi[Qi; cycles 1-4 We have now colored most of the edges in E(S). Left to color are the edges between f(0;0);(1;0);(2;0);(3;0);(4;0)g2L0 and f(6;1);(7;1);(8;1);(9;1);(10;1)g2R0 that were not used in the cycles denoted by Ci above. Each vertex has degree sixteen, so we will give these edges an evenly equitable edge coloring with eight colors, namely 1-8. Now each of our eight colors appears at each vertex u a total 2f(u) more times and each color class is connected. The next goal is to disentangle the graph H. To be able to apply Lemma 1.1, we need to use the same technique as in the p 1 (mod 4) case which required adding edges to our graph H so that it is the amalgamation of the complete graph K3p. All of these additional edges and loops are colored 0. We call this new graph H+ and note that it now satis es the conditions of Lemma 1.1. Thus we apply Theorem 1.3 to H+ to produce G+, which is an 21 L0 R0 (0, 0) (1, 0)(2, 0)(3, 0)(4, 0)(5, 0)(6, 0)(7, 0)(8, 0)(9, 0) (10, 1)(1, 1)(2, 1)(3, 1)(4, 1)(5, 1)(6, 1)(7, 1)(8, 1)(9, 1) L0 R0 (0, 0) (1, 0)(2, 0)(3, 0)(4, 0)(5, 0)(6, 0)(7, 0)(8, 0)(9, 0) (10, 1)(1, 1)(2, 1)(3, 1)(4, 1)(5, 1)(6, 1)(7, 1)(8, 1)(9, 1) L0 R0 (0, 0) (1, 0)(2, 0)(3, 0)(4, 0)(5, 0)(6, 0)(7, 0)(8, 0)(9, 0) (10, 1)(1, 1)(2, 1)(3, 1)(4, 1)(5, 1)(6, 1)(7, 1)(8, 1)(9, 1) L0 R0 (0, 0) (1, 0)(2, 0)(3, 0)(4, 0)(5, 0)(6, 0)(7, 0)(8, 0)(9, 0) (10, 1)(1, 1)(2, 1)(3, 1)(4, 1)(5, 1)(6, 1)(7, 1)(8, 1)(9, 1) L0 R0 (0, 0) (1, 0)(2, 0)(3, 0)(4, 0)(5, 0)(6, 0)(7, 0)(8, 0)(9, 0) (10, 1)(1, 1)(2, 1)(3, 1)(4, 1)(5, 1)(6, 1)(7, 1)(8, 1)(9, 1) L0 R0 (0, 0) (1, 0)(2, 0)(3, 0)(4, 0)(5, 0)(6, 0)(7, 0)(8, 0)(9, 0) (10, 1)(1, 1)(2, 1)(3, 1)(4, 1)(5, 1)(6, 1)(7, 1)(8, 1)(9, 1) L0 R0 (0, 0) (1, 0)(2, 0)(3, 0)(4, 0)(5, 0)(6, 0)(7, 0)(8, 0)(9, 0) (10, 1)(1, 1)(2, 1)(3, 1)(4, 1)(5, 1)(6, 1)(7, 1)(8, 1)(9, 1) L0 R0 (0, 0) (1, 0)(2, 0)(3, 0)(4, 0)(5, 0)(6, 0)(7, 0)(8, 0)(9, 0) (10, 1)(1, 1)(2, 1)(3, 1)(4, 1)(5, 1)(6, 1)(7, 1)(8, 1)(9, 1) Figure 3.9: Ci = Pi[Qi; cycles 5-8 edge-colored copy of K3p. We now remove all edges in G+ colored 0. Using Theorem 1.3, we see that each color class is 2-regular by (i) and connected by (ii), which implies that each color class is a hamilton cycle. We now consider G E(S). Note that all edges between vertices in L0 and R0 were in E(S), so we have that G E(S) has cut vertex v. So our set of hamilton cycles is maximal. 3.3 p 7 (mod 8), p 31 As mentioned in the introduction to this chapter, we present two approaches to the general case when n = 3 and p 7 (mod 8). We begin by stating the following unproven conjecture. 22 Conjecture 3.1 Let z 5. There exist 1-factorizations F = fFiji2Zzg and G = fGij i2Zzg of Kz;z with vertex set Zz Z2 such that for all i2Zz, 1. f(0;0);(i;1)g and f(0;1);(i;0)g are in Fi if i6= 0, and f(i;0);(i;1)g is in F0, 2. f(i;0);(i;1)g is in Gi, and 3. Fi[Gi is connected if i 1. Conditions (1-3) of Conjecture 3.1 cannot be satis ed if z 4. Lemma 3.1 Conjecture 3.1 holds for z = 5. Proof Let F be F0 =ff(0;0);(0;1)g;f(1;0);(1;1)g;f(2;0);(2;1)g;f(3;0);(3;1)g;f(4;0);(4;1)gg F1 =ff(0;0);(1;1)g;f(1;0);(0;1)g;f(2;0);(3;1)g;f(3;0);(4;1)g;f(4;0);(3;1)gg F2 =ff(0;0);(2;1)g;f(1;0);(4;1)g;f(2;0);(0;1)g;f(3;0);(1;1)g;f(4;0);(3;1)gg F3 =ff(0;0);(3;1)g;f(1;0);(2;1)g;f(2;0);(4;1)g;f(3;0);(0;1)g;f(4;0);(1;1)gg F4 =ff(0;0);(4;1)g;f(1;0);(3;1)g;f(2;0);(1;1)g;f(3;0);(2;1)g;f(4;0);(0;1)gg Let G be G0 =ff(0;0);(0;1)g;f(1;0);(2;1)g;f(2;0);(1;1)g;f(3;0);(4;1)g;f(4;0);(3;1)gg G1 =ff(0;0);(3;1)g;f(1;0);(1;1)g;f(2;0);(4;1)g;f(3;0);(2;1)g;f(4;0);(0;1)gg G2 =ff(0;0);(4;1)g;f(1;0);(3;1)g;f(2;0);(2;1)g;f(3;0);(0;1)g;f(4;0);(1;1)gg 23 G3 =ff(0;0);(1;1)g;f(1;0);(4;1)g;f(2;0);(0;1)g;f(3;0);(3;1)g;f(4;0);(2;1)gg G4 =ff(0;0);(2;1)g;f(1;0);(0;1)g;f(2;0);(3;1)g;f(3;0);(1;1)g;f(4;0);(4;1)gg Then we have hamilton cycles induced by the following sets of edges: F1[G1 = ff(0;0);(1;1)g;f(1;0);(1;1)g;f(1;0);(0;1)g;f(4;0);(0;1)g;f(4;0);(2;1)g; f(3;0);(2;1)g;f(3;0);(4;1)g;f(2;0);(4;1)g;f(2;0);(3;1)g;f(0;0);(3;1)gg F2[G2 = ff(0;0);(2;1)g;f(2;0);(2;1)g;f(2;0);(0;1)g;f(3;0);(0;1)g;f(3;0);(1;1)g; f(4;0);(1;1)g;f(4;0);(3;1)g;f(1;0);(3;1)g;f(1;0);(4;1)g;f(0;0);(4;1)gg F3[G3 = ff(0;0);(3;1)g;f(3;0);(3;1)g;f(3;0);(0;1)g;f(2;0);(0;1)g;f(2;0);(4;1)g; f(1;0);(4;1)g;f(1;0);(2;1)g;f(4;0);(2;1)g;f(4;0);(1;1)g;f(0;0);(1;1)gg F4[G4 = ff(0;0);(4;1)g;f(4;0);(4;1)g;f(4;0);(0;1)g;f(1;0);(0;1)g;f(1;0);(3;1)g; f(2;0);(3;1)g;f(2;0);(1;1)g;f(3;0);(1;1)g;f(3;0);(2;1)g;f(0;0);(2;1)gg F, G, and Fi[Gi;1 i 4 are pictured in Figures 3.10, 3.11, and 3.12. The bold edges represent those required by Conditions (1-2) in Conjecture 3.1. In proving Theorem 3.4, we can use Conjecture 3.1, but could also make use of the following result. Let 2Kn denote the multigraph on n vertices in which each pair of vertices is joined by exactly two edges. An i-factor of a graph G is a spanning subgraph of G that is regular of 24 (0,0) (1,0) (2,0) (3,0) (4,0) (0,1) (1,1) (2,1) (3,1) (4,1) (0,0) (1,0) (2,0) (3,0) (4,0) (0,0) (1,0) (2,0) (3,0) (4,0) (0,0) (1,0) (2,0) (3,0) (4,0) (0,0) (1,0) (2,0) (3,0) (4,0) (0,1) (1,1) (2,1) (3,1) (4,1) (0,1) (1,1) (2,1) (3,1) (4,1) (0,1) (1,1) (2,1) (3,1) (4,1) (0,1) (1,1) (2,1) (3,1) (4,1) F1 F2 F3 F4 F0 Figure 3.10: F =fFiji2Z5g degree i. An m-cycle decomposition of a graph G is a collection of edge-disjoint m-cycles which partition the edge set E(G). An m-cycle decomposition C(m) is resolvable if the m-cycles in C(m) can be partitioned into 2-factors of G. A subgraph X of a graph G is an almost parallel class if for some vertex v, X is a 2-factor of G v. In this case v is called the de ciency of the almost parallel class and is denoted by d(X). An m-cycle decomposition C(m) is almost resolvable if C(m) can be partitioned into almost parallel classes. From results of Heinrich, Lindner, Rodger, and Burling, we have the following theorem. Theorem 3.3 [2, 5] For all m 3, there exists an almost resolvable m-cycle system of 2Kn if and only if n 1 (mod m). Theorem 3.4 Let 3, let n = 3, and let p = 7 + 8 . There exists a maximal set of m = l 3(p 1) 4 m = 3x+ 2 edge disjoint hamilton cycles in Kpn. 25 (0,0) (1,0) (2,0) (3,0) (4,0) (0,1) (1,1) (2,1) (3,1) (4,1) (0,0) (1,0) (2,0) (3,0) (4,0) (0,0) (1,0) (2,0) (3,0) (4,0) (0,0) (1,0) (2,0) (3,0) (4,0) (0,1) (1,1) (2,1) (3,1) (4,1) (0,1) (1,1) (2,1) (3,1) (4,1) (0,1) (1,1) (2,1) (3,1) (4,1) G2 G3 G4 G0 (0,0) (1,0) (2,0) (3,0) (4,0) (0,1) (1,1) (2,1) (3,1) (4,1) G1 Figure 3.11: G =fGiji2Z5g Proof The case when p = 7 is settled in Theorem 3.1, so we now use our construction for K73 to produce a maximal set S of hamilton cycles when p = 7 + 8 . Recall that in producing a maximal set of hamilton cycles for K73, we viewed our complete multipartite graph as having seven columns of three vertices each. We then split this graph into two sections denoted L0 and R0 and a single vertex v. As we generalize this case, we start with the aforementioned seven parts and add more in groups of eight. We will visualize this with four parts on each side of the original seven parts. The eight new parts are viewed as eight columns (parts named 0 to 7) and three rows (named 0, 1, and 2). We follow the same naming convention as before, except we include a third coordinate. The original vertices in K73 are now named (i;j;0) instead of (i;j) as before. Each new vertex is then denoted as an ordered triple (i;j;x) where i2f0;1;2;3;4;5;6;7g (the part), j2f0;1;2g (the row) and x2Z +1nf0g. These vertices are then grouped into two new sections Lx and Rx, x2Z +1 as follows 26 (0,0) (1,0) (2,0) (3,0) (4,0) (0,0) (1,0) (2,0) (3,0) (4,0) (0,0) (1,0) (2,0) (3,0) (4,0) (0,0) (1,0) (2,0) (3,0) (4,0) (0,1) (1,1) (2,1) (3,1) (4,1) (0,1) (1,1) (2,1) (3,1) (4,1) (0,1) (1,1) (2,1) (3,1) (4,1) (0,1) (1,1) (2,1) (3,1) (4,1) F2?G2 F3?G3 F4?G4 F5?G5 Figure 3.12: Fi[Gi;1 i 4 Lx = f(0;0;x);(0;1;x);(0;2;x);(0;3;x);(1;0;x);(1;1;x);(1;2;x);(1;3;x); (2;0;x);(2;1;x);(2;2;x);(2;3;x)g, and Rx = f(0;4;x);(0;5;x);(0;6;x);(0;6;x);(1;4;x);(1;5;x);(1;6;x);(1;7;x); (2;4;x);(2;5;x);(2;6;x);(2;7;x)g So, our vertex set isfZ7 Z3gSfZ8 Z3 Z +1nf0gg. Thus, for each x2Z +1nf0g, Lx =fZ4 Z3 fxggnf(2;2;x);(3;2;x)gSf(4;0;x);(5;0;x)gand Rx =fZ4 Z3 fxggnLx. Therefore, V(Kpn) = LSRSfvg, where v = (3;1;0), L = Sx2Z Lx, and R = Sx2Z Rx. This can be viewed in Figure 3.13. As before, our aim is to produce a set of colored edges E(S) in G = Kpn that form m = 3p 14 = 6x+ 5 hamilton cycles such that in the complement, G E(S), v is a cut vertex ensuring that our set is indeed maximal. The edges chosen are as follows: Type 1: All edges that join a vertex in L to a vertex in R. 27 v L0L1L? L1 L? R0 R1 R?R1R? Figure 3.13: Set up of K7+8 3 Type 2: All special edges from the p = 7 case. (These were denoted as Type 2 and Type 3 edges previously.) Type 3: Speci c edges incident with v, along with edges among vertices of Lx and edges among vertices of Rx, namelyffv;(i;j;x)gji2f2;3g;j2f0;1g;1 x g[ffv;(i;j;x)gj i 2f4;5g;j 2f1;2g;1 x g[ffv;(i;j;x)gj i 2f2;3g;j = 2;1 x g[ ffv;(i;j;x)gji2f4;5g;j = 0;1 x g[ff(2;2;x);(3;2;x)g;f(4;0;x);(5;0;x)ggj 1 x g. (These are shown in Figure 3.14.) v L0L1 L1 R0 R1R1 Figure 3.14: Type 3 Edges It remains to show that these edges induce a graph which has a hamilton decomposition. To do so, the technique of amalgamations will be used to aid in the proof. The amalgamation function f : V(G[E(S)]) !V(H) is de ned as follows and is pictured in Figure 3.15. For all vertices in L0[R0[v, f(i;j;0) = f(i;j), where f(i;j) is de ned in the proof of Theorem 3.1. If x2f1;:::; g, then 28 f(i;j;x) = 8 >>> >>>> >>> >>> >< >>>> >>> >>> >>>> : (i;0;x) if i2f0;1g; (i;0;x) if i2f2;3g and j20;1; (i;0;x) if i2f4;5g and j = 0; (i;2;x) if i2f2;3g and j = 2; (i;2;x) if i2f4;5g and j2f1;2g; (i;2;x) if i2f6;7g: L0 R0 R1 L1 v L1 R1 Figure 3.15: The Amalgamated Graph H; the size of the vertex indicated its amalgamation number It is helpful now to shift our view of this amalgamated graph to where the Li?s and Ri?s each form a column. Our special vertex v is then pictured above these columns in the center (see Figure 3.16). Vertices in the same row have the same amalgamation number. Now, we must color our edge set so that conditions (1-4) of Lemma 1.1 are satis ed in order that Theorem 1.3 can be applied. This is done by coloring the graph in small pieces and then connecting them afterward. These small pieces consist of the trails, denoted T1(x);T2(x);:::;T6(x), and hamilton cycles on the vertices of Li and Rj, denoted H(i;j;c). Recall from Chapter 1 that trails are denoted using brackets and cycles are denoted using parentheses. These pieces are de ned as follows: Hamilton cycles on the vertices in L0 and R0: Use the same construction of ve hamilton cycles in the proof of Theorem 3.1. We now rename these H(0;0;c), c2Z5 and picture them in Figure 3.17. Eulerian Trails on the vertices in L0, Rx, Lx and R0, 1 x : The edges of these trails are de ned below. Each trail is de ned so that (1) it spans the vertices 29 v L0 R0 (0,0,0) (1,0,0) (2,0,0) (3,0,0) (4,0,0) (5,0,0) (5,2,0) (4,2,0) (3,2,0) (2,2,0) (6,2,0) (1,2,0) L1 R1 L? R? (0,0,1) (1,0,1) (2,0,1) (3,0,1) (4,0,1) (5,0,1) (0,0,?) (1,0,?) (2,0,?) (3,0,?) (4,0,?) (5,0,?) (7,2,1) (6,2,1) (5,2,1) (4,2,1) (3,2,1) (2,2,1) (7,2,?) (6,2,?) (5,2,?) (4,2,?) (3,2,?) (2,2,?) Figure 3.16: Column View of Amalgamated Graph fvg[L0[R0[Lx[Rx (where x2Z nf0g), and (2) each vertex has degree 2 except for (0;0;x), (1;0;x), (6;2;x), and (7;2;x), which each have degree 4. We begin de ning our trails with a subtrail T0i(x). For each x2f1;:::; g, let T00(x) = [(2;2;x);(0;0;0);(6;2;x);(2;0;0);(6;2;x);(5;0;0);(7;2;x); (3;0;0);(5;2;x);(1;0;0);(4;2;x);(4;0;0);(7;2;x)] T01(x) = [(2;2;x);(0;0;0);(6;2;x);(2;0;0);(7;2;x);(3;0;0);(3;2;x) (5;0;0);(4;2;x);(1;0;0);(5;2;x);(4;0;0);(7;2;x)] T02(x) = [(4;2;x);(3;0;0);(6;2;x);(2;0;0);(2;2;x);(0;0;0);(7;2;x); (4;0;0);(3;2;x);(1;0;0);(5;2;x);(5;0;0);(7;2;x)] 30 L0 R0 (0,0,0) (1,0,0) (2,0,0) (3,0,0) (4,0,0) (5,0,0) (5,2,0) (4,2,0) (3,2,0) (2,2,0) (6,2,0) (1,2,0) v L0 R0 (0,0,0) (1,0,0) (2,0,0) (3,0,0) (4,0,0) (5,0,0) (5,2,0) (4,2,0) (3,2,0) (2,2,0) (6,2,0) (1,2,0) v L0 R0 (0,0,0) (1,0,0) (2,0,0) (3,0,0) (4,0,0) (5,0,0) (5,2,0) (4,2,0) (3,2,0) (2,2,0) (6,2,0) (1,2,0) v H(0,0,1) H(0,0,2) H(0,0,3) H(0,0,4) H(0,0,5) L0 R0 (0,0,0) (1,0,0) (2,0,0) (3,0,0) (4,0,0) (5,0,0) (5,2,0) (4,2,0) (3,2,0) (2,2,0) (6,2,0) (1,2,0) v L0 R0 (0,0,0) (1,0,0) (2,0,0) (3,0,0) (4,0,0) (5,0,0) (5,2,0) (4,2,0) (3,2,0) (2,2,0) (6,2,0) (1,2,0) v Figure 3.17: Hamilton Cycles H(0;0;c), 1 c 5 T03(x) = [(4;2;x);(5;0;0);(2;2;x);(2;0;0);(7;2;x);(0;0;0);(3;2;x); (1;0;0);(5;2;x);(4;0;0);(6;2;x);(3;0;0);(6;2;x)] T04(x) = [(5;2;x);(3;0;0);(4;2;x);(1;0;0);(2;2;x);(4;0;0);(6;2;x); (5;0;0);(7;2;x);(2;0;0);(3;2;x);(0;0;0);(6;2;x)] T05(x) = [(5;2;x);(5;0;0);(6;2;x);(4;0;0);(4;2;x);(1;0;0);(2;2;x); (3;0;0);(7;2;x);(2;0;0);(3;2;x);(0;0;0);(7;2;x)] Now, for each trail T0(x), let g(T0(x)) be the trail formed by replacing each vertex u2V(T0(x)) with the vertex g(u), where g is de ned by: g(i;0;x) = 8 >>< >>: (7 i;2;x) if i2Z8 and x2Z nf0g; (6 i;2;x) if i2Z7 and x = 0; and g2 is the identity map on V: De ne the required trails as follows: 31 T0(x) = T00(x)[g(T00(x))[[(5;0;x);(4;0;x);v;(3;2;x);(2;2;x)][[(0;0;x);(7;2;x)] T1(x) = T01(x)[g(T01(x))[[(5;0;x);v;(2;2;x)][[(1;0;x);(6;2;x);(1;0;x)][[(0;0;x);(7;2;x)] T2(x) = T02(x)[g(T02(x))[[(3;0;x);v;(4;2;x)][[(0;0;x);(6;2;x);(1;0;x);(7;2;x)] T3(x) = T03(x)[g(T03(x))[[(3;0;x);v;(4;2;x)][[(1;0;x);(7;2;x);(0;0;x);(6;2;x)] T4(x) = T04(x)[g(T04(x))[[(2;0;x);v;(5;2;x)][[(1;0;x);(7;2;x);(0;0;x);(6;2;x)] T5(x) = T05(x)[g(T05(x))[[(2;0;x);v;(5;2;x)][[(0;0;x);(6;2;x);(1;0;x);(7;2;x)] Hamilton cycles on the vertices in Lx and Ry, for 1 x;y : These cycles are de ned below and pictured in Figure 3.19. H(i;j;0) = ((0;0;x);(2;2;y);(5;0;x);(7;2;y);(4;0;x);(6;2;y);(3;0;x); (5;2;y);(2;0;x);(4;2;y);(1;0;x);(3;2;y)) H(i;j;1) = ((0;0;x);(3;2;y);(1;0;x);(2;2;y);(2;0;x);(7;2;y);(3;0;x); (6;2;y);(5;0;x);(5;2;y);(4;0;x);(4;2;y)) H(i;j;2) = ((0;0;x);(2;2;y);(4;0;x);(3;2;y);(3;0;x);(7;2;y);(2;0;x); (6;2;y);(5;0;x);(4;2;y);(1;0;x);(5;2;y)) H(i;j;3) = ((0;0;x);(4;2;y);(5;0;x);(3;2;y);(2;0;x);(6;2;y);(4;0;x); (7;2;y);(3;0;x);(2;2;y);(1;0;x);(5;2;y)) H(i;j;4) = ((0;0;x);(2;2;y);(1;0;x);(4;2;y);(4;0;x);(7;2;y);(5;0;x); (5;2;y);(3;0;x);(6;2;y);(2;0;x);(3;2;y)) H(i;j;5) = ((0;0;x);(4;2;y);(1;0;x);(3;2;y);(3;0;x);(2;2;y);(2;0;x); (7;2;y);(5;0;x);(6;2;y);(4;0;x);(5;2;y)) Hamilton cycles on the vertices in Lx and Rx for 1 x : These cycles are de ned below and shown in Figure 3.20. 32 L0 R0 (0,0,0) (1,0,0) (2,0,0) (3,0,0) (4,0,0) (5,0,0) (5,2,0) (4,2,0) (3,2,0) (2,2,0) (6,2,0) (1,2,0) Li Ri v T0(x) (0,0,x) (1,0,x) (2,0,x) (3,0,x) (4,0,x) (5,0,x) (7,2,x) (6,2,x) (5,2,x) (4,2,x) (3,2,x) (2,2,x) L0 R0 (0,0,0) (1,0,0) (2,0,0) (3,0,0) (4,0,0) (5,0,0) (5,2,0) (4,2,0) (3,2,0) (2,2,0) (6,2,0) (1,2,0) Li Ri v T1(x) (0,0,x) (1,0,x) (2,0,x) (3,0,x) (4,0,x) (5,0,x) (7,2,x) (6,2,x) (5,2,x) (4,2,x) (3,2,x) (2,2,x) L0 R0 (0,0,0) (1,0,0) (2,0,0) (3,0,0) (4,0,0) (5,0,0) (5,2,0) (4,2,0) (3,2,0) (2,2,0) (6,2,0) (1,2,0) Li Ri v T2(x) (0,0,x) (1,0,x) (2,0,x) (3,0,x) (4,0,x) (5,0,x) (7,2,x) (6,2,x) (5,2,x) (4,2,x) (3,2,x) (2,2,x) L0 R0 (0,0,0) (1,0,0) (2,0,0) (3,0,0) (4,0,0) (5,0,0) (5,2,0) (4,2,0) (3,2,0) (2,2,0) (6,2,0) (1,2,0) Li Ri v T3(x) (0,0,x) (1,0,x) (2,0,x) (3,0,x) (4,0,x) (5,0,x) (7,2,x) (6,2,x) (5,2,x) (4,2,x) (3,2,x) (2,2,x) L0 R0 (0,0,0) (1,0,0) (2,0,0) (3,0,0) (4,0,0) (5,0,0) (5,2,0) (4,2,0) (3,2,0) (2,2,0) (6,2,0) (1,2,0) Li Ri v T4(x) (0,0,x) (1,0,x) (2,0,x) (3,0,x) (4,0,x) (5,0,x) (7,2,x) (6,2,x) (5,2,x) (4,2,x) (3,2,x) (2,2,x) L0 R0 (0,0,0) (1,0,0) (2,0,0) (3,0,0) (4,0,0) (5,0,0) (5,2,0) (4,2,0) (3,2,0) (2,2,0) (6,2,0) (1,2,0) Li Ri v T5(x) (0,0,x) (1,0,x) (2,0,x) (3,0,x) (4,0,x) (5,0,x) (7,2,x) (6,2,x) (5,2,x) (4,2,x) (3,2,x) (2,2,x) Figure 3.18: Coloring Tc(x) with 6x+c 33 Li Rj Li Rj Li Rj Li Rj Li Rj Li Rj H(i,j,0) H(i,j,1) H(i,j,2) H(i,j,3) H(i,j,4) H(i,j,5) (0,0,x) (1,0,x) (2,0,x) (3,0,x) (4,0,x) (5,0,x) (7,2,y) (6,2,y) (5,2,y) (4,2,y) (3,2,y) (2,2,y) (0,0,x) (1,0,x) (2,0,x) (3,0,x) (4,0,x) (5,0,x) (7,2,y) (6,2,y) (5,2,y) (4,2,y) (3,2,y) (2,2,y) (0,0,x) (1,0,x) (2,0,x) (3,0,x) (4,0,x) (5,0,x) (7,2,y) (6,2,y) (5,2,y) (4,2,y) (3,2,y) (2,2,y) (0,0,x) (1,0,x) (2,0,x) (3,0,x) (4,0,x) (5,0,x) (7,2,y) (6,2,y) (5,2,y) (4,2,y) (3,2,y) (2,2,y) (0,0,x) (1,0,x) (2,0,x) (3,0,x) (4,0,x) (5,0,x) (7,2,y) (6,2,y) (5,2,y) (4,2,y) (3,2,y) (2,2,y) (0,0,x) (1,0,x) (2,0,x) (3,0,x) (4,0,x) (5,0,x) (7,2,y) (6,2,y) (5,2,y) (4,2,y) (3,2,y) (2,2,y) Figure 3.19: Coloring H(i;j;c) with 6x+c 34 H(i;i;1) = ((0;0;x);(5;2;x);(1;0;x);(3;2;x);(2;0;x);(7;2;x);(4;0;x); (6;2;x);(5;0;x);(4;2;x);(3;0;x);(2;2;x)) H(i;i;2) = ((0;0;x);(3;2;x);(4;0;x);(5;2;x);(3;0;x);(6;2;x);(2;0;x); (7;2;x);(5;0;x);(4;2;x);(1;0;x);(2;2;x)) H(i;i;3) = ((0;0;x);(4;2;x);(2;0;x);(5;2;x);(1;0;x);(2;2;x);(4;0;x); (6;2;x);(3;0;x);(7;2;x);(5;0;x);(3;2;x)) H(i;i;4) = ((0;0;x);(4;2;x);(3;0;x);(5;2;x);(4;0;x);(7;2;x);(5;0;x); (6;2;x);(2;0;x);(3;2;x);(1;0;x);(2;2;x)) H(i;i;5) = ((0;0;x);(4;2;x);(2;0;x);(7;2;x);(4;0;x);(6;2;x);(5;0;x); (2;2;x);(3;0;x);(5;2;x);(1;0;x);(3;2;x)) Let F and G be 1-factorizations of K +1; +1 satisfying Conditions (1-3) of Conjecture 3.1. Associate the 1-factor Fx (for 1 x ) with the colors 6x, 6x + 1, 6x + 2, 6x + 3, 6x+ 4, and 6x+ 5 as follows. (Note that F0 will be associated with only the colors 1, 2, 3, 4, and 5. These ve colors correspond the the construction of K73, where there is no color 0.) For each edge f(a;0);(b;1)g, a;b6= 0, in Fx, x > 0, the hamilton cycles H(a;b;c), for each c2Z6 are colored 6x + c. For each of the edges f(a;0);(0;1)g and f(0;0);(b;1)g in Fx, we use the trails T0(x);T1(x);:::;T5(x) given in Figure 3.18, coloring Tc with 6x+c. For F0 we have that all edges are of the form f(a;0);(a;1)g. For a6= 0, we color the cycles of Figure 3.20, denoted by H(i;i;c), with colors 1, 2, 3, 4, and 5. Edge f(0;0);(0;1)g corresponds to the 5 hamilton cycles constructed for K73 that are colored as in the proof of Theorem 3.1. At this point, we note that almost every vertex is incident with exactly 2 edges of each color. The only exceptions are all the vertices (i;j;x) with amalgamation number 3 and x 1, namely (0;0;x), (1;0;x), (7;2;x), and (6;2;x), for all x 2f1;2;:::; g; these exceptional vertices are incident with 4 edges of colors 6x, 6x + 1, 6x + 2, 6x + 3, 6x + 4, and 6x+ 5 and with 2 edges of all other colors. 35 Li Ri Li Ri Li Ri Li Ri Li Ri H(i,i,1) H(i,i,2) H(i,i,3) H(i,i,4) H(i,i,5) (0,0,x) (1,0,x) (2,0,x) (3,0,x) (4,0,x) (5,0,x) (7,2,x) (6,2,x) (5,2,x) (4,2,x) (3,2,x) (2,2,x) (0,0,x) (1,0,x) (2,0,x) (3,0,x) (4,0,x) (5,0,x) (7,2,x) (6,2,x) (5,2,x) (4,2,x) (3,2,x) (2,2,x) (0,0,x) (1,0,x) (2,0,x) (3,0,x) (4,0,x) (5,0,x) (7,2,x) (6,2,x) (5,2,x) (4,2,x) (3,2,x) (2,2,x) (0,0,x) (1,0,x) (2,0,x) (3,0,x) (4,0,x) (5,0,x) (7,2,x) (6,2,x) (5,2,x) (4,2,x) (3,2,x) (2,2,x) (0,0,x) (1,0,x) (2,0,x) (3,0,x) (4,0,x) (5,0,x) (7,2,x) (6,2,x) (5,2,x) (4,2,x) (3,2,x) (2,2,x) Figure 3.20: Coloring H(i;i;c) with 6x+c 36 It is also important to note that the cycles and trails used to color the edges so far purposely did not use many edges between vertices with amalgamation number 3. Namely, there are no edges between vertices in f(0;0;x);(1;0;x)g and vertices in f(7;2;y);(6;2;y)g for 1 x;y , x 6= y. For 1 x , there are precisely 4 (of the 9) edges joining vertices inf(0;0;x);(1;0;x)gto vertices inf(7;2;x);(6;2;x)gcolored so far. For 1 x , there are exactly 3 edges used between (0;0;0) and (7;2;x), (0;0;0) and (6;2;x), (6;2;0) and (0;0;x), and (6;2;0) and (1;0;x). There are no edges used between the vertex (1;0;0) (which has amalgamation number two) and vertices in f(7;2;x);(6;2;x)g for 1 x and, symmetrically, no edges used between (5;2;0) (which also has amalgamation number two) and vertices in f(0;0;x);(1;0;x)g for 1 x . We have done this to allow room to connect our color classes. Most importantly, there are at least six edges left between vertices mentioned above, with the exception that there are only ve left between vertices in f(0;0;x);(1;0;x)g and vertices in f(7;2;x);(6;2;x)g for 1 x . Tables 3.1, 3.2, 3.3, and 3.4 summarize this information. Each cell gives the number of edges used between the vertices given in the heading of the row and column. Each cell is further divided into a 2 3 table, with cell (1;1) corresponding to the hamilton cycle or eulerian trail colored 6x, cell (1;2) corresponding to the hamilton cycle or eulerian trail colored 6x+ 1, etc. We now connect our color classes. To do so, we either use Conditions (2-3) of Conjecture 3.1 or we use results from [5] and [2], so we present each in turn. Using Conjecture 3.1 to connect the color classes By Condition (2) of Conjecture 3.1, the rainbow one factor appears as the \horizontal" edges. For 1 x and for each edge f(a;0);(b;1)g2Gx with a6= b (so by Condition 2 of Conjecture 3.1, a6= x), color six copies of the 4-cycle ((0;0;i);(7;2;j);(1;0;i);(6;2;j)), the cth copy being colored with 6x + c where c 2 Z6. Note that this boosts the degree of the vertices involved to four in each color class. (We leave out edges where a = b both because vertices in Li and Ri are already connected in those color classes by the construction of Tc(x), and because the vertices (0;0;x);(1;0;x);(7;2;x); and (6;2;x) for 1 x are 37 (7,2,y) (6,2,y) (5,2,y) (4,2,y) (3,2,y) (2,2,y) = 3 = 3 = 2 = 2 = 1 = 1 (0,0,x) 1 1 1 1 1 1 = 3 1 1 1 1 1 1 (1,0,x) 1 1 1 1 1 1 = 3 1 1 1 1 1 1 (2,0,x) 1 1 1 1 1 1 = 2 1 1 1 1 1 1 (3,0,x) 1 1 1 1 1 1 = 2 1 1 1 1 1 1 (4,0,x) 1 1 1 1 1 1 = 1 1 1 1 1 1 1 (5,0,x) 1 1 1 1 1 1 = 1 1 1 1 1 1 1 Table 3.1: Number of Edges used in H(i;j;c) with 0 c 5, broken down by color class (7,2,x) (6,2,x) (5,2,x) (4,2,x) (3,2,x) (2,2,x) = 3 = 3 = 2 = 2 = 1 = 1 (0,0,x) 1 1 1 1 1 1 = 3 1 1 1 1 (1,0,x) 1 1 1 1 1 1 = 3 1 1 1 1 (2,0,x) 1 1 1 1 1 1 = 2 1 1 1 1 (3,0,x) 1 1 1 1 1 1 = 2 1 1 1 1 (4,0,x) 1 1 1 1 1 1 = 1 1 1 1 1 (5,0,x) 1 1 1 1 1 1 = 1 1 1 1 1 Table 3.2: Number of Edges used in H(i;i;c) with 1 c 5, broken down by color class 38 (7,2,x) (6,2,x) (5,2,x) (4,2,x) (3,2,x) (2,2,x) = 3 = 3 = 2 = 2 = 1 = 1 (0,0,0) 1 1 1 1 1 1 = 3 1 1 1 1 1 1 (1,0,0) 1 1 1 1 1 1 = 2 1 1 1 1 1 1 (2,0,0) 1 2 1 1 1 = 2 1 1 1 1 1 1 (3,0,0) 1 1 1 1 1 1 = 1 1 2 1 1 1 (4,0,0) 1 1 1 1 1 1 = 1 1 1 1 1 1 1 (5,0,0) 1 1 1 1 1 1 = 1 1 1 1 1 1 1 Table 3.3: Number of Edges used in Tc(x) with 0 c 5, broken down by color class (6,2,0) (5,2,0) (4,2,0) (3,2,0) (2,2,0) (1,2,0) = 3 = 2 = 2 = 1 = 1 = 1 (0,0,0) 1 1 1 1 1 1 = 3 1 1 1 1 (1,0,0) 1 1 1 1 1 = 2 1 1 1 (2,0,0) 1 1 1 1 1 = 2 1 1 1 (3,0,0) 1 1 1 1 1 = 1 1 1 1 1 (4,0,0) 1 1 1 1 = 1 1 1 1 1 (5,0,0) 1 1 1 1 = 1 1 1 1 1 Table 3.4: Number of Edges used in H(0;0;c) with 1 c 5, broken down by color class 39 are already boosted to degree four in each color class.) By Condition (3) of Conjecture 3.1, Fi[Gi forms a hamilton cycle for each i2Z nf0g, so all color classes except for colors 1, 2, 3, 4, and 5 are now connected. We connect color classes 1,2,3,4, and 5 using the following cycles. First suppose that is even. Color three copies of each of the four cycles (e ;j;1;e ;j;2;:::;e ;j; ) for ;j2Z2, the dth copy of each cycle being colored with d for 1 d 3, where e ;j;i = 8 >>> >>>> < >>>> >>> : ( ;0;i) if i is odd and j = 0; (7 ;2;i) if i is even and j = 0; (7 ;2;i) if i is odd and j = 1; ( ;0;i) if i is even and j = 1: Color two copies of each of the four cycles (e ;j;1;e ;j;2;:::;e ;j; ) for ;j2Z2, the dth copy of each cycle being colored with d+ 3 for 1 d 2, where e ;j;i = 8 >>> >>>> < >>> >>> >: ( ;0;i) if i is odd and j = 0; (6 + ;2;i) if i is even and j = 0; (6 + ;2;i) if i is odd and j = 1; ( ;0;i) if i is even and j = 1: Next suppose that is odd. Color three copies of each of the two cycles (e ;1;e ;2;:::;e ;2 ) for 2Z2, the dth copy of each cycle being colored with d for 1 d 3, where e ;j;i = 8> < >: ( ;0;i0) if i is odd and j = 0; (7 ;2;i0) if i is even and j = 0; where i0 is de ned by: i0 = 8 >< >: i if i ; i if i> : 40 Color two copies of each of the four cycles (e ;1;e ;2;:::;e ; ) for 2Z2, the dth copy of each cycle being colored with d+ 3 for 1 d 2, where e ;i = 8 >< >: ( ;0;i0) if i is odd and j = 0; (6 + ;2;i0) if i is even and j = 0; where i0 is de ned by: i0 = 8 >< >: i if i ; i if i> : Using Theorem 3.3 to connect the color classes For our purposes, we need an almost resolvable -cycle decompositionX = (X0;:::;X ) of 2K +1 on the vertex set Z +1; by Theorem 3.3, this decomposition exists for 3. We connect our color classes using these + 1 -cycles. First suppose that is even. For any X = (x1;:::;x )2X, de ne four cycles E( ;j;X = (x1;:::;x );straight) = (e ;j;1;e ;j;2;:::;e ;j; ) for ;j2Z2, where for 1 i e ;j;i = 8 >>> >>>> < >>> >>> >: ( ;0;xi) if i is odd and j = 0; (7 ;2;xi) if i is even and j = 0; (7 ;2;xi) if i is odd and j = 1; ( ;0;xi) if i is even and j = 1: For any X = (x1;:::;x )2X de ne four cycles E( ;j;X = (x1;:::;x );crossed) = (e ;j;1;e ;j;2;:::;e ;j; ) for ;j2Z2, where for 1 i e ;j;i = 8 >>> >>>> < >>> >>> >: ( ;0;xi) if i is odd and j = 0; (6 + ;2;xi) if i is even and j = 0; (6 + ;2;xi) if i is odd and j = 1; ( ;0;xi) if i is even and j = 1: 41 De ne C(X;straight) = E(0;0;X;straight)[E(1;0;X;straight)[E(0;1;X;straight) [E(1;1;X;straight) and C(X;crossed) = E(0;0;X;crossed)[E(1;0;X;crossed)[ E(0;1;X;crossed)[E(1;1;X;crossed). Note that C(X;straight) and C(X;crossed) are each 2-factors on the vertex set f(0;0;x);(1;0;x);(7;2;x);(6;2;x)jx2V(X)gnf(0;0;d(X)); (1;0;d(X));(7;2;d(X));(6;2;d(X))g. For each X2X, if d(X)6= 0 then color three copies of C(X;straight), the dth copy being colored with 6d(X) + d for 0 d 2. If d(X) = 0, then just color two copies of C(X;straight), one with color 1 and one with color 2. For each X 2X, color three copies of C(X;crossed), the dth copy being colored with 6d(X) + d for 3 d 5. Next suppose that is odd. For any X = (x1;:::;x ) 2X de ne two cycles E( ;X = (x1;:::;x );straight) = (e ;1;e ;2;:::;e ;2 ) for 2Z2, where for 1 i 2 e ;j;i = 8 >< >: ( ;0;xi0) if i is odd; (7 ;2;xi0) if i is even; where i0 is de ned by: i0 = 8> < >: i if i ; i if i> : For anyX = (x1;:::;x )2X de ne two cyclesE( ;X = (x1;:::;x );crossed) = (e ;1;e ;2;:::;e ; ) for 2Z2, where for 1 i 2 e ;i = 8 >< >: ( ;0;xi0) if i is odd; (6 + ;2;xi0) if i is even; where i0 is de ned by: i0 = 8> < >: i if i ; i if i> : De ne C(X;straight) = E(0;X;straight)[E(1;X;straight) and C(X;crossed) = E(0;X;crossed)[E(1;X;crossed). Note that C(X;straight) and C(X;crossed) are each 42 2-factors on the vertex set f(0;0;x);(1;0;x);(7;2;x);(6;2;x)jx2V(X)gnf(0;0;d(X)); (1;0;d(X));(7;2;d(X));(6;2;d(X))g. For each X2X, if d(X)6= 0 then color three copies of C(X;straight), the dth copy being colored with 6d(X) + d for 0 d 2. If d(X) = 0, then just color two copies of C(X;straight), one with color 1 and one with color 2. For each X 2X, color three copies of C(X;crossed), the dth copy being colored with 6d(X) + d for 3 d 5. Continuing for both Conjecture 3.1 and Using Theorem 3.3 Color classes 1;2;3;4; and 5 now consist of two components, with the vertices (i;j;0) inducing one of the two components. Each of the color classes 6;:::;6 + 5 is connected because for each X2X: (i) X spans all vertices except d(X)2Z +1, and (ii) by (1) of the de nition of F and Tc(d(X)) for 0 c 5, the vertices (i0;j0;d(X)) are joined to vertices in (i;j;0) by edges colored 6d(X) +c. For each vertex u 2 V(H), if u 62 T = f(0;0;0);(1;0;0);(6;2;0);(5;2;0)g then u = (i;j;x) is incident with the same number of edges of each color as of each other color (namely 4 if (i;j) 2f(0;0), (1;0), (6;2), (7;2)g and 2 otherwise). If u2T then it has degree 4 in each color class except for colors 1,2,3,4, and 5. in which it has degree two. In order for the use of the evenly equitable edge-coloring in the next paragraph to work, it is critical that the degrees of these vertices in each of the ve color classes be raised to 4, except possibly for one pair of vertices in one color class. Since vertices (1;0;0) and (5;2;0) have amalgamation number two, there are only four edges between them in H, so we cannot simply use ve C4?s as we did when connecting our color classes. (In fact, we have already used one of the edges between (1;0;0) and (5;2;0) in H(0;0;1), so we cannot even place four 4-cycles there.) To boost the degree of these vertices in the rst ve color classes, take three copies of the 4-cycle ((0;0;0);(6;2;0);(1;0;0);(5;2;0)) and color them using colors 1,2, and 3. Take the 2-cycles ((0;0;0);(5;2;0)) and ((1;0;0);(6;2;0)) and color them using color 4. Finally, take the 2-cycle ((0;0;0);(6;2;0)) and color it with color 5. So, the vertices (0;0;0) and (6;2;0) are now incident with four edges of each color c, 1 c 6 + 5. Vertices (1;0;0) and 43 (5;2;0), however, are each incident with four of every color, except only two edges of color 5. De ne G to be the subgraph induced by uncolored edges of S. Note that this is precisely the edges in S not used in the trails or cycles described previously. The degree of each vertex in E(S) is divisible by 2(6 +5), except for vertices (1;0;0) and (5;2;0) which have degree 2 (mod 2(6 + 5)). Apply an evenly equitable edge-coloring with the colors 1;2;:::;6 + 5 to the edges in G. This edge-coloring has the property that at each vertex each color appears on the same number of edges as each other color, except that one color appears twice more than each other color at the vertex (1;0;0) and (5;2;0) since G is bipartite, necessarily the color appearing twice more at those vertices is the same, so name this color 5. It is also important to note that this edge coloring connects the color classes 1, 2, 3, 4, and 5, which were previously in two components. Let G0 be the subgraph induced by the vertices of L0[R0 in G. Note that the vertex (0;0;0) has degree ten in G0, so the evenly equitable edge coloring will produce at most 5 colors on edges to vertices in L0 [R0. So, at least 6 + 5 5 = 6 colors must be on edges joining (0;0;0) to vertices not in L0[R0. Since a 4, 6 > 5. Name ve of these 6 colors 1;2;3;4; and 5. The component previously induced by the vertices of L0[R0 is now connected with the second component spanning the rest of the graph. Now, we must disentangle the graph. We will use the same method as with the other cases. To be able to apply Lemma 1.1, we need to add edges to our graph H so that it is the amalgamation of the complete graph K3p. All of these additional edges and loops are colored 0. We call this new graph H+ and note that it now satis es the conditions of Lemma 1.1. Thus we apply Theorem 1.3 to H+ to produce G+, which is an edge-colored copy of K3p. We now remove all edges in G+ colored 0; the resulting graph is Kp3. Using Theorem 1.3, we see that each color class is 2-regular by (i) and connected by (ii), which implies that each color class is a hamilton cycle. We now consider G E(S). Note that all edges between 44 vertices in L0 and R0 were in E(S), so we have that G E(S) has cut vertex v. So our set of hamilton cycles is maximal. So this chapter culminates in the following state of knowledge: Theorem 3.5 There exists a maximal set of m hamilton cycles in Kpn if and only if 1. l n(p 1) 4 m m j n(p 1) 2 k and 2. m> n(p 1)4 if (a) n is odd and p 1 (mod 4)), or (b) p = 2, or (c) n = 1, except possibly when n = 3, m = l n(p 1) 4 m and either p 3 (mod 8), p 19 or p2f15;23g. 45 Bibliography [1] D.E. Bryant, S. El-Zanati and C.A. Rodger, Maximal Sets of Hamilton Cycles in Kn;n. J. Graph Theory. 33(2000), 25-31. [2] J. Burling, K. Heinrich. Near 2-factorizations of 2Kn: Cycles of Even Length. Graphs Combin. 5(1989), 213-221. [3] M.D. Daven, J.A. McDougall and C.A. Rodger, Maximal Sets of Hamilton Cycles in Complete Multipartite Graphs. J. Graph Theory 43(2003), 49-66. [4] H.L. Fu, S.L. Logan and C.A. Rodger, Maximal Sets of Hamilton Cycles in K2p F. Discrete Math 308(2008), 2822-2829. [5] K. Heinrich, C.C. Lindner and C.A. Rodger, Almost Resolvable Decompositions of 2Kn into Cycles of Odd Length. J Combin. Theory Ser. A 49(1988), 218-232. [6] A.J.W. Hilton, Edge-Colourings of Locally Finite Graphs. Combinatorica. 2(1982), 37- 51. [7] D.G. Ho man, C.A. Rodger and A. Rosa, Maximal Sets of 2-Factors and Hamiltonian Cycles. J. Combin. Theory Series B, 57(1993), 69-76. [8] S.L.Jarrell, C.A. Rodger, Maximal Sets of Hamilton Cycles in Complete Multipartite Graphs II. Aust. J. Combinatorics 39(2007), 207-217. [9] C.D. Leach, C.A. Rodger, Nondisconnecting Disentanglements of Amalgamated 2- Factorizations of Complete Multipartite Graphs. J. Combin. Designs 9(2001), 460-467. [10] C.D Leach, C.A. Rodger, Hamilton Decompositions of Complete Graphs with a 3-factor Leave. Discrete Math. 279(2004), 337-344. 46