Decomposition of Complete Tri-Partite Graphs into 5-Cycles by Chris Davis A thesis submitted to the Graduate Faculty of Auburn University in partial ful llment of the requirements for the Degree of Master of Science Auburn, Alabama May 5, 2013 Keywords: tri-partite, 5-cycle Copyright 2013 by Chris Davis Approved by Chris Rodger, Chair, Professor of Mathematics and Statistics Dean Ho man, Professor of Mathematics and Statistics Peter Johnson, Professor of Mathematics and Statistics Jessica McDonald, Professor of Mathematics and Statistics Abstract E. S. Mahmoodian gave necessary conditions for when the edges of a complete tripartite graph can be partitioned so that each set in the partition induces a 5-cycle. Since then, he, N. J. Cavenagh, E. J. Billington, S. Alipour, and E. Mollaahmadi have found several cases where these necessary conditions are also su cient. We continue this investigation by considering further cases for complete tripartite graphs. ii Acknowledgments I would like to thank my parents for all of their love and support. iii Table of Contents Abstract . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ii Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iii List of Figures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . v 1 History . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 2 A New Approach to Decomposing Complete Tripartite Graphs . . . . . . . . . . 11 2.0.1 A New Trade . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 2.0.2 Decomposition of K7;17;19 using this new approach . . . . . . . . . . . 16 3 Final Comments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34 Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35 Appendices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36 iv List of Figures 1.1 Types of 5-cycles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.2 Latin Representation of K5;5;7 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 1.3 A trade with n triangles and 2n edges . . . . . . . . . . . . . . . . . . . . . . . 8 2.1 Types of 5-cycles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 2.2 Example of the New Trade . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 2.3 Leave L1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 2.4 First Implementation of this New Trade . . . . . . . . . . . . . . . . . . . . . . 19 2.5 Second Implementation of this New Trade . . . . . . . . . . . . . . . . . . . . . 19 2.6 Leave L2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 2.7 Type 3 5-cycles removed and Leave L3 . . . . . . . . . . . . . . . . . . . . . . . 21 2.8 Type 2 5-cycles removed and Leave L4 . . . . . . . . . . . . . . . . . . . . . . . 22 2.9 First 4-path to be replaced along with the 5-cycle needed and Leave L5 . . . . . 23 2.10 Second 4-path to be replaced along with the 5-cycle needed and Leave L6 . . . . 24 2.11 Third 4-path to be replaced along with the 5-cycle needed and Leave L7 . . . . 25 2.12 Fourth 4-path to be replaced along with the 5-cycle needed the Leave L8 . . . . 26 v 2.13 Fifth 4-path to be replaced along with the 5-cycle needed and Leave L9 . . . . . 27 2.14 5-cycle removed and Leave L10 . . . . . . . . . . . . . . . . . . . . . . . . . . . 28 2.15 Fifth 4-path to be replaced along with the 5-cycle needed and Leave L11 . . . . 29 2.16 5-cycle removed and Leave L12 . . . . . . . . . . . . . . . . . . . . . . . . . . . 30 2.17 Sixth 4-path to be replaced along with the 5-cycle needed and Leave L13 . . . . 31 2.18 Final two 5-cycles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32 1 Covered latin representation of K7;17;19 by trades . . . . . . . . . . . . . . . . . 36 2 List of 5-cycles to which edges between R and S belong in Kr;s;t . . . . . . . . . 37 3 List of 5-cycles to which edges between R and T belong in Kr;s;t . . . . . . . . . 37 4 List of 5-cycles to which edges between S and T belong in Kr;s;t . . . . . . . . . 37 vi Chapter 1 History A graph, G, is said to be decomposable into a subgraph, H, if the edges of G can be partitioned into sets, each of which induces a copy of H. A bipartite graph is a graph in which the vertices can be partitioned into two groups such that no edges exist between any pair of vertices in the same group, but there may be an edge between a pair of vertices in di erent groups. A complete bipartite graph is a bipartite graph in which every possible edge exists; if the parts have sizes r and s then it is denoted by Kr;s. Similarly, a tripartite graph is a graph in which the vertices can be partitioned into three groups where no edges exist between any pair of vertices in the same group, but there may be an edge between a pair of vertices in di erent groups; if all such edges are in the graph then it is called complete, and is denoted by Kr;s;t, where r, s, and t are the sizes of each part. A cycle is a walk in a graph that starts and ends at the same vertex, but otherwise has no repeated vertices. In 1981, D. Sotteau[6] developed necessary and su cient conditions for decomposing complete bipartite graphs into cycles of any xed even length. More recently, in 1995 E. S. Mahmoodian and M. Mirzakhani[4] developed necessary conditions for decomposing com- plete tripartite graphs into 5-cycles, and conjectured that these conditions are also su cient. Since then several papers have been written trying to prove that these necessary conditions are also su cient. Many cases towards showing that these conditions are su cient have been settled, while several others are still open for investigation. Necessary conditions for the existence of a 5-cycle system of a tripartite graph Kr;s;t follow. 1 Theorem 1.1 [4] Let r s t. If there exists a decomposition of Kr;s;t into 5-cycles then the following conditions are satis ed: (i) r;s, and t are either all even or all odd; (ii) 5jrs+rt+st; and (iii) t 4rs (r +s) . These three conditions are necessary, as the following arguments show. (i) is necessary because clearly all vertices must have even degree since each vertex is incident with an even number of edges in each cycle. If only one part has odd size then the degrees of the vertices in the other parts will be odd, and if only one part has even size then the degrees of the vertices in the other parts will be odd. (ii) is necessary because the 5-cycles partition the edges of Kr;s;t, so the number of edges rs+rt+st must be a multiple of 5. Now, it is a little less obvious why (iii) is necessary. The basic idea here is that there cannot be too many vertices in the largest part in order for there to be a chance of using up all of the edges that are incident with vertices in this part. To prove (iii), Mahmoodian found three sets of inequalities that must be satis ed for a 5-cycle system to exist, one for each part of the graph. These inequalities were determined by the three types of 5-cycles that can exist, as pictured in Figure 1.1. 2 (a) Type 1 (b) Type 2 (c) Type 3 Figure 1.1: Types of 5-cycles It is clear that in each 5-cycle in Kr;s;t there must be exactly one edge or exactly three edges between vertices in any two of the three parts. We know that the number of 5-cycles is preciselyjE(Kr;s;t)j=5 = (rs+st+rt)=5, so the number of edges between any two parts must be greater than or equal to this number, and one third of the number of edges between any two parts must be less than or equal to this number. So, we get two inequalities for each pair of parts of the graph. For the parts of size r and s these inequalities are rs=3 (rs + st + rt)=5 and (rs + st + rt)=5 rs. Simply replace rs with st and then with rt to obtain the inequalities for the other two pairs of parts. By solving for each part size the following inequalities can be obtained: 2st 3(s+t) r 4st (s+t) 2rt 3(r +t) s 4rt (r +t) 2rs 3(r +s) t 4rs (r +s) The last of these three inequalities contains condition (iii). Notices that since t is the largest of these part sizes, requiring that t 4rs(r +s) forces the other bounds on the part sizes to hold. To see this, rearrange t 4rs(r +s) to obtain r st4s t 2st3(s+t) since 3 t s by assumption and similarly, s rt4r t 2rt3(r +t) since t r by assumption. To see the implication that s 4rt(r +t) we start with s t 4r2s+ 4rst 4r2t+ 4rst 4rs (r +s) 4rt (r +t) s t 4rs(r +s) 4rt(r +t) So, s 4rt(r +t), and similarly r t 4rs(r +s) 4st(s+t). Similar to the rst implica- tion we can see that r 4st(s+t) implies that t 2rs3(r +s). Mahmoodian goes on to conjecture that the necessary conditions given in Theorem 1.1 are also su cient. He then proves some very useful corollaries about when these conditions are su cient. First, if Kr;s;t admits a 5-cycle decomposition, then so does Kar;as;at for each positive integer a. Next, Kr;r;r admits a 5-cycle decomposition if and only if 5 jr. He also shows that for any positive integer n, K2n;2n;4n and Kn;3n;3n admit 5-cycle decompositions. The main result of Mahmoodian?s rst paper on decomposing complete tripartite graphs into 5-cycles was his theorem that Kr;s;t admits a 5-cycle decomposition if two of the parts have the same size and the necessary conditions are satis ed except possibly when the two parts have size divisible by 5 but the third does not. Theorem 1.2 [4] Suppose that at least two parts in a complete tripartite graph G have the same number of vertices, say G = Kr;r;s. And suppose that Kr;r;s satis es all three necessary conditions given in Theorem 1.1. Then Kr;r;s has a 5-cycle decomposition except possibly when r is a multiple of 5 but s is not. N.J. Cavenagh and E.J. Billington[2] introduced a new way to represent a complete tripartite graph by extending the idea of a latin square. An r s latin rectangle is an r s array, each cell being lled with one of n di erent symbols, with each symbol occurring at 4 most once in each row and at most once in each column. In [2] Kr;s;t is represented by starting with an r s latin rectangle R, the entries of R being elements of the set T =f1;2;::: ;tg, and nishes the representation by adding t s entries at the end of each row and t r entries at the end of each column so that each element of the set T =f1;2;::: ;tg appears exactly once in every row and exactly once in every column. (See Figure 1.2 for an example) 1 2 3 4 5 6 7 2 3 4 5 6 7 1 4 1 3 4 5 5 6 3 6 7 4 5 6 7 7 6 2 1 3 7 2 4 1 3 6 2 5 1 4 1 5 Figure 1.2: Latin Representation of K5;5;7 In this Latin Representation ofKr;s;t the numbers inside ther slatin rectangle represent a 3-cycle in Kr;s;t and the numbers outside of the latin rectangle represent single edges in Kr;s;t in the following way. Let the vertex set of Kr;s;t be f(v;w)jv 1, and v r;s; or t if w = 1;2 or 3 respectivelyg. The cell (i;j) in R containing symbol k corresponds to the 3-cycle ((i;1);(j;2);(k;3)) in Kr;s;t. Now, the edges that are not in the 3-cycles are either of the form f(i;1);(k;3)g, which is represented by k being an entry in row i outside of R, or f(j;2);(k;3)g, which is represented by k being an entry in column j outside of R. Cavenagh uses this latin representation to implement a technique known as a trade. De nition 1.1 [3] Let M be a Latin Representation of the complete tripartite graph Kr;s;t. A trade is a set of entries in M for which the corresponding 3-cycles and edges in Kr;s;t form a graph which can be decomposed into 5-cycles. For example, it is possible to form a trade using two entries corresponding to 3-cycles and four entries corresponding to edges. As the name suggests, these two 3-cycles and the four single edges contain ten edges which can be rearranged into two 5-cycles. 5 Cavenagh goes on to describe two di erent types of 5-cycle trades. A trade of Type 1 uses both 3-cycles and single edges, and in fact always uses exactly twice as many single edges, or entries from outside the latin rectangle, as 3-cycles, or entries from inside the latin rectangle. So, the di erent trades of Type 1 either use two 3-cycles and four single edges to obtain two 5-cycles or use three 3-cycles and six single edges to obtain three 5-cycles. A trade of Type 2 uses only 3-cycles, or entries from inside the latin rectangle. So, the di erent trades of Type 2 use ve 3-cycles to obtain three 5-cycles. Cavenagh then uses this method to show that the necessary conditions that Mahmoodian developed in [4] are also su cient for several new cases. He starts by nishing the case where two of the partite sets have the same size by considering the situation when the part sizes that are the same are divisible by 5 and the third part size is not, which was the exception Mahmoodian had in [4]. He goes on to complete the case when r and s are both divisible by 10. In [3] Cavenagh continues to use this method of trades described in [2] to complete the proof that the necessary conditions given by Mahmoodian in [4] are su cient for Kr;s;t when either two of the partite sets have the same size, or in the case where all partite sets have even size. He considered four cases to complete this, one of which he had completed in [2]. These four cases are: (A) Either r t 0 (modulo 10) and s is not divisible by 10 or s t 0 (modulo 10) and neither s nor t are divisible by 10. (B) Either s t 0 (modulo 10) and r is not divisible by 10 or r t (modulo 10) and neither r nor t are divisible by 10. (C) r s (modulo 10) and neither r nor s is divisible by 10. (D) r s 0 (modulo 10). E. J. Billington and N. J. Cavenagh introduce a new approach to this problem in [1] by embedding smaller, previously known decompositions into larger decompositions. They start by nding 5-cycle decompositions of subgraphs of K5;5;5, and then using this process to embed 6 K2r;2s;2t into KR;S;T where R > 2r, S > 2s, and T > 2t, by rst nding a decomposition of KR;S;TnE(K2r;2s;2t) into 5-cycles. Using the two following de nitions they give the subsequent theorem for this decomposition. De nition 1.2 [1] A triple fx;y;zg is said to be good if there exists a subgraph Gx;y;z of K5;5;5 and there exist subsets Xab, Xbc, Xca of Z5 with jXabj = x, jXbcj = y and jXcaj = z such that Gx;y;z contains only the edges of di erence d2Xab between Va and Vb, the edges of di erence d2Xbc between Vb and Vc, and the edges of di erence d2Xca between Vc and Va and there exists a decomposition of Gx;y;z into 5-cycles. De nition 1.3 [1] We say that a positive integer D is permissible with respect to r, s and t if there exist x1;x2;::: ;xD; y1;y2;::: ;yD and z1;z2;::: ;zD, each between 0 and 5 inclusive, with the following properties: for each 1 i D, the triple f5 x;5 y;5 zg is good; DX i=1 xi = ; DX i=1 yi = ; DX i=1 zi = . where = r +s t, = r s+t, and = r +s+t and a Theorem 1.3 [1] Let D be an odd integer that is permissible with respect to r;s and t. Let d = 5D, R = 2r + d, S = 2s + d, and T = 2t + d. Then there exists a decomposition of KR;S;T nK2r;2s;2t into 5-cycles. Billington and Cavenagh go on to give several lemmas describing some values of D that are permissible, one over-arching and two with speci c restrictions on r, s, and t. They conclude this paper by considering the case when R, S, and T have similar sizes, meaning 7 that R, S, and T are all odd with R 19 = t. Now we see how many of each type of 5-cycle we need. Using the system of linear equations described earlier we take the part sizes r = 7, s = 17, and t = 19 and we get that we need 104 5-cycles of Type 1, 9 5-cycles of Type 2, and 2 5-cycles of Type 3. We start by taking as many 5-cycles as we can, so we nd a 5-cycle that we can cycle through the edges of the graph by adding 1 to each vertex incident with edges of the 5-cycle to get the next 5-cycle. So, we begin by nding a 3-path between parts S and T that will cycle through all the edges of the graph between parts S and T and nd two further edges, one incident with one of the ends of this 3-path and the vertex (1;1) and the other edge incident with the other end of the 3-path and the vertex (1;1). In order to de ne as many 5-cycles as possible in this way, we start with the 3-path P = ((1;3);(1;2);(8;3);(13;2)), noting that the edge di erences here are 0, 7, and 14. The edge di erences here are important because the di erence between s and t is 2, so we pick di erences that alternate in parity, hence the even-odd-even arrangement. So, the rst 5-cycle is ((1;1);(1;3);(1;2);(8;3);(13;2)), the second 5-cycle will be ((2;1);(2;3);(2;2);(9;3);(14;2)). When an edge joining vertices 16 in parts S and T is cycled, the di erence of the resulting edge is unchanged unless the vertex (16;2) is cycled to the vertex (1;2), in which case the edge di erence will decrease by t s = 19 17 = 2. Note here that looking at the di erences 0, 7, and 14 it takes six full cycles for the di erence 0 to shift down to 7 (namely 0 to 17 to 15 to 13 to 11 to 9 to 7) , six full cycles for the di erence 7 to shift down to 14 (namely 7 to 5 to 3 to 1 to 18 to 16 to 14), and yet again six full cycles for the di erence 14 to shift down to 0 (namely 14 to 12 to 10 to 8 to 6 to 4 to 2 to 0). Thus we get 6 17 = 102 5-cycles of Type 1 this way. Note that 6 = t 3 , so this is precisely s t 3 . After we take these 5-cycles out of K7;17;19 we are left with the leave, L1, in Figure 2.3. Figure 2.3: Leave L1 17 Now, we know that we need 104 5-cycles of type 1, so we implement the new trade described earlier, performing it twice to get two more 5-cycles. For the rst implementation we pick the 5-cycle ((1;1), (1;3), (1;2), (8;3), (13;2)) and the edges f(1;3), (6;2)g, f(1;2), (15;3)g, f(15;3), (13;2)g, f(6;2), (1;1)g, f(1;1), (8;3)g, f(3;1), (8;3)g and f(3;1), (1;2)g, though in order to use the edgef(1;1), (8;3)gwe must take the 5-cycle ((1;1), (3;2), (15;3), (8;2), (8;3)) and replace it with the 5-cycle ((5;1), (3;2), (15;3), (8;2), (8;3)). With these edges we can get two 5-cycles instead of just the one 5-cycle that we started with; these 5- cycles are ((1;1), (6;2), (1;3), (1;2), (8;3)) and ((3;1), (1;2), (15;3), (13;2), (8;3)) leaving the edges f(1;1), (1;3)g and f(1;1), (13;2)g. For the second implementation we pick the 5-cycle ((2;1); (2;3), (2;2), (9;3), (14;2)) and the edges f(2;3), (7;2)g, f(2;2), (16;3)g, f(16;3), (14;2)g, f(7;2), (2;1)g, f(2;1), (9;3)g, f(4;1), (9;3)g and f(4;1), (2;2)g, though in order to use the edgef(2;1), (9;3)gwe must take the 5-cycle ((2;1), (4;2), (16;3), (9;2), (9;3)) and replace it with the 5-cycle ((6;1), (4;2), (16;3), (9;2), (9;3)). With these edges we can get two 5-cycles instead of just the one 5-cycle that we started with; these 5-cycles are ((2;1), (7;2), (2;3), (2;2), (9;3)) and ((4;1), (2;2), (16;3), (14;2), (9;3)) leaving the edges f(2;1), (2;3)g and f(2;1), (14;2)g. See Figure 2.4 and 2.5 for a picture of this trade. 18 Figure 2.4: First Implementation of this New Trade Figure 2.5: Second Implementation of this New Trade 19 After we implement these trades we have 104 5-cycles of Type 1 and a new leave, L2 (see Figure 2.6). Figure 2.6: Leave L2 20 From this leave we will nd as many of the other two types of 5-cycles as we can. We can get both of the 5-cycles of Type 3 that we need, these 5-cycles are ((1;1), (13;2), (5;1), (17;3), (3;2)), and ((2;1), (14;2), (6;1), (18;3), (4;2)), which we remove to get a new leave, L3 (see Figure 2.7). Figure 2.7: Type 3 5-cycles removed and Leave L3 21 Now we start looking for 5-cycles of Type 2, we can see that there are ve of these 5-cycles in this leave. These 5-cycles are ((5;1), (10;3), (7;1), (5;3), (10;2)), ((6;1), (11;3), (1;1), (6;3), (11;2)), (7;1), (12;3), (2;1), (7;3), (12;2)), ((3;1), (15;3), (5;1), (3;3), (8;2)), and ((4;1), (16;3), (6;1), (4;3), (9;2)), which we remove to get a new leave, L4 (see Figure 2.8). Figure 2.8: Type 2 5-cycles removed and Leave L4 22 This new leave has no 5-cycles that we can remove from the graph, so we need to start the process of swapping one 4-path from a 5-cycle we have already de ned for a 4-path in the leave of the graph to create a new 5-cycle in order to change the leave and look for an additional 5-cycle. We nd the 4-path ((4;1), (2;3), (2;1), (19;3), (17;2)) and see that we need the edge f(4;1), (17;2)g, so we need to nd the 5-cycle that contains this edge. The 5-cycle that contains f(4;1);(17;2)g is ((4;1), (1;3), (5;2), (8;3), (17;2)), so we now have the 5-cycle ((4;1), (2;3), (2;1), (19;3), (17;2)) (see Figure 2.9). Note that this new 5-cycle is a Type 2 5-cycle, of which we now need 3 more. Figure 2.9: First 4-path to be replaced along with the 5-cycle needed and Leave L5 23 We see that this leave has no 5-cycles that we can remove from the graph, so we make another swap. We nd the 4-path ((4;1), (1;3), (1;1), (18;3), (16;2)) and see that we need the edgef(4;1), (16;2)g, so we need to nd the 5-cycle that contains this edge. The 5-cycle that contains f(4;1), (16;2)g is ((4;1), (4;3), (4;2), (11;3), (16;2)), so we now have the 5-cycle ((4;1), (1;3), (1;1), (18;3), (16;2)) (see Figure 2.10). Note that this new 5-cycle is a Type 2 5-cycle, of which we now need 2 more. Figure 2.10: Second 4-path to be replaced along with the 5-cycle needed and Leave L6 24 We see that this leave has no 5-cycles that we can remove from the graph, so we make another swap. We nd the 4-path ((1;1), (13;3), (3;1), (1;3), (5;2)) and see that we need the edge f(1;1), (5;2)g, so we need to nd the 5-cycle that contains this edge. The 5-cycle that containsf(1;1), (5;2)gis ((1;1), (2;3), (10;2), (9;3), (5;2)), so we now have the 5-cycle ((1;1), (13;3), (3;1), (1;3), (5;2)) (see Figure 2.11). Note that this new 5-cycle is a Type 2 5-cycle, of which we now need 1 more. Figure 2.11: Third 4-path to be replaced along with the 5-cycle needed and Leave L7 25 We see that this leave has no 5-cycles that we can remove from the graph, so we make another swap. We nd the 4-path ((4;1), (14;3), (2;1), (17;2), (8;3)) and see that we need the edge f(4;1), (8;3)g, so we need to nd the 5-cycle that contains this edge. The 5-cycle that contains f(4;1), (8;3)g is ((4;1), (8;3), (12;2), (15;3), (7;2)), so we now have the 5- cycle ((4;1), (14;3), (2;1), (17;2), (8;3)) (see Figure 2.12). Note that this new 5-cycle is a Type 2 5-cycle, of which we now have all 9 needed. Figure 2.12: Fourth 4-path to be replaced along with the 5-cycle needed the Leave L8 26 We see that this leave has no 5-cycles that we can remove from the graph, so we make another swap. We nd the 4-path ((7;2), (4;1), (4;3), (4;2), (11;3)) and see that we need the edgef(7;2), (11;3)g, so we need to nd the 5-cycle that contains this edge. The 5-cycle that contains f(7;2), (11;3)g is ((7;2), (11;3), (12;2), (4;3), (3;1)), so we now have the 5-cycle ((7;2), (4;1), (4;3), (4;2), (11;3)) (see Figure 2.13). Figure 2.13: Fifth 4-path to be replaced along with the 5-cycle needed and Leave L9 27 We see that this leave does have a 5-cycle that we can remove from the graph, this 5-cycle is ((3;1), (4;3), (12;2), (15;3), (7;2)) leaving 15 edges in the leave, L10 (see Figure 2.14). Figure 2.14: 5-cycle removed and Leave L10 28 We see that this leave has no 5-cycles that we can remove from the graph, so we make another swap. We nd the 4-path ((10;2), (2;3), (1;1), (16;2), (11;3)) and see that we need the edgef(10;2), (11;3)g, so we need to nd the 5-cycle that contains this edge. The 5-cycle that contains f(10;2), (11;3)g is ((10;2), (11;3), (5;2), (5;1), (4;3)), so we now have the 5-cycle ((10;2), (2;3), (1;1), (16;2), (11;3)) (see Figure 2.15). Figure 2.15: Fifth 4-path to be replaced along with the 5-cycle needed and Leave L11 29 We see that this leave does have a 5-cycle that we can remove from the graph, this 5-cycle is ((5;1), (5;2), (9;3), (10;2), (4;3)) leaving 10 edges in the leave, L12 (see Figure 2.16). Figure 2.16: 5-cycle removed and Leave L12 30 We see that this leave has no 5-cycles that we can remove from the graph, so we make another swap. We nd the 4-path ((7;1), (5;2), (8;3), (12;2), (11;3)) and see that we need the edgef(7;1), (11;3)g, so we need to nd the 5-cycle that contains this edge. The 5-cycle that contains f(7;1), (11;3)g is ((7;1), (11;3), (15;2), (18;3), (10;2)), so we now have the 5-cycle ((7;1), (5;2), (8;3), (12;2), (11;3)) (see Figure 2.17). Figure 2.17: Sixth 4-path to be replaced along with the 5-cycle needed and Leave L13 31 From the 10 edges in this leave we actually have both of the 5-cycles that we need, which is to be expected. If we had only one 5-cycle the leave would only have 5 edges and supposedly no 5-cycles, which is impossible since this would imply that at least one vertex had degree 1 which can not be the case since each vertex in the graph started with even degree and whenever a 5-cycle is removed from the graph the degree of each vertex incident with an edge in the 5-cycle decreased by precisely 2. These 5-cycles are ((7;1), (19;3), (5;2), (11;3), (15;2)) and ((7;1), (10;2), (18;3), (15;2), (17;3)) (see Figure 2.18). Figure 2.18: Final two 5-cycles 32 This process of swapping one 5-cycle for another in order to create a new leave represents a trade in which we take seven 5-cycles and twenty edges and decompose the graph induced by these edges into 5-cycles. We take the 5-cycles ((4;1), (1;3), (5;2), (8;3), (17;2)); ((4;1), (4;3), (4;2), (11;3), (16;2)); ((1;1), (2;3), (10;2), (9;3), (5;2)); ((4;1), (8;3), (12;2), (15;3), (7;2)); ((7;2), (11;3), (12;2), (4;3), (3;1)); ((10;2), (11;3), (5;2), (5;1), (4;3)); and ((7;1), (11;3), (15;2), (18;3), (10;2)) along with the edges f(1;1), (1;3)g; f(1;1), (17;3)g; f(1;1), (18;3)g; f(1;1), (16;2)g; f(3;1), (1;3)g; f(3;1), (17;3)g; f(16;2), (18;3)g; f(2;1), (2;3)g; f(2;1), (14;3)g; f(2;1), (19;3)g; f(2;1), (17;2)g; f(4;1), (2;3)g; f(4;1), (14;3)g; f(7;1), (5;2)g; f(7;1), (15;2)g; f(7;1), (17;3)g; f(7;1), (19;3)g; f(5;2), (19;3)g; f(15;2), (17;3)g; andf(17;2), (19;3)gto get the following eleven 5-cycles ((4;1), (2;3), (2;1), (19;3), (17;2)); ((4;1), (1;3), (1;1), (18;3), (16;2)); ((1;1), (13;3), (3;1), (1;3), (5;2)); ((4;1), (14;3), (2;1), (17;2), (8;3)); ((7;2), (4;1), (4;3), (4;2), (11;3)); ((3;1), (4;3), (12;2), (15;3), (7;2)); ((10;2), (2;3), (1;1), (16;2), (11;3)); ((5;1), (5;2), (9;3), (10;2), (4;3)); ((7;1), (5;2), (8;3), (12;2), (11;3)); ((7;1), (19;3), (5;2), (11;3), (15;2)); and ((7;1), (10;2), (18;3), (15;2), (17;3)). This uses all of the edges from the leave of the graph of K7;17;19, thus we have a decom- position of K7;17;19 into 5-cycles. 33 Chapter 3 Final Comments Several of the cases that remain to be solved are complete tripartite graphs where the part sizes are relatively prime to each other. It is my belief that the process detailed in the previous chapter will de ne 5-cycle decompositions for any Complete Tripartite graph G = Kr;s;t where r, s, and t are relatively prime to each other. Thus I make the following conjecture, which is made inconsequential if Mahmoodian?s original conjecture is proved: Conjecture 3.1 Let Kr;s;t be a complete tripartite graph with part sizes r < s < t. If r, s, and t are pairwise relatively prime and the necessary conditions are satis ed, then Kr;s;t admits a 5-cycle decomposition. 34 Bibliography [1] Billington, E.J. and Cavenagh, N.J.: Decomposing complete tripartite graphs into 5- cycles when the partite sets have similar size. Aequationes Math. 82, 277-289 (2011) [2] Cavenagh, N.J. and Billington, E.J.: On decomposing complete tripartite graphs into 5-cycles. Australas. J. Combin. 22, 41-62 (2000) [3] Cavenagh, N.J.: Further decompositions of complete tripartite graphs into 5-cycles. Discrete Math. 256, 55-81 (2002) [4] Mahmoodian, E.S and Mirzakhani, M: Decomposition of complete tripartite graphs into 5-cycles, Combinatorics advances (Tehran, 1994), vol. 329 of Math. Appl., pp. 235-241. KluwerAcad. Publ., Dordrect, 1995 [5] Mahmoodian, E.S., Alipour, S and Mollaahmadi, E.: On decomposing complete tripar- tite graphs into 5-cycles, Australas. J. Combin. 54, 289-301 (2012) [6] Sotteau, D.: Decomposition of K(m;n) into cycles (circuits) of length 2k. J. of Combi- natorial Theory B 30, 75-81, 1981 35 Appendices Figure 1: Covered latin representation of K7;17;19 by trades 36 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 1 2 3 4 5 6 7 1 2 3 4 5 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 6 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 A B C D E F G H I J K L M N OP F F G G Figure 2: List of 5-cycles to which edges between R and S belong in Kr;s;t 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 1 2 3 4 5 6 7 18 19 1 2 3 4 5 6 6 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 41 41 42 43 44 45 46 47 48 48 48 49 50 51 52 53 54 55 56 57 58 5960 81 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 8080 61 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 A B C D E F G H I H H I I J J J K K K L L L M N OP Figure 3: List of 5-cycles to which edges between R and T belong in Kr;s;t 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 1 2 3 4 5 6 7 18 19 8 9 10 11 12 13 14 15 16 17 1 1 1 3 3 3 2 4 2 4 2 4 5 55 6 7 7 7 8 88 9 99 10 1010 11 11 11 12 12 12 13 1313 14 1414 15 15 15 16 16 16 17 17 17 18 18 18 1919 19 20 20 20 21 21 21 22 2222 23 23 23 24 2424 25 2525 26 26 26 27 2727 28 2828 29 2929 30 3030 31 3131 32 3232 33 3333 34 34 34 35 35 35 36 36 36 37 37 37 38 38 38 39 39 39 40 40 40 41 42 4242 43 4343 44 44 44 45 4545 46 4646 47 4747 48 49 4949 5050 50 51 51 51 52 5252 53 5353 54 54 54 55 55 55 56 56 56 57 57 57 58 58 58 59 59 59 60 6060 61 61 61 62 6262 63 6363 64 6464 65 6565 66 6666 67 6767 68 6868 69 69 69 70 7070 71 7171 72 72 72 73 73 73 74 74 74 7575 75 76 76 76 77 77 77 78 7878 79 7979 80 81 8181 82 8282 83 8383 84 84 84 85 8585 86 8686 87 8787 88 8888 89 8989 90 9090 91 91 91 92 92 92 93 93 93 94 94 94 95 95 95 96 96 96 97 97 97 98 9898 99 9999 A AA B BB C CC D DD E EE F G H I J K L O O O P PP N NN M M M Figure 4: List of 5-cycles to which edges between S and T belong in Kr;s;t 37