k-star Decompositions of Lambda-fold Complete Multipartite Graphs Except where reference is made to the work of others, the work described in this dissertation is my own or was done in collaboration with my advisory committee. This dissertation does not include proprietary or classifled information. Matthew Paul Anzur Certiflcate of Approval: C.C. Lindner Distinguished University Professor Mathematics and Statistics Dean Hofiman, Chair Professor Mathematics and Statistics Douglas Leonard Professor Mathematics and Statistics Kevin Phelps Professor Mathematics and Statistics Chris Rodger Professor Mathematics and Statistics Michael Bozack Professor Physics Joe F. Pittman Interim Dean Graduate School k-star Decompositions of Lambda-fold Complete Multipartite Graphs Matthew Paul Anzur A Dissertation Submitted to the Graduate Faculty of Auburn University in Partial Fulflllment of the Requirements for the Degree of Doctor of Philosophy Auburn, Alabama August 4, 2007 k-star Decompositions of Lambda-fold Complete Multipartite Graphs Matthew Paul Anzur Permission is granted to Auburn University to make copies of this dissertation at its discretion, upon the request of individuals or institutions and at their expense. The author reserves all publication rights. Signature of Author Date of Graduation iii Vita Matthew Paul Anzur was born October 17, 1975 in Pittsburgh, Pennsylvania. He is the son of Frank Anzur and Marcia (Przywara) Anzur. He graduated from Jacksonville High School in Jacksonville, Alabama in 1994. He entered Auburn University in August of 1994 and graduated cum laude in December of 1998 with a Bachelor of Science degree in Mathematics. He entered Graduate School, Auburn University in January of 1999. He worked as a Graduate Teaching Assistant through his time in Graduate School. iv Dissertation Abstract k-star Decompositions of Lambda-fold Complete Multipartite Graphs Matthew Paul Anzur Doctor of Philosophy, August 4, 2007 (B.S., Auburn University, 1998) 57 Typed Pages Directed by Dean Hofiman We examine the problem of k-star decompositions on ?-fold complete multipartite graphs. After a brief examination of the computational complexity issues involved, we present complete proofs for necessary and su?cient conditions in the case where k = 2 and the case where ? = 2 and k = 3. We then show some partial results for k = 3 and higher values of ? along with some helpful tools, including some necessary conditions, which may help in solving further cases. v Acknowledgments The author wishes to thank the members of his advisory committee, especially Pro- fessor Dean Hofiman, for their helpful comments and suggestions. He also wishes to thank Professors Darrell Hankerson and Edward Slaminka for creating and maintaining the style flles and templates used in the preparation of this dissertation. Finally, he thanks his family for all of their support. vi Style manual or journal used Journal of Approximation Theory (together with the style known as \aums"). Bibliography follows van Leunen?s A Handbook for Scholars. Computer software used The document preparation package TEX (speciflcally LATEX) together with the departmental style-flle aums.sty and text editor WinEdt. Figures were prepared in Mathematica or CorelDraw. vii Table of Contents List of Figures ix 1 Introduction 1 1.1 Deflnitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.2 A Small Example . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 1.3 Previous Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 1.4 k = 2 and Complexity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 2 Our General Approach for ? ? 2 and k ? 3 7 2.1 Central Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 2.1.1 The Greedy Central Function . . . . . . . . . . . . . . . . . . . . . . 8 2.2 Some General Results and Lemmas . . . . . . . . . . . . . . . . . . . . . . . 9 2.2.1 Some Necessary Conditions . . . . . . . . . . . . . . . . . . . . . . . 10 2.3 The Subsets and The Inequalities . . . . . . . . . . . . . . . . . . . . . . . . 13 2.3.1 The Inequalities . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 3 k = 3;? = 2 18 4 Partial Results for k = 3, ? > 2 30 5 Conclusion 37 Bibliography 39 Appendix 40 viii List of Figures 1.1 An S3-decomposition of 2K4. . . . . . . . . . . . . . . . . . . . . . . . . . . 2 1.2 S2-decomposition when N(u) = 2j. . . . . . . . . . . . . . . . . . . . . . . . 4 1.3 S2-decomposition when N(u) = 2j +1 and ? = 2. . . . . . . . . . . . . . . . 5 3.1 An S3-decomposition of 2K3;5. . . . . . . . . . . . . . . . . . . . . . . . . . 24 3.2 An S3-decomposition of 2K1;1;4. . . . . . . . . . . . . . . . . . . . . . . . . . 28 ix Chapter 1 Introduction An H-decomposition (or H-design) of a graph G is a set of subgraphs of G, called blocks, with the properties that each block is isomorphic to H and every edge in G is in exactly one block. A Steiner Triple System, for example, is a K3-decomposition of Kn. We will be examining the problem of k-star decompositions of ?-fold complete multipartite graphs. First, some deflnitions. 1.1 Deflnitions For most deflnitions we will use terms as deflned in [1]. We will use the notation G = (V(G);E(G)) where V(G) is the set of vertices of G and E(G) is the set of edges of G. A ?-fold complete multipartite graph is a graph in which the vertices are partitioned into p partite sets (or parts) A1;:::;Ap with the property that each pair of vertices have either ? edges between them (if they are in difierent parts) or zero edges between them (if they are in the same part). We will use the notation ?Ka1;:::;ap where ai = jAij to indicate a ?-fold complete multipartite graph. We will also put the parts in increasing order of size so a1 ? a2 ? ::: ? ap. Then, let n = Ppi=1 ai be the total number of vertices in the graph, m = Pp?1i=1 Ppj=2 aiaj the number of edges in the underlying simple graph, and e(G) = ?m the total number of edges of G. We will also use the notation ?(xy) to indicate the number of edges between vertices x and y and for A;B V(G) let e(AB) be the number of edges with one end in A and the other in B. Finally, for S V(G), let mS be the number of edges in the underlying induced simple subgraph on S. 1 1 4 2 3 1 2 3 4 4 1 2 3 2 1 3 4 3 1 2 4 Figure 1.1: An S3-decomposition of 2K4. A k-star (also known as a k-claw) is a simple (? = 1) complete multipartite graph with one part of size one and one of size k, that is, K1;k. We will call the part of size 1 adjacent to the other k vertices the center of the star and the other k vertices the ends of the star. 1.2 A Small Example For a small example, let us consider the graph 2K4. We will label the vertices as V(G) = f1;2;3;4g. By simply centering one 3-star at each vertex of 2K4 and carefully selecting the ends, we get the S3-design on 2K4 shown in Figure 1.1. 1.3 Previous Results A ?-fold complete graph ?Kn is a complete multipartite graph with n parts of size one and each pair of vertices has ? edges between them. In [2] Tarsi proved that the following conditions are necessary and su?cient for ?Kn to have an Sk-decomposition: 2 Theorem 1.1 (Tarsi). ?Kn has an Sk-decomposition if and only if 1. ?n(n?1) ? 0 mod 2k 2. a. n ? 2k if ? = 1 b. n ? k +1 if ? is even c. n ? k +1+ k? if ? is odd In [3] Tazawa proved that the following conditions are necessary and su?cient for Ka1;:::;ap to have an Sk-decomposition: Theorem 1.2 (Tazawa). Ka1;:::;ap has an Sk-decomposition if and only if 1. kjm 2. k(n?ap) ? m if k ? n?ap 3. mk flfl(n?ap) if n?ap < k With these results in mind, we will assume that G is neither simple nor Kn; that is, ? ? 2 and ap ? 2. 1.4 k = 2 and Complexity In [4], Priesler and Tarsi proved that Sk-decomposition can be done in polynomial time if k = 2 and it is NP-complete for multigraphs of any multiplicity ? and k ? 3. Decomposing graphs into copies of S2 is equivalent to flnding a perfect matching in the ?-line graph of G, L?(G). L?(G) consists of a vertex for each edge of G and two vertices are adjacent in L?(G) if and only if they form a path of length 2 in G. Edmonds proved in [5] that a 3 u v1 v2 v3 v4 vl-1 vl ? c108 Figure 1.2: S2-decomposition when N(u) = 2j. perfect matching could be found in polynomial time. Priesler and Tarsi give a method that is easier to check in [4] for determining whether a graph admits an S2-decomposition, but for ?Ka1;:::;ap one must only check that 2je(G), n ? 3, and p ? 2. Theorem 1.3. G = ?Ka1;:::;ap has an S2-decomposition if and only if 2je(G), n ? 3, and p ? 2. Proof. Necessity is clear. For su?ciency, suppose flrst that ? is even; in this case, we will use induction. Start with a vertex u 2 A1. Let fv1;:::;vtg = N(u), the vertices adjacent to u. If t = 2j we may center j copies of S2 with ends fv1;v2g;fv3;v4g;:::;fvt?1;vtg and repeat this ? times. Figure 1.2 shows an example. Ift = 2j+1, wemayflrstcenter?j starsatuwithendsfv1;v2g;fv3;v4g;:::;fvt?2;vt?1g. Then reorient one copy of S2 with ends fvi;vi+1g to have its ends as fvi;vtg. Finally, add ? 2 more stars centered at u with ends fvi+1;vtg. All edges incident to u have now been covered. Repeat the same assignment in all other vertices in A1. If there are still uncovered 4 v1 vi vi+1u vl v1 vi vi+1u vl v1 vi vi+1u vl Figure 1.3: S2-decomposition when N(u) = 2j +1 and ? = 2. edges remaining, move on to the next-indexed part and repeat the above steps until no uncovered edges remain. An example is shown in Figure 1.3. If ? is odd, then we need 2jm. But then this (and ap ? 2 as previously assumed) is all that is needed to satisfy Tazawa?s three conditions in [3] for an S2-decomposition in the underlying simple graph. Thus we need only take an S2-decomposition on the underlying simple graph and make ? copies of it. Not surprisingly, it is rather easy to determine whether an S2-decomposition exists for ?Ka1;:::;ap and then construct it. In the chapters that follow, however, we take on values of k ? 3; again, not surprisingly, things get much more complicated as [4] has shown that the general problem is NP-complete. For 2Ka1;:::;ap and k = 3, we have necessary and su?cient conditions that may be quickly checked, and present this in Chapter 3. In Chapter 2 we will start by gathering some information and tools for narrowing the search down a bit as well as some necessary (but not always su?cient) conditions. We 5 will then examine the case where ? = 2 and present necessary and su?cient conditions for 2Ka1;:::;ap to have an S3-decomposition. The case where ? ? 3 and k = 3, presented in Chapter 4 is unfortunately incomplete at this time. There are a few subcases where greater values of ? pull the inequalities we will be using a little too much and we cannot, at this time, draw any conclusions. We will, however, present the subcases that we have completed in Chapter 4. 6 Chapter 2 Our General Approach for ? ? 2 and k ? 3 Now we will begin putting together some helpful tools to help us in the search for graphs with Sk-decompositions. We will start with an important theorem giving us a place to start looking. We then present some small Lemmas useful in many of the cases to follow and necessary conditions for ?Ka1;:::;ap to have an Sk-decomposition. Finally we construct a set of inequalities that will be our main tool in proving the su?ciency of these conditions. 2.1 Central Functions We will deflne a central function on the vertices of a graph G as c : V(G) !N where N is the set of nonnegative integers and c(x) is the number of blocks of the Sk-decomposition whose center is x. In [6] Hofiman proved that the following conditions are necessary and su?cient for any graph to have an Sk-decomposition with a given function c: Theorem 2.1 (Hofiman). G has an Sk-decomposition with central function c if and only if: 1. k X x2V(G) c(x) = e(G) 2. ?(xy) ?c(x)+c(y) for all x;y 2?V(G)2 ?, where ?V(G)2 ? is the set of all pairs of vertices in G 3. e(S)+ X x2S y=2S minfc(x);?(xy)g? kc(S) for all S V(G) 7 We will use this theorem as the basis for flnding necessary conditions speciflc to ?Ka1;:::;ap. 2.1.1 The Greedy Central Function In most of the cases we will examine, we shall use a greedy central function to attempt to center copies of Sk in G. Let Ci, the capacity of the part Ai, be the maximum number of blocks of an Sk-decomposition we may center at a vertex in Ai. If n ? ai ? k, then Ci = j?(n?a i) k k ; if n ? ai < k then Ci = 0. We will say that a part Ai is at capacity if c(t) = Ci for all t 2 Ai. We will run the greedy central function algorithm as follows: Initialization: Let i = 1, c(t) = 0 for all t 2 V(G), and r = e(G)=k. 1. If Ai is not already at capacity: a. If r ? ai increase c(t) by one at each vertex t 2 Ai and decrease r by ai. If i = p, set i = 1 and repeat Step 1. If i < p, increase i by one and repeat Step 1. b. If 0 < r < ai, let t1;:::;tai be the vertices in Ai. Increase c(x) by one on vertices t1;:::;tr and stop. c. If r = 0, stop. 2. If Ai is at capacity, set i = 1 and go back to Step 1. As the greedy central function respects the capacities of each part and does not move up to a higher value until the all vertices not already at capacity have been increased, there will be at most one part Afl with c(t) = c(u) + 1 for some vertices t and u in Afl. We will call Afl the split part. In every other part, c is constant; for simplicity, we will let qi be the 8 least value of c(x) for x 2 Ai, Ti S be the vertices x in non-split parts with c(x) = i, and ti = jTij. As we will see in Chapters 3 and 4, in most cases where k = 3 this greedy central function will yield an S3-decomposition of ?Ka1;:::;ap. There are a few exceptions when ? = 2, but we have backup central functions that work. There are, however, possibly several cases when ? ? 3 where this function will not yield an S3-decomposition. 2.2 Some General Results and Lemmas We have a few more or less straightforward (but helpful) lemmas to aid us in the cases ahead. This result for graphs where the greedy central function stops on a split part is trivial, but as we refer to it in several cases that follow, we present it as a lemma. Lemma 2.1. If the greedy central function c terminates in Afl and Afl is a split part, then max x2V(G) fc(x)g = qfl +1. If Afl is not split, then max x2V(G) fc(x)g = qfl. Proof. As c respects the capacities of each part, the central function algorithm will only go back to A1 (and thus increase the maximum value of c) when it has added one to the value of c in all of the vertices in parts that are not already at capacity. Thus, if the algorithm ends in a part Afl, then the central function value in all parts Ai where i < fl must be the same, namely, the greatest value of c(x) for x 2 Afl. This is qfl + 1 if Afl is split, and qfl if it is not. As the central function is decreasing as the indices increase, this is the maximum value of c. The following is simply a straightforward counting of edges in a subset S V(G), but again, it is used in many cases ahead so we present it as a lemma. 9 Lemma 2.2. If S V(G) consists of p parts of size at least t, then mS ? p?1p st, where s = jSj. Proof. If S consists of p parts of size at least t, then s pt ? pt p ? t = t2 So then mS ? t(s?t) = st?t2 ? st? stp = p?1 p ? 2.2.1 Some Necessary Conditions Here we present two necessary conditions for a graph to have an Sk-decomposition. In the case where ? = 2 and k = 3, as we will see in Chapter 3 these are also su?cient. For k = 3 and higher values of ?, we will need another condition which we present in Chapter 4. Theorem 2.2. If G = ?Ka1;:::;ap has an Sk-decomposition, then 1. kje(G) 2. a. k(n?ap) ? m if 2ap ? n b. n+ "?(n?2ap) ? 2mk where " = ? mod 2 if 2ap ? n. Proof. The necessity of Condition 1 is obvious; we cannot have any leftover edges. Now we examine each case of Condition 2. 10 Case 1 (2ap ? n) Condition 2a. is equivalent to ?mk ? ?(n?ap). Suppose then, that ?m k < ?(n?ap) ? ?n 2 . There must be, then, a vertex x in some part Ai with q = c(x) < ? 2. Hofiman?s Condition 2 in Theorem 2.1 must hold here; thus every other vertex y in GnAi must have c(y) ? ??q. But then ?(n?ap) > ?mk ? (??q)n?(??q)ai +qai = (??q)n?(??2q)ai ? (??q)n?(??2q)ap = ?(n?ap)+q(2ap ?n) But here 2ap ? n, so the above inequality cannot hold. Case 2 (2ap ? n) We will examine subcases by whether ? is even or odd. Case 2.1 (? is even) Here Condition 2b. is equivalent to ?mk ? ?n2 . Suppose, then, that ?m k < ?n 2 . There must be, then, a vertex x in some part Ai with q = c(x) < ? 2. Again by Hofiman?s Condition 2 in Theorem 2.1 we need that for every other vertex y in GnAi that 11 c(y) ? ??q. But then we need ?n 2 > ?m k ? (??q)(n?ai)+qai = (??q)n?(??2q)ai ? (??q)n?(??2q)ap = (??q)(n?ap)+qap = ??q ? ?2 ? (n?ap)+ ?2(n?ap)+qap = ?n2 + ? 2 ?q ? (n?2ap) But with q < ?2 and n ? 2ap, the above inequality cannot hold. Case 2.2 (? is odd) Here Condition 2b. is equivalent to ?mk ? ?+12 n?ap. Suppose, then, that ?mk < ?+12 n?ap. There must be, then, a vertex x in some part Ai with q = c(x) ? ??12 . Once again by Hofiman?s Condition 2 in Theorem 2.1 we need that for every other vertex y in GnAi that c(y) ? ??q. We have, then, that ?+1 2 n?ap > ?m k ? (??q)(n?ai)+qai = (??q)n?(??2q)ai ? (??q)n?(??2q)ap = (??q)(n?ap)+qap = ??q ? ?+12 ? (n?ap)+ ?+12 (n?ap)+qap = ?+12 n?ap + ??1 2 ?q ? (n?2ap) 12 But with q ? ??12 and n ? 2ap, the above inequality cannot hold. 2.3 The Subsets and The Inequalities In most cases of the proofs for su?ciency of these conditions, we will show that the greedy central function meets Hofiman?s Condition 3 in Theorem 2.1. Checking every possible subset of V(G), however, is a daunting task; we want to narrow down the subsets S V(G) that we need to examine. From this point forward, we will let S V(G) be a largest subset that minimizes f(S) = e(S)?3c(S)+ X x2S y=2S minfc(x);?(xy)g (2.1) The following lemma shows that, in each part, all of the vertices with the same value of c are all either in S or none of them are. Thus, if the central function is constant across each part (and the only one where it may not be is the part where the algorithm stops), then we may select S part-by-part instead of vertex-by-vertex. If a part Ai is split, either all of the vertices are in S, none of them are, only those with c(x) = qi are, or only those with c(x) = qi +1 are. Lemma 2.3. Let x and y be two vertices in a part Ai such that c(x) = c(y). Then x 2 S if and only if y 2 S. 13 Proof. Let q = c(x) = c(y). Assume without loss of generality that x 2 S and y =2 S. Removing x from S increases f by ??(n?ai)+kq ? X t=2S minfq;?(xt)g+ X t2S minfc(t);?(xt)g? 0 However, all terms in the above sums of minimums corresponding to vertices in Ai other than x are zero, as there are no edges between them. We may ignore those terms. So the above inequality becomes ??(n?ai)+kq ? X t=2S[Ai minfq;?g+ X t2S t=2Ai minfc(t);?g? 0 (2.2) Adding y to S increases f by ?(n?ai)?kq + X t=2S minfq;?(yt)g? X t2S minfc(t);?(yt)g > 0 As above, we can ignore all terms in the sums corresponding to vertices in Ai other than y. The above inequality becomes ?(n?ai)?kq + X t=2S[Ai minfq;?g? X t2S t=2Ai minfc(t);?g > 0 (2.3) Adding the corresponding left and right sides of 2.2 and 2.3 above gives 0 > 0, obviously a contradiction. With this lemma in mind, we will deflne the following subsets of indices of the p parts. Let I = f1;2;:::;pg be the indices of the parts, Bi = fx 2 Aijc(x) = qig be the vertices in 14 a part with the least value of the central function, and bi = jBij. Then let U = fi 2 IjBi = Aig U = fi 2 Ijbi < aig V = fi 2 UjAi \S =?g W = fi 2 UjAi Sg X = 'i 2 UjAi \S =?? Y = 'i 2 UjAi \S = Bi? Y0 = 'i 2 UjAi \S = AinBi? Z = 'i 2 UjAi S? Now instead of picking subsets vertex-by-vertex, we may select them part-by-part (or one of the "halves" of the part if it is split). We still have a lot of work to do, and there are still many possible subsets, but this greatly simplifles things. 2.3.1 The Inequalities Now we may put together the primary means of proving the cases to come. The following inequalities result from giving a largest set minimizing S a small nudge; that is, we will either add one part to S that was not in there before or remove one part from S and examine the change in f. As we are assuming that S is a largest set that minimizes f, adding any vertices to S will always increase f; removing vertices may or may not increase f but will not decrease it. 15 For all v 2 V, adding Av to S gives ?sav ?kqvav +(n?s?av) X t2Av minfqv;?g?av X t2S minfc(t);?g > 0 (2.4) For all w 2 W, removing Aw from S gives ??(s?aw)aw +kqwaw ?(n?s) X t2Aw minfqv;?g+aw X t2SnAw minfc(t);?g? 0 (2.5) For all x 2 X, adding Bx to S gives ?sbx ?kqxbx +(n?s?ax) X t2Bfi minfqx;?g?bx X t2S minfc(t);?g > 0 (2.6) Adding AxnBx to S gives ?s(ax?bx)?k(qx+1)(ax?bx)+(n?s?ax) X t2AxnBx minfqx;?g?(ax?bx) X t2S minfc(t);?g > 0 (2.7) For all y 2 Y, adding By to S gives ?sby ?kqyby +(n?s?by) X t2By minfqy;?g?by X t2Sn(AynBy) minfc(t);?g > 0 (2.8) Removing Ay nBy from S gives ??(s?(ay ?by))(ay ?by)+k(qy +1)(ay ?by)? (n?s?by) X t2AynBy minfqx;?g+(ay ?by) X t2Sn(AynBy) minfc(t);?g? 0 (2.9) 16 For all y 2 Y0, removing By from S gives ??(s?by)by +kqyby ?(n?s?(ay ?by)) X t2By minfqy;?g+by X t2SnBy minfc(t);?g? 0 (2.10) Adding Ay nBy to S gives ?s(ay ?by)?k(qy +1)(ay ?by)+ (n?s?(ay ?by)) X t2AynBy minfqy;?g?(ay ?by) X t2SnBy minfc(t);?g > 0 (2.11) For all z 2 Z, removing Bz from S gives ??(s?az)bz +kqzbz ?(n?s) X t2Bx minfqz;?g+bx X t2SnAz minfc(t);?g? 0 (2.12) Removing Az nBz from S gives ??(s?(az ?bz))(az ?bz)+k(qz +1)(az ?bz)? (n?s) X t2AznBz minfqz;?g+(az ?bz) X t2Sn(AznBz) minfc(t);?g? 0 (2.13) As awful as some of these inequalities look, they are very valuable tools in examining su?ciency in the cases to come. We will generally divide these cases by the value of minfqi;?g, greatly simplifying the work ahead. In fact, if minfqi;?g = ? we usually only have two terms in each inequality to deal with. Now, we will put them to use in the case where k = 3 and ? = 2. 17 Chapter 3 k = 3;? = 2 Here we present our result on S3-decompositions of 2-fold complete multipartite graphs. We will show that conditions given in Theorem 2.2 are necessary and su?cient. Theorem 3.1. Let G = 2Ka1;:::ap. G has an S3-decomposition if and only if: 1. 3jm 2. a. If 2ap ? n then 3n ? 2m b. If 2ap ? n then 3(n?ap) ? m Proof. The necessity of these conditions was proved in Theorem 2.2. For su?ciency, we will examine four main cases. In the flrst three we will assume that the capacities of each part are positive and then examine cases according to the values c takes, speciflcally, when c(x) is at most 2 or at least 2 for all x 2 V(G). For the last case, we will examine graphs where the capacity of Ap is zero. We will let S V(G) be a largest subset that minimizes f(S) = e(S)?3c(S)+ X x2S y=2S minfc(x);?(xy)g Note that f(V(G)) = f(?) = 0; we will assume that S is neither. We then use the inequalities and subsets from Section 2.3 to flnd all of the possible subsets S that minimize f(S). In each of these cases, our goal will either be to show that even if that set minimizes 18 S, f(S) ? 0, or, that S cannot minimize f due to some contradiction. We begin with the case where all vertices receive exactly one star from the greedy central function. Case 1 (qi = 1 for all i): We may assume that V 6= ? 6= W, or else we would have S = G or S = ?. From 2.4 and 2.5 we get aw > av. Here f(S) = e(S)?s(3?(n?s)); with aw ? 2 by Lemma 2.2, e(S) = 2m ? 2s, so f(S) ? 0. Case 2 (1 ? qi ? 2, qi = 1 for some i 2 I, qj = 2 for some j 2 I) Case 2.1 (V 6=?6= W): From 2.4 and 2.5 we have [3?(n?s)](qw ?qv)+(2?qw)aw ?avqv ?1 ? 0 (3.1) so we cannot have qv = qw = 2 for any v 2 V or w 2 W; in other words, the partite sets with qi = 2 are all either in V or W. Case 2.1.1 (fijqi = 2g W) Here qv = 1 for all v 2 V. Then the inequality in 3.1 becomes [3?(n?s)] ? av +1 so we must have av = n?s = 1 and thus U =?; the central function must be constant across each part. Thus S consists of all of the vertices in G except for a part Afl of size 1 with afl = 1. So then f(S) = e(S)?2c(S) = 3c(G)?2(n?1)?2[c(G)?1] = c(G)?2n+4 = 2n?1?s1 ?2n+4 = 3?s1 We will then assume that s1 > 3 and eliminate this case by contradiction. 19 With G 6= 2Kn, there must be a w 2 W such that aw ? 2 and qw = 1. Here, then, Tj = Si2W qi=j Ai and tj = jTjj. Let Awo be a smallest part in T1. Removing Aw0 from S we get from 2.5 ?2(n?1?aw0)+2+(c(S)?aw0) ? 0 and by our assumptions in this case, c(S) = 2n?2?s1 so the above inequality becomes s1 ?aw0 ? 2; removing Aw1 would leave at most 2 vertices in T1. And, by the inequality in 3.1 above, awo > av = 1. With c(G) = 2n?1?s1, m = 3n? 32 (s1 +1) so s1 must be odd. But then if removing the least-sized part in T1 leaves at most two vertices in T1 and Ap T1 has size at least 2, we must have T1 = Ap and so G consists of p?1 parts of size 1 and Ap. We will now count edges to arrive at the promised contradiction. We must have here that e(G) = 6n?3ap ?3 = 2 n?a p 2 ? +2ap(n?ap) = (n?ap)(n?ap ?1)+2ap(n?ap) = n2 ?n+ap ?a2p This is a little easier to prove if we substitute n = t2 + 1 + ap. With a little shu?ing of terms, the above equation becomes ap +3 = t2(t2 ?5)+2apt2 ??6+4ap But this is only true when ap ? 3, contradicting our assumption here that s1 > 3. Case 2.1.2 (fijqi = 2g V) 20 Case 2.1.2.1 (U = ?) Here c(S) = s and f(S) = e(S)?[3?(n?s)]s. By 3.1, for aw1 2 W and v2 2 V with qv2 = 2, we have aw1 ? [3?(n?s)]+2av +1 S must consist of at least two parts, as the greedy central function respects the capacities of each part, all parts have capacity of at least 1, and qi ? 1 for all i by assumption. Let Aw0 be a smallest part in T1. By the above inequality, aw1 ? 4 and then by Lemma 2.2, e(S) ? 4s and so f(S) ? 0. Case 2.1.2.2 (U 6=?) If U = X, f(S) = e(S)?[3?(n?s)]s. With V 6=? and ax ? 2 we have n?s ? 3 and so f(S) ? 0. If U = Y, we have f(S) = e(S)?3c(S)+(n?s)c(S)?2by(ay ?by) = e(T1)+2(ay ?by)t1 ?2by(ay ?by)?[3?(n?s)]c(S) = 2(ay ?by)[t1 ?by]+e(T1)?[3?(n?s)]c(S) and with t1 > by, we may again assume that n?s ? 2. But then this means av = 1, by = 1 (so n?s = 2), and fi 2 Vjqi = 1g = ?. So c(G) = 2n?1?t1 and so m = 3n? 32 ? 32s1; s1, then, must be odd. By 3.1, we have for any w1 2 T1 that aw1 ? 4. Here, c(S) = 2(ay ?1) + t1, so we will show 2(ay ?1)[t1 ?1] ? 2(ay ?1)+t1, or 2(ay ?1)[t1 ?2] ? t1. But when t1 ? 4, we have 2(s1 ?2) ? s1, and so f(S) ? 0. 21 If U = Y0, then we have f(S) = e(S)?[3?(n?s)]s?by(ay ?by) = e(T1)+by[t1 ?(ay ?by)]?[3?(n?s)]s As t1 > (ay ?by), we may again assume that n?s = 2. But then the inequality from 2.10 becomes t1 ? 2, contradicting 3.1 above. Lastly, in the case where U = Z, we have f(S) = e(S)?[3?(n?s)]c(S) = e(S)?[3?(n?s)](s+(az ?bz)) so we may again assume that n?s < 3. We will show that mS ? (s + (az ?bz)). In this case c(G) = 2n?bz ?t1 and m = 3n? 32bz ? 32t1 so bz + t1 must be even. If az = 2 then bz = 1 and thus (as bz +t1 must be even) s1 ? 3. We then need mS ? s+1; with mS ? 2t1 and t1 ? 3 this is always the case. If az ? 3, then by Lemma 2.2, mS ? 32s ? s+(az ?bz), as az < t1. Case 2.2 (V 6=?;W =?) If U =? or U = X then S =? and f(S) = 0. So flrst suppose U = Y. Then f(S) = ?3c(S)+(n?s?by)c(S). But G must have at least one part other than Ay and it must be in V. With qy = 1 there must be at least three other vertices outside of Ay as the greedy central function respects the capacities of each part, thus f(S) ? 0. The cases where U = Y0 and U = Z are similar. Case 2.3 (V = ?;W 6= ?) If either U = ? or U = Z, then S = V(G) and f(S) = 0. We will examine the remaining cases separately. 22 Case 2.3.1 (U = X) Here f(S) = e(S) ? 3c(S) + axc(S), so we will assume that ax = 2. Combining inequalities from 2.5 and 2.6 for W and X, we get (2?qw)aw +qw ?3 > 0, so qw = 1 for all w 2 W thus c(S) = s and f(S) = e(S)?s: Since aw ? ax = 2, by Lemma 2.2 we have e(S) ? 2s > c(S). Case 2.3.2 (U = Y) In all of the other cases we have examined, we have been able to show that either f(S) ? 0 directly, or, assuming that a particular set minimized f lead to a contradiction. In this case, assuming that S = V(G) n By minimizes f, this implies that f(S) < 0. Thus we would hope that the usual inequalities and other properties of the graph would lead to a contradiction. We will be able to use the usual inequalities to greatly narrow the fleld, but, as we will see, one graph will remain. In graphs where S = GnBy, f(S) = e(S)?c(S)+(n?s?by)c(S) and c(S) = 2n?2by?t1. Note also here that c(G) = 2n?by ?t1 and so m = 3n? 32by ? 32t1; thus by + t1 must be even. From the inequalities in 2.8 and 2.9 we have 2(n?ay)?3?[2n?2by ?t1 ?2(ay ?by)] > 0 (so t1 ? 4 and thus T1 6= ?) and ?2(n ? ay) + 6 + 2n + 2ay ? t1 ? 0, (and so t1 ? 6). Removing any Aw1 T1, from 2.5 we get t1 ?aw ? 3?by. This means there are at most two more vertices in T1 outside of Aw1; so either Ap is the only part in W with qw = 1 or T1 = Ap?1 [ Ap where ap?1 = ap = 2. In the latter case, as ay ? ap?1 we must have ay = 2 and so by = 1; but this contradicts the condition above that by + t1 must be even. So T1 = Ap. 23 ?2 Figure 3.1: An S3-decomposition of 2K3;5. Now we need to see if T2 6=?. By our assumptions in this case about the central function, we have m = 3n? 32by ? 32t1; counting edges we have 3n? 32by ? 32ap ? t2(ay +ap)+ayap 3t2 +3ay +3ap ? 32by ? 32ap ? t2ay +t2ap +ayap ap 3 2 ?t2 ?ay ? ??3t2 +t2ay + 32by 6 3 2 ?t2 ?ay ? ??3t2 +t2ay + 32by 9 ? 3t2 +(t2 +6)ay + 32by Assuming that t2 ? 1, we have a contradiction. Thus, T2 =?and G must be bipartite. Here is where we have a problem; the graph 2K3;5 meets all of the conditions above (and is the only graph that does), and if we apply the greedy central function to this graph, f(S) < 0! Fortunately, this is the only such graph and it has a straightforward S3-decomposition. 24 Letting c(x) = 0 for x 2 A1 and c(x) = 2 for x 2 A2 gives an S3-decomposition on 2K3;5, as illustrated in Figure 3.1. Case 2.3.3 (U = Y0) Here f(S) = e(S)?3c(S) + c(S)[n?s?(ay ?by)]. The inequalities from 2.11 and 2.10 for Y0 give 2(n?ay)?6?c(S)+by > 0 and ?2(n?ay)+3+c(S)?by ? 0; adding the left sides of these, we have ?3 > 0, obviously a contradiction. Case 3 (qi ? 2 for all i 2 I) First, we will need a lemma. We will show that the greedy central function will not flll the largest two parts (Ap?1 and Ap) to capacity. This will reduce the number of distinct values of c to at most three. Lemma 3.1. qp?1 < ?2(n?a p?1) 3 ? . Proof. If Ap?1 and Ap are both at capacity, then we must have (n?ap) ?2(n?a p?1) 3 ? +ap ?2(n?a p) 3 ? ? 2m3 so (n?ap) ?2(n?a p?1) 3 ? 2 3 ? +ap ?2(n?a p) 3 ? 2 3 ? ? 2m3 Maximizing the possible number of edges in V(G)nAp in the graph gives (n?ap)[2(n?ap?1)?2]+ap[2(n?ap)?2] ? 2 n?a p 2 ? +2ap(n?ap) and so (n?ap)[n?2ap?1 +ap ?1] ? 2ap 25 G cannot be bipartite; both parts cannot be at capacity, for we would need 2m ? 4m?4 which certainly cannot be the case if 3jm. So p ? 3 and we have (n?ap) "p?2X i=1 ai ?1+ap ?ap?1 +ap # ? 2ap but with n?ap ? 3, Pp?2i=1 ai ? 1, and ap?1 ? ap, we have a contradiction. From this, we now know that the only step of size two or greater can be from Ap?1 to Ap: Note that in the case U = Y0, the inequalities from 2.11 and 2.10 give a direct contradiction. Case 3.1 (V 6= ? 6= W) From the inequalities for V and W from 2.4 and 2.5, we get qw ?qv ? 23av + 13. (Note that this also eliminates the case where the central function is constant and q ? 2.) The central function is decreasing, so we get aw ? av. If qw ?qv = 1, we must have av = 1 for all v 2 V, but then ap = 1 and so G = 2Kn, which we are assuming it is not in light of Theorem 1.1. So under our previous assumption that ap ? 2 we must have qw ?qv ? 2, and Ap must be at capacity. Case 3.1.1 (U =?) Here W = f1;:::;p?1g, V = p, and f(S) = e(G)?3c(S) > 0. Note that if U = Z, f has the same value. Case 3.1.2 (U = X) From 2.5 and 2.6 we have qw?qx ? 23ax+ 13. Since ax ? 2, qw?qx ? 2, but we must have maxi2Ifqig = qx +1 by Lemma 2.1, so we have a contradiction. Case 3.1.3 (U = Y) From inequalities 2.5 and 2.8 we have qw?qy ? 23by+13. Thus if by ? 2, qw ?qy ? 2 and, similar to the previous case we have maxi2Ifqig = qy +1, a contradiction. If by = 1 then we need to examine f(S) a little difierently. As a split part must have size at least two and qw > qy ? qv, all parts in V must be at capacity; by Lemma 3.1 only Ap 26 may be at capacity, thus V = fpg. Then f(S) = e(S)?3c(S)+2(s?(ay ?by))(n?s)+2(ay ?by)ap = e(S)?3c(S)+e(SS) = e(G)?e(S)?3c(S) = 3c(S)?e(S) = 3c(S)?2ap > 4ap and as qp ? 2 = ? by assumption in this case, f(S) > 0. Case 3.2 (W = ?) First, assume that U = Y. Then f(S) = ?3(qy + 1)(ay ?by) + 2(ay ? by)(n?ay), so we need 2(n?ay) ? 3(qy + 1) or qy ? 2(n?ay)3 ?1. But since Ay is split, it cannot be completely flled to capacity, so qy ? j2(n?a y) 3 k ?1 and so f(S) > 0. If U = Z, then from 2.12 we have 2(n?az) ? 3qz, but this would put qz +1 over capacity. Case 3.3 (V =?) Here we can only have U = X or U = Y, and these cases are similar in the case where V 6=?6= W above. Case 4 (n?ap < 3 so qp = Cp = 0) In this case we will use a difierent central function than the other cases. First, we will eliminate the case when n ? ap < 3 and 2ap < n. Our assumption that ap ? 2 leaves only three possible graphs: 2K1;2, 2K1;1;2, and 2K2;2. None of these graphs satisfy the edge-multiplicity Condition 1. Thus if n ? ap < 3, we must have ap ? 3. Fortunately, there are only three cases to consider here, and all three are straightforward assuming the graph satisfles 3je(G). If G is bipartite, then condition 1 says we must have 3jap. We then need only put 2ap3 copies of S3 at each vertex in A1, grouping the ends in threes. If G = 2K1;1;ap, and 3jm we must have ap ? 1 mod 3 and 27 a b 1 2 3 4 Figure 3.2: An S3-decomposition of 2K1;1;4. so ap ? 4. We may, then, construct an S3-decomposition on G as follows: we will label the vertices as A1 = fag, A2 = fbg, and Ap = fv1;v2;:::;vapg. Then we may center three stars at a with ends fb;1;2g;f1;3;4g, and f2;3;4g. Then center three stars at b with ends fb;1;2g;f1;3;4g, and f2;3;4g. All edges between A1 and A2 are covered, as are the edges between A1[A2 and four vertices of Ap. If ap ? 7, the number of vertices in Ap whose edges incident to A1 [A2 have not yet been covered is a multiple of 3 and may be covered in a straightforward manner by grouping ends in threes. Figure 3.2 shows this S3-decomposition on 2K1;1;4. 28 We have now have necessary and su?cient conditions for an S3-decomposition on 2Ka1;:::;ap. With ? = 2, many of the inequalities were as tight as they could be; in par- ticular, in the cases where minfqi;2g = qi there were not many possibilities for values of qi. It was also helpful in many cases that we could assume n ? s ? 2 = ?. This will be the main di?culty in the next chapter where we examine S3-decompositions for ?Ka1;:::;ap where ? ? 3. 29 Chapter 4 Partial Results for k = 3, ? > 2 Here we examine the problem of S3-decompositions of ?-fold complete multipartite graphs where ? ? 3. We have similar necessary conditions here as we did in the previous case where ? = 2, along with one small exception to give another necessary condition. Conjecture 4.1. Let G = ?Ka1;:::ap. G has an S3-decomposition if and only if: 1. 3jm 2. a. 3(n?ap) ? m if 2ap ? n b. n+ "?(n?2ap) ? 2m3 where " = ? mod 2 if 2ap ? n 3. If G = ?K1;1;ap and ? is odd, then 3j?. The necessity of Conditions 1 and 2 were proved in Theorem 2.2. The proof for the necessity of Condition 3 will be similar to Tazawa?s proof of necessity for his Condition 3 in Theorem 1.1, though of course we will have to consider higher values of ?. Let G = ?K1;1;ap and suppose that G has an S3-decomposition. Here Cp = 0; we cannot center any stars in Ap. The copies of S3 centered in either A1 or A2 must cover all ?ap edges between then and Ap. We then have, for all i < p that ??a p 3 ? ? qi ? ??(a p +1) 3 ? (4.1) 30 We will assume here that ? is odd and either ? ? 1 mod 3 or ? ? 2 mod 3. Then by Condition 1 we must have 3jm = 2ap + 1; thus ap ? 1 mod 3. If ? ? 1 mod 3 then 4.1 above becomes ??a p 3 ? = ?ap3 + 23 ? qi ? ??(a p +1) 3 ? = ?(ap +1)3 ? 13 = ?ap3 And so we have a contradiction. The case where ? ? 2 mod 3 is similar. Thus, 3j?. Unfortunately we are not, at this time, able to prove that these conditions are always su?cient; that is, for all of the possible subsets S V(G) that either f(S) ? 0 or that assuming that set minimizes f, that there is a contradiction. We present the cases that we have flnished and comment on the ones still open. Case 1 (qi < ? for all i 2 I): We will flrst examine the case where the central function is constant. Case 1.1 (qi = qj for all i;j 2 I) We may assume that V 6=?6= W, or else we would have S = G or S = ?. Let q = ?m3n be the value of the central function on all vertices. Here f(S) = e(S)?qs[3?(n?s)]; if n?s ? 3 then f(S) ? 0 so we will assume that n?s < 3. By 2.4 and 2.5 we have ??q q aw > av (4.2) for all w 2 W and v 2 V. Since the central function is constant on all vertices we must have q ? ?2 and so aw > av. Also, since the greedy central function respects the capacities of each part and q > 0, S must consist of at least two parts. First we will examine the case when n?s = 2. 31 Case 1.1.1 (n?s = 2) Here f(S) = e(S)?qs = ?mS ?qs. Since q < ? here by assumption and aw ? 2 for all w 2 W, by Lemma 2.2 mS ? s ? q?s and thus f(S) ? 0. Case 1.1.2 (V = f1g and a1 = 1) Here we have f(S) = e(S) ? 2qs. Let aw0 be the least size of a partite set in S. If aw0 ? 4, then again by Lemma 2.2 mS ? 2s ? 2q? s and thus f(S) ? 0. We must then consider the cases when aw0 is equal to either 2 or 3. Case 1.1.2.1 (aw0 = 2) By 4.2 above, 2 > q??q so q = ?m3n < 2?3 . Now, if S consists of three or more parts, by Lemma 2.2 mS ? 2q? s and so f(S) ? 0; we will assume that S is bipartite and so G = ?K1;2;n?3. However, then m = 3n ? 7 = 3?qn, which implies that 3n ? ??q q ? = 7 ? 32n, which is only true when n ? 4, a contradiction. Case 1.1.2.2 (aw0 = 3) As in the previous case, we will assume thatS is bipartite and further assume that ap ? 5 as mS ? 3(s?3) ? 2s when s ? 9. By 4.2, 3 > q??q so q = ?m3n < 3?4 . But if S is bipartite then G = ?K1;3;n?4 so m = 4n?13 and q = ?(4n?13)3n < 3?4 implies that n < 6. With S consisting of at least two parts of size at least three, we have a contradiction. Case 1.2 (qi ? ? for all i 2 I, qi = qj + 1 for some i;j 2 I) These cases are the ones that prevent this conjecture from being a theorem at this time. In the ? = 2 case, the necessary conditions in the related cases there implied that 1 ? qi ? 2 for all i. However, increasing lambda stretches out this set of inequalities, and we have ?2 possible central function values to consider. In particular, in the case where ? = 2 the fact that the greater of the two values in the central function was equal to ? was particularly helpful. In these cases, however, the inequalities in section 2.3.1 alone are not enough to draw any conclusions toward proving that either f(S) ? 0 or that a given set cannot minimize f. Case 2 (qi ? ? for all i 2 I) As before, we will flrst examine the case when the central function is constant. 32 Case 2.1 (qi = qj for all i;j 2 I) As in other cases where the central function is constant, we must have U =?, and if v =? or W =? then S = V(G) or S =? respectively. Thus we may assume W 6= ? 6= V. The inequalities 2.4 and 2.5 give qw ?qv ? ?av3 + 13 ? 0, a contradiction. Case 2.2 (qi > qj for some i;j 2 I) Case 2.2.1 (W 6=?6= V) First we will examine the case when U =?. Case 2.2.1.1 (U = ? or U = Z) In this case we will need look at f a little bit difierently; we will put f in terms of S. Here we have f(S) = e(S)?3c(S)+ X x2S y=2S ?(xy) = e(S)?3c(S)+e(SS) = e(G)?e(S)?3c(S) = 3c(G)?e(S)?3c(S) = 3c(S)?e(S) If S consists of only one part, then e(S) = 0 and f(S) ? 0. Let us then assume that S consists of two or more parts. Inequalities 2.4 and 2.5 give us qw ?qv ? ?av3 + 13 > 0 Thus, qw > qv and as c is decreasing, av ? aw for all v 2 V and w 2 W; but then p 2 V. With our assumption that ap ? 2 and ? ? 3, we then have qw ?qp ? 2. The greedy central 33 function will only give two parts with such a difierence in values if either every part in V is at capacity. We will now show that 3c(S) ? e(S). Let S = Spi=fl+1 Ai and s = jSj. Then 3c(S) = 3 pX i=fl+1 ??(n?a i) 3 ? ai ? 3 pX i=fl+1 ??(n?a i) 3 ? 2 3 ? ai ? pX i=fl+1 [?(n?ai)?2ai] = ? pX i=fl+1 (n?ai)ai ?2s With qfl ?qfl+1 ? 2, Afl+1 must be at capacity and Cfl > Cfl+1 so afl+1 > afl; by Lemma 2.2 we have e(S) ? 2s. Finally, ? pX i=fl+1 (n?ai)ai ?2s ? ? pX i=fl+1 (n?ai)ai ?e(S) = 2e(S)+e(SS)?e(S) = e(SS)+e(S) ? e(S) The case where U = Z is similar, as S consists only of parts whose indices are in V. Case 2.2.1.2 (U = X or U = Y) From inequalities 2.5 and 2.6 we have qw ?qx ? ?3ax + 13. Since ax ? 2, qw ?qx ? 2, but qx + 1 is the maximum value that the central function will take, so we have a contradiction. The case where U = Y is similar. Case 2.2.2 (W =?) In this case, we must have V =?= U. Also, we may assume that U 6= X as then S =?. Suppose that U = Y. Here f(S) = ?3(qy+1)(ay?by)+?(ay?by)(n?ay), so we need ?(n?ay) ? 3qy +3 or qy ? ?(n?ay)3 ?1; this is always the case as qy +1 is the maximum value the greedy central function will take, and as it respects the capacities of each part, qy +1 ? j?(n?a y) 3 k . Thus f(S) ? 0. The case where U = Z is similar. 34 Case 2.2.3 (V = ?) Here we will assume W = ? = U and U 6= Z as that would mean S = V(G). From the inequalities 2.6 and 2.5 we have qw ? qx ? ?3bx + 13 and with our assumption that ? ? 3, we have qw ?qx ? 2. However, by Lemma 2.1 the maximum value that the greedy central function can take is qx + 1, so we have a contradiction. The case where U = Y is similar. Case 3 (n ? ap < 3) As in the ? = 2 case, we will use a difierent central function here and not the usual greedy one. We have from Condition 2a. that 3(n?ap) ? m, thus guaranteeing that ap ? 3. If G is bipartite, then this along with Condition 1 is su?cient. If G = ?K1;ap or ?K2;ap, we must have 3jap. We then need only put ?3ap copies of S3 at each vertex in A1, grouping ends in threes. Things get a bit more complicated in the case where G = ?K1;1;ap. If ? is even, we may simply use ?2 copies of the same S3-decomposition in Case 4 of Theorem 3.1. We have shown necessity for Condition 3; for su?ciency we will present an S3-decomposition on G = 3K1;1;ap which may then be copied as needed. Now suppose ? is odd and 3j?. We will separate cases by values of ap mod 3. In each case we will label the vertices as A1 = fag, A2 = fbg, and Ap = f1;2;:::;apg. Case 3.1 (ap ? 0 mod 3) As ap ? 3, we will flll A1 to capacity flrst; the remainder of the edges will have a straightforward S3-decomposition. Center 4 copies of S3 at a with ends fb;1;2g;fb;1;3g;fb;2;3g, and f1;2;3g. The number of vertices in Ap whose edges incident to a have not yet been covered is a multiple of 3 and may be covered in a straightforward manner by grouping ends in threes. All vertices from A1 to A2[Ap have now been covered. As 3jap we may easily cover the edges from b to Ap with 3ap copies of S3. 35 Case 3.2 (ap ? 1 mod 3) Here we must have that ap ? 4. As in the previous case, we flll A1 to capacity flrst. Center flve copies of S3 at a with ends fb;1;2g;fb;3;4g;f1;2;3g;fb;1;4g, and f2;3;4g. Now center four copies of S3 at b with ends f1;2;3g;f1;2;4g;f1;3;4g, and f2;3;4g. All edges between A1 and A2 as well as the edges from four of the vertices of Ap to A1 [ A2 have now been covered. If ap ? 7, the number of vertices in Ap whose edges incident to A1 [A2 have not yet been covered is a multiple of 3 and may be covered in a straightforward manner by grouping ends in threes. Case 3.3 (ap ? 2 mod 3) Here we must have that ap ? 5. We will flll A1 to capacity flrst; the remainder of the edges will have a straightforward S3-decomposition. Center at a copies of S3 with ends f1;2;3g and fb;4;5g; repeat twice more. Now center flve copies of S3 at b with ends f1;2;3g;f1;4;5g;f2;3;4g;f1;2;5g, and f3;4;5g. All edges between A1 and A2 as well as the edges from flve of the vertices of Ap to A1 [A2 have now been covered. If ap ? 8, the number of vertices in Ap whose edges incident to A1 [ A2 have not yet been covered is a multiple of 3 and may be covered in a straightforward manner by grouping ends in threes. While many of the cases here are similar to those of Theorem 3.1, higher values of ? can be problematic. In the cases where qi ? ?, even with the lower bound on qi from the necessary conditions, we had ?2 difierent values of the central function to consider. Even in Case 2.3.2 of Theorem 3.1 the greedy central function would not yield an S3-decomposition. We were then able to come up with a central function that worked, and we suspect the same will need to be done in similar cases for ? ? 3. 36 Chapter 5 Conclusion We have only begun to scratch the surface of solving the most general problem of flnding Sk-decompositions of ?-fold complete multipartite graphs. Using Theorem 2.1 and the fact that all vertices in a part of ?Ka1;:::;ap have the same degree, we were able to lay a foundation that we believe will helpful for solving the overall general problem of Sk- decompositions of ?-fold complete multipartite graphs for higher values of k and ?. We then developed a system of inequalities that, given a largest set S that minimizes f(S) gave many necessary conditions on G, often leading to direct contradictions. We summarize here the results we proved. Proposition 5.1. We have necessary conditions that are easily checked for flnding Sk- decompositions of ?-fold complete multipartite graphs. These conditions are also su?cient for k = 2 and all values of ? and for k = 3 and ? = 2. In our attempt at the case where k = 3 and ? ? 3, we ran into di?culty in the cases where qi ? ? for all i. It is likely, as in the related cases in Theorem 3.1, that we will need to develop another central function to get the desired result. We have begun some preliminary work in flnding Sk-decompositions for 2Ka1;:::;ap where k ? 4. The main di?culty in this case is, again, when qi ? ? = 2. In most of those cases in the case where k = 3, we could assume that n?s < 3, which only left a small handful of possible subcases. A similar assumption is not nearly as helpful for larger values of k, especially in the case where n?ap < k. We summarize the open cases remaining. 37 Proposition 5.2. For k = 3, the problem of flnding easily checked necessary and su?cient conditions for Sk-decompositions of ?-fold complete multipartite graphs is still open for graphs where ? ? 3, the greedy central function is not constant, and c(x) ? ? for all x 2 V(G). It is also open for ? ? 2 and k ? 4. During our investigation, we developed a small computer program to search for graphs with particular properties. We have included the source code for our program that flnds the set(s) that minimize f(S) for graphs with a given number of vertices in the Appendix. Using this program, we are developing some ideas on how to proceed and what types of graphs we may need to try a new central function on. 38 Bibliography [1] West, Douglas B. \Introduction to Graph Theory," First Edition. Prentice-Hall (1996). [2] Tarsi, Michael. \Decomposition of complete multigraphs into stars," Discrete Math. 26 (1979), no. 3, 273 { 278. [3] Tazawa, Shinsei. \Decomposition of a complete multi-partite graph into isomorphic claws," SIAM J. Alg. Disc. Math. 6 (1985), no. 3, 413 { 417. [4] Priesler, Miri; Tarsi, Michael. \Multigraph decomposition into stars and into multi- stars," Discrete Math. 296 (2005), no. 2-3, 235 { 244. [5] Edmonds, Jack. \Paths, trees, and owers," Canad. J. Math. 17 (1965) 449 { 467. [6] Hofiman, D.G. \The Real Truth About Star Designs," Discrete Math. 284 (2004) 177 { 180. 39 Appendix We include here the source code for a program written in C++ to examine when a k-star design on a graph G is possible. Various adaptations of this program were also used to flnd graphs with speciflc properties. #include #include // Prototype for function that will use graph to figure things out int kstars(int a[100], int n, int p, int lambda); int main(int argc, char* argv[]) { int n, p, i, x, s, y, lambda; int a[100]; bool alldone = false; /* for (n = 4; n <= 20; n++) { p = n-1; for (i=1; i<=p-1; i++) a[i] = 1; a[p] = 2; cout << "What about lambda?"; cin >> lambda; // Now do what needs to be done on the graphs with n vertices while (!alldone) { // Call function to figure out everything! kstars(a, n, p, lambda); // Compute the next graph to be worked on if needed if (p > 1) { s = a[p - 1] + a[p]; x = a[p - 1]; y = floor(s / (x + 1)); for (i = p-1; i <= p-2 + y; i++) a[i] = x + 1; 40 p = p - 2 + y; a[p] = a[p] + s - y*(x+1); } else alldone = true; } alldone = false; } kstars(a, n, p, lambda); } int kstars (int a[100], int n, int p, int lambda) { int i, j, m, e_G, k, t, starsLeft, beta, b_beta, stopPart, f, c_S, e_S, minsum, s, min_f, num_with_min, splittype, num_at_cap, g; int cap[100], q[100], S[100], min_splittype[256]; int sets_with_min[256][256]; bool splitPart, donewithsets, foundone; // Compute m (number of edges) m = n*n; for (i=1; i <= p; i++) { m -= a[i]*a[i]; } m = m/2; e_G = m * lambda; // Print the graph and number of edges cout << "\nG = "; for (i=1; i<=p; i++) { cout << a[i] << " "; } // Start looking through the possible values of k for something // that might work. // We?ll start at k=3 as k<2 is done and/or trivial for (k=3; k <= n - a[p]; k++) { foundone = false; 41 // Check condition 1 if (e_G == 0 || e_G % k != 0) { // cout << ": Condition 1 failed for k = " << k << ".\n\n"; continue; } // Condition 2? if (n - a[p] >= k && k*(n - a[p]) > m) { // cout << ": Condition 2 failed for k = " << k << ".\n\n"; // continue; } // This looks OK so far, so let?s compute the capacities of each part for (i=1; i <= p; i++) { if (n-a[i] >= k) cap[i] = floor(lambda*(n-a[i])/k); else cap[i] = 0; } // Now assign our greedy central function to this graph, // going part by part.We?ll first see if we have enough stars // for the whole part. If so, go ahead and give every vertex // in this part a star. If there are some left but not // enough to go around to every vertex, give out what we can // and then make a note of the part number where we had to stop // (beta) and where in the part we had to stop (a[beta]-b_beta). starsLeft = e_G / k; // Reset the q?s to all zeros for (i=1; i<=p; i++) q[i] = 0; // stopPart is the last part that isn?t at capacity (and therefore // where we want to stop giving out stars). stopPart = p; splitPart = false; b_beta = 0; do { 42 for (i=stopPart; cap[i] == q[i] && i > 1; i--); stopPart = i; for (i=1; i<=stopPart && a[i] <= starsLeft; i++) { q[i] += 1; starsLeft -= a[i]; } // This checks to see if we didn?t have enough stars if (a[i] > starsLeft && starsLeft > 0 && i <= stopPart) { beta = i; b_beta = a[beta] - starsLeft; starsLeft = 0; splitPart = true; } } while (starsLeft > 0); // Now that the greedy central function is set, we need to // check condition ii). For the graphs we?re looking at though, // it?s not too bad. We need only check to see if the values of // the central function in the last two parts add to lambda. if (q[p] + q[p-1] < lambda) { cout << ": Condition 2 failed for k = " << k << ". Moving on...\n"; continue; } // This prints out the central function. num_at_cap = 0; for (i=1; i<=p; i++) if (q[i] == cap[i] && cap[i] > 0) num_at_cap++; cout << "\nOur central function for k = " << k << ":\n"; for (i=1; i<= p; i++) cout << "q[" << i << "] = " << q[i] << " capacity = " << cap[i] << "\n"; if (splitPart) cout << "beta = " << beta << ", b_beta = " << b_beta << ", a[beta] = " << a[beta] << "\n"; */ 43 // Now we?re going to check this to see what subset of parts // minimizes the inequality in condition iii). To do this, we?re // going to have to look at all possible subsets. // To start off with, we need to set up an array, S, that will // keep track of what parts are in the set we?re looking at (1) // and aren?t (0). First we need to reset // S to all zeros. for (i=1; i<=100; i++) for (j=1; j<=p; j++) sets_with_min[i][j] = 0; min_f = 0; num_with_min = 0; for (i=1; i<=100; i++) min_splittype[i] = 0; if (!splitPart) { for (i=1; i<=p; i++) S[i] = 0; donewithsets = false; while (!donewithsets) { donewithsets = true; f = 0; c_S = 0; e_S = 0; minsum = 0; s = 0; for (i=1; i<=p && donewithsets == true; i++) if (S[i] == 0) donewithsets = false; for (i=1; i<=p; i++) { if (S[i] == 1) { c_S += (a[i]*q[i]); s += a[i]; e_S -= pow(a[i],2); if (q[i] < lambda) minsum += a[i]*q[i]; else minsum += (a[i]*lambda); } } e_S += pow(s,2); e_S = e_S * lambda / 2; minsum *= (n - s); 44 f = e_S - k*c_S + minsum; // Now we need to see if this is less than the minimum // value of f we?ve reached so far. if (f < min_f) { min_f = f; num_with_min = 1; for (j=1; j<=p; j++) sets_with_min[1][j] = S[j]; } else if (f == min_f) { num_with_min++; for (j=1; j<=p; j++) sets_with_min[num_with_min][j] = S[j]; } // If this isn?t the last subset (namely, everything) // then compute the next set if (!donewithsets) { t=p; while (S[t] != 0) t--; S[t] = 1; for (i=t+1;i<=p;i++) S[i] = 0; } } } else { // Now things get a little trickier. We?ve got a split part, // so we?re going to have to look at three possibilities: // the split part being in X, Y, or Z. // The int splittype variable keeps track of what // case we?re looking at: // 0 = X // 1 = Y // 2 = Y? // 3 = Z for (splittype=0; splittype <=2; splittype++) { for (i=1; i<=p; i++) S[i] = 0; 45 donewithsets = false; while (!donewithsets) { donewithsets = true; f = 0; c_S = 0; e_S = 0; minsum = 0; s = 0; for (i=1; i<= p-1 && donewithsets == true; i++) if (S[i] == 0) donewithsets = false; for (i=1; i