Gregarious Path Decompositions of Some Graphs by Guven Yuceturk 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 6, 2011 Keywords: gregarious, path, decomposition Copyright 2011 by Guven Yuceturk Approved by Dean G. Ho man, Chair, Professor of Mathematics & Statistics Curt Lindner, Professor of Mathematics & Statistics Chris Rodger, Professor of Mathematics & Statistics Peter Johnson, Professor of Mathematics & Statistics Abstract Let G be a simple graph and f(v) a positive integer for each vertex v of G. Form Gf by replacing each v by a set F(v) of f(v) vertices, and each edge uv by complete bipartite graph on bipartition (F(u);F(v)). Can we partition Gf into paths of length 2 which are gregarious, that is, meet three di erent F(u)?s? ii Acknowledgments I would rst like to thank Dr. Dean G. Ho man for his invaluable knowledge, guidance, and patience. I am indebted to him. I would also like to thank Dr. Chris Rodger and the rest of the Auburn faculty for guiding me throughout my graduate career. I would like to thank Dan Roberts for his insightful comments. Finally, I would like to thank my family and my friends for their love and support throughout my life. iii Table of Contents Abstract . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ii Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iii List of Figures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . vi List of Tables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . viii List of Abbreviations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ix 1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.1 History of the problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 2 Tutte?s f-Factor Theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 2.1 Tutte?s f Factor Theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 2.2 Applying Tutte?s f-Factor Theorem . . . . . . . . . . . . . . . . . . . . . . . 7 3 Parity Balanced Bipartite Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . 12 3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 3.2 Bipartite Graphs with Four Degrees . . . . . . . . . . . . . . . . . . . . . . . 13 3.3 Parity balanced Bipartite Graphs . . . . . . . . . . . . . . . . . . . . . . . . 18 4 Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 4.1 Complete Multipartite Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . 31 4.1.1 Complete Tripartite Graph . . . . . . . . . . . . . . . . . . . . . . . . 31 4.2 Star Multipartite Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32 4.3 Cycle Multipartite Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35 4.3.1 Even Cycles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35 4.3.2 Odd Cycles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38 4.4 Path Multipartite Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40 4.5 Some Tree Multipartite Graphs . . . . . . . . . . . . . . . . . . . . . . . . . 42 iv 4.5.1 Necessary And Su cient Conditions for T(A1;A2;A3;B1;:::;Bn) . . 46 4.5.2 Necessary And Su cient Conditions forT(C1;:::;Cm;A1;A2;B1;:::;Bn) 48 Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57 v List of Figures 1.1 Example of Gregarious Path Decomposition . . . . . . . . . . . . . . . . . . . . 1 1.2 Example of Gf and G[h] . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 2.1 Example of an f-factor . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 2.2 Example of an f-factor . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 2.3 De nition of (S;T) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 2.4 Example of a G-triple . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 2.5 Component of B . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 2.6 Tutte?s f-factor Theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 2.7 Gf and G[h] . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 2.8 G[h] and L[h](G) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 2.9 LM(G) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 2.10 Example of how to apply Tutte?s f-Factor Theorem . . . . . . . . . . . . . . . . 10 2.11 Counter Example . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 3.1 Bipartite Graph with Four Degrees . . . . . . . . . . . . . . . . . . . . . . . . . 14 3.2 Adding balanced distributions . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 vi 3.3 Example of a parity balanced bipartite graph . . . . . . . . . . . . . . . . . . . 18 3.4 Example of a bipartite complement . . . . . . . . . . . . . . . . . . . . . . . . . 19 3.5 Translating PBBG to a BGwFDs . . . . . . . . . . . . . . . . . . . . . . . . . . 22 3.6 Bipartite graphs with 2 edges . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 3.7 Exception for b = 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 4.1 K(A;B;C) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 4.2 Multipartite Star S(A;B1;B2;:::;Bn) . . . . . . . . . . . . . . . . . . . . . . . . 33 4.3 Multipartite Even Cycle C2n . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36 4.4 Multipartite Odd Cycle C2n+1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38 4.5 Multipartite Path Pn . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40 4.6 T(C1;:::Cm;A1;A2;B1;:::;Bn) . . . . . . . . . . . . . . . . . . . . . . . . . . 42 4.7 T(A1;A2;A3;B1;:::;Bn) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43 4.8 Orientation of G . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43 4.9 An Example for Theorem 4.10 . . . . . . . . . . . . . . . . . . . . . . . . . . . 46 4.10 How to get conditions 2 - 4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47 4.11 How to get conditions 2 - 4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50 4.12 Types of paths . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51 vii List of Tables 3.1 Distribution of the edges . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 3.2 Exceptions for Theorem 3.12 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 4.1 Exceptions for Theorem 4.13 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49 viii List of Abbreviations PBBG Parity Balanced Bipartite Graph BGwFD Bipartite Graph with Four Degrees L(G) Line Graph of G GDDs Group Divisible Designs NASCs Necessary and Su cient Conditions TFAE The following are equivalent ix Chapter 1 Introduction Let G = (V; E) be a simple graph and f : V !N, where f(v) is a positive integer for each vertex v of G. Form the graph Gf by replacing each v by a set F(v) of f(v) vertices, and each edge uv by a complete bipartite graph on bipartition (F(u);F(v)). Our question is: \Can we partition Gf into paths of length 2, P3, which are gregarious, that is, each vertex of P3 is in a di erent F(u)?" Example 1.1. Let G = (V;E) be a graph where jVj = 5 and f : V(G) ! P such that f : (v1;v2;v3;v4)!(2;3;2;2). 2 v1 3 v2 2 v3 2 v4 G Gf Gf Figure 1.1: Example of Gregarious Path Decomposition Each color represents a di erent class of P3?s. 1 1.1 History of the problem Non-Gregarious Case: In a recent paper [3], the complete solution is given for a decomposition of any complete multipartite graph into paths of lengths 3 and 4. Dr. Ho man & Dr. Billington introduce the problem \what if we try to solve the same problem with gregarious paths?" Previous work in Gregarious Decompositions: 1. In [5], Dean G. Ho man & Elizabeth Billington give necessary and su cient conditions to decompose a complete tripartite graph into gregarious 4-cycles. They use the notion of gregarious decompositions as \a cycle is said to be gregarious if its vertices occur in as many di erent parts of the multipartite graph as possible". 2. In [6], Dean G. Ho man & Elizabeth Billington give the necessary and su cient con- ditions for gregarious 4-cycle decompositions of the complete equipartite graph Kn(m) (with n > 4 parts of size m) whenever a 4-cycle decomposition (gregarious or not) is possible, and also of a complete multipartite graph in which all parts but one have the same size. 3. In [7], Benjamin R. Smith give necessary and su cient conditions for the existence of a gregarious 5-cycle decomposition of the complete equipartite graph Km(n). 4. In [8], Elizabeth J. Billington, Benjamin R. Smith & D.G. Ho man give necessary and su cient conditions for gregarious cycle decomposition of the complete equipartite graph Kn(m) (with n parts, n> 6 or n> 8, of size m) into both 6-cycles and 8-cycles. 5. In [9] Jung R. Cho & Ronald J. Gould give necessary and su cient conditions for the existence of decompositions of the complete multipartite graph Kn(2t) into gregarious 6-cycles if n 0; 1; 3 or 4 (mod 6) . They used the method of a complete set of di erences in Zn. 2 6. In [10], Jung R. Cho gives another proof of the problem of decomposing the complete multipartite graph Kn(2t) into gregarious 6-cycles for the case of n 0 or 3 (mod 6). 7. In [11], Benjamin R. Smith gives necessary and su cient conditions for the existence of gregarious k cycle decomposition of a complete equipartite graph, having n parts of size m, and either n 0;1 (mod k), or k is odd and m 0 (mod k). 8. In [12], Elizabeth J. Billington , Dean G. Ho man & Chris A. Rodger give necessary and su cient conditions for decomposing a complete equipartite graph Kn(m) with n parts of size m into n-cycles in such a way that each cycle meets each part of Kn(m); that is, each cycle is said to be gregarious. Furthermore, they give gregarious decompositions which are also resolvable. 9. In [13], Saad I. El-Zanati, Narong Punnim & Chris A. Rodger give necessary and su cent conditions for the existence of Gregarious GDDs with Two Associate Classes having block size 3. De nition 1.2. Let G = (V; E) be simple graph and h : E!P. De ne G[h] on vertex set V as follows: if u; v2V and uv = e2E then put h(e) edges in between u and v in G[h]. Example 1.3. Let?s use the example 1.1 and de ne h(vivj) := f(vi)f(vj). 2 v1 3 v2 2 v3 2 v4 G Gf G[h] Gf Figure 1.2: Example of Gf and G[h] In G[h], any P3 will be a gregarious path of length two. 3 Chapter 2 Tutte?s f-Factor Theorem 2.1 Tutte?s f Factor Theorem De nition 2.1. Let G = (E;V) be a graph. G is called a k-regular graph if for every v2V, deg(v) = k for some k2N. De nition 2.2. Let G = (V;E) be a graph, then 1. A factor of a graph G is a spanning subgraph of G. 2. A k factor is a spanning k regular subgraph. 3. Given a function f : V(G)!Z, an f factor of a graph G is a spanning subgraph H such that dH(v) = f(v) for all v2V. Example 2.3. Let G = (V;E) be a graph with f : (v1;v2;v3;v4;v5;v6) ! (3;1;1;2;3;2), then we can get the f factor: G v1 v2 v3v4 v5 v6 1 f ?factor G 3 1 12 3 2 1 Figure 2.1: Example of an f-factor 4 De nition 2.4. If f : V(G)!Z, de ne f : V(G)!Z by f(v) = degG(v) f(v). Example 2.5. From the previous example f : (v1;v2;v3;v4;v5;v6)!(0;2;2;1;1;2) f ?factor G3 1 12 3 2 ?f ?factor 0 2 21 1 2 1 Figure 2.2: Example of an f-factor De nition 2.6. LetS;T V(G), withS\T =;, then (S;T) = the set of edges with one end in S and the other end in T. G S T?(S,T) Figure 2.3: De nition of (S;T) De nition 2.7. B = (S;T;U) is a G triple if 1. S;T;U V(G), 2. S[T[U = V(G) 5 3. S\T = S\U = T\U =; S T U 1 Figure 2.4: Example of a G-triple De nition 2.8. Let G = (V;E) be a graph and f : V !P be a function. Then de ne f(S) = X s2S f(s) for any S V. De nition 2.9. By a component of B, we mean a component of Gn(S[T). S T U c Figure 2.5: Component of B 1. If c is a component of B, let J(B;f;c) = f(c) + (c;T). 2. c is called odd or even according to if J(B;f;c) is odd or even. 3. k(B;f) = # of odd components of B. 6 Theorem 2.10. [4] G has an f factor, i for each G triple B = (S;T;U) k(B;f) + (S;T) 6 f(S) + f(T) S T U 1 Figure 2.6: Tutte?s f-factor Theorem 2.2 Applying Tutte?s f-Factor Theorem De nition 2.11. The line graph of a graph G, written L(G), is the graph whose vertices are the edges of G, with ef2E(L(G)) whenever e and f are di erent edges of G having at least one vertex of G in common. Let G = (V; E) be a simple graph and f : V !N, where f(v) is a positive integer for each vertex v of G. Then, let h : E!P where h(vivj) := f(vi)f(vj). In this way we can get Gf and G[h] with given G and f. 7 Gf B1 B2 B3 B4 ? G[h] b1b2 b2b3 b3b4 b2b 4 Figure 2.7: Gf and G[h] Now, if we have a gregarious decomposition of Gf into P3?s (denoted by Gf g,!P3), then getting decomposition of G[h] into P3?s (denoted by G[h] ,!P3) is trivial. So Gf g,!P3 )G[h] ,!P3. The opposite direction is not true, but it will still give us some of the necessary conditions for Gf g,!P3. We can apply Tutte?s f-factor theorem to solve G[h] ,!P3. G[h] B1 B2 B3 B4 e12 e23 e34 e24 ? L[h](G) e12 e23 e34e24 x1 x2 x3 x4 x5 Figure 2.8: G[h] and L[h](G) In G[h], assume that there are eij = bibj edges in between any pair of sets of vertices Bi and Bj where jBij = bi for any i. Firstly, get the line graph of G, L(G), then blow the edges of L(G) in such a way that for each vertex eij 2V(L(G)), deg(eij) is bibj in the new graph, L[h](G). In L[h](G), each edge will represent a P3 in G[h]. For example, in gure 2.8, x1 represents the number of P3?s passing through sets B1!B2!B3 in G[h]. 8 Therefore, if we nd each xi, we can nd the P3 decomposition of G[h]. To nd the xi?s, we will use Tutte?s f-factor theorem. Start with G, get L(G), let M be a su ciently large number, then get LM(G) by replacing every edge of L(G) with M edges ( g. 2.9). So if we nd an h factor of LM(G) such that h(eij) = bibj, then we can get G[h] ,!P3. e12 e23 e34e24 M M M M M Figure 2.9: LM(G) Theorem 2.12. LM(G) has an h factor for all su ciently large M , i for each L(G) triple B = (S;T;U) where T is independent and (T;U) = 0, k(B;h) +h(T) 6 h(S): Proof. Let M be a su ciently large number. From Tutte?s f-factor theorem, for all L(G)-triples B = (S;T;U): k(B;h) + LM(S;T) 6 h(S) + h(T) k(B;h) +M L(S;T) 6 h(S) +MdegL(T) h(T) k(B;h) +h(T) h(S) 6 M(degL(T) L(S;T)) Here, degL(T) > L(S;T) for any L(G) triple since degL(T) = X t2T deg(t) and L(S;T) = number of edges in between S & T. In addition, when degL(T) > L(S;T) the inequality holds since we can choose M su ciently large and the left hand side of the 9 inequality doesn?t depend on M. So the only problem is when degL(T) = L(S;T). Which means T is independent and there is no edge in between T & U ( L(T;U) = 0). So the condition we need to check for each L(G) triple reduces to: k(B;h) +h(T) 6 h(S) when T is independent and L(T;U) = 0. Example 2.13. Let G be the underlying graph in Figure 2.8. Let?s nd the necessary conditions for G[h] to have a gregarious P3 decomposition. We need to check k(B;h) +h(T) 6h(S) for all L(G) triples B = (S;T;U) where T is independent and L(T;U) = 0. S T U e23 e24 e12 e34 S T U e23 e24 e12 e34 S T U e23 e24 e34 e12 Figure 2.10: Example of how to apply Tutte?s f-Factor Theorem where deg(eij) = bibj. So we can get conditions: 1. b1b2 +b3b4 6b2b3 +b2b4 2. b1b2 6b2b3 +b2b4 3. b3b4 6b2b3 +b2b4 10 Therefore the necessary condition to decompose G[h] into gregarious P3?s is: b1b2 +b3b4 6b2b3 +b2b4 since 1 is stronger than 2 and 3. In summary, if we have a gregarious decomposition of Gf into P3?s (Gf g,!P3), then getting a decomposition of G[h] into P3?s is trivial (G[h] ,!P3). So Gf g,!P3 )G[h] ,!P3. The opposite direction is not true (G[h] ,!P3 ; Gf g,!P3, see the following counter example), but it will still give us some of the necessary conditions for Gf g,!P3. Example 2.14. Let G = S3 be a tristar and de ne f : V(G)!P by f : (a;v1;v2;v3)!(2;1;1;1). S3 Gf G[h] Figure 2.11: Counter Example Gf doesn?t have a gregarious P3 decomposition since both vertices in the root have odd degree. On the other side, G[h] has a gregarious P3 decomposition, each color gives a di erent gregarious P3. 11 Chapter 3 Parity Balanced Bipartite Graphs Let a; b 2 P and e 2 N , and let a; b 2f0;1g. We say the simple bipartite graph G on bipartition (A;B), where jAj = a and jBj = b, with e edges, is parity balanced with parameters (a; b; e; a; b) if 8u2A, deg(u) a (mod 2), and further 8v2A, jdeg(u) deg(v)j6 2, 8u2B, deg(u) b (mod 2), and further 8v2B, jdeg(u) deg(v)j6 2. We will give necessary and su cient conditions on the parameters (a; b; e; a; b) for the existence of such graphs. 3.1 Introduction All the graphs are simple, i.e., they have no loops or multiple edges. Let P be the set of positive integers and N be the set of non-negative integers. De nition 3.1. The integer vector (x1; x2; :::; xt) is said to be balanced if jxi xjj 6 1 for all 1 6 i; j 6 t. Two vectors are equivalent if one can be obtained from the other by permuting the entries. De nition 3.2. Let G be a bipartite graph on bipartition (A; B). If for all v2A, degG(v) = d1 and for all w2B, degG(w) = e1, then we will call G a (d1; e1) regular bipartite graph. The following lemmas are proved in [1], p. 399. Lemma 3.3. Let v and w be balanced vectors with the same number of coordinates. Then, for some vector w0 equivalent to w, v +w0 is balanced. Lemma 3.4. Let a; b2P, and let e6ab be a non-negative integer. Then there is a bipartite graph G on bipartition (A; B) with both (degG(v)jv2A) and (degG(y)jy2B) balanced. 12 3.2 Bipartite Graphs with Four Degrees The theorems we will be proving here can be proven by using the Ryser-Gale theorem ([2], p. 185), but the proof is much harder. Theorem 3.5. Let a1; a2; b1; b2; d1; d2; e1; e2 be non-negative integers. Then: There is a simple bipartite graph on bipartition (A; B), where A consists of a1 vertices of degree d1 and a2 vertices of degree d2; and B consists of b1 vertices of degree e1 and b2 vertices of degree e2, if and only if ( )a1d1 +a2d2 = b1e1 +b2e2 1. a1d1 6a1b1 +b2e2, or, equivalently, b1e1 6a1b1 +a2d2 2. a1d1 6a1b2 +b1e1, or, equivalently, b2e2 6a1b2 +a2d2 3. b1e1 6a2b1 +a1d1, or, equivalently, a2d2 6a2b1 +b2e2 4. b2e2 6a2b2 +a1d1, or, equivalently, a2d2 6a2b2 +b1e1 5. either a1 = 0, or d1 6b1 +b2 6. either a2 = 0, or d2 6b1 +b2 7. either b1 = 0, or e1 6a1 +a2 8. either b2 = 0, or e2 6a1 +a2 Necessity: Proof. Each side of ( ) counts the total number of edges, hence they must be equal. Condi- tions 5 - 8 come from the fact that maximum degree of any vertex is less than the number of vertices in the other part. Now for conditions 1 - 4: 13 A d1A1 d2A2 x B e1 B1 e2 B2 Figure 3.1: Bipartite Graph with Four Degrees For i = 1; 2, let Ai (resp. Bi) be the vertices of degree di (resp. ei) in Ai (resp. Bi). In addition, let?s assume that there are x edges in between vertices of A1 and B1. If we look at the other pairs, we will get: B1 B2 A1 x a1d1 x a2d2 b1e1 +x A2 b1e1 x = b2e2 a1d1 +x Table 3.1: Distribution of the edges Using table 3.1, we can get the following inequalities: 0 6 x 6a1b1 0 6 a1d1 x 6a1b2 0 6 b1e1 x 6a2b1 0 6 a2d2 b1e1 +x 6a2b2 14 So, we can get: 0 6x6 a1b1 a1d1 a1b2 6x6 a1d1 b1e1 a2b1 6x6 b1e1 b1e1 a2d2 6x6 a2b2 a2d2 +b1e1 We can get sixteen inequalities on the variables (a1; a2; b1; b2; d1; d2; e1; e2) from above since we have x in the middle of all of the four inequalities. If we use the left side of the rst inequality and right sides of the all them, then we can get: 0 6 a1b1 0 6 a1d1 0 6 b1e1 0 6 a2b2 a2d2 +b1e1 )a2d2 6a2b2 +b1e1;cond. 4 X From the second one: a1d1 a1b2 6 a1b1 )d1 6b1 +b2 a1d1 a1b2 6 a1d1 )0 6a1b1 a1d1 a1b2 6 b1e1 )a1d1 6a1b2 +b1e1;cond. 2 X a1d1 a1b2 6 a2b2 a2d2 +b1e1 )a1d1 +a2d2 6a2b2 +b1e1 +a1b2 If we use ( ), we will get a1d1 + a2d2 = b1e1 + b2e2 6 a2b2 + b1e1 + a1b2, so this reduces to e1 6a1 +a2. 15 From the third one: b1e1 a2b1 6 a1b1 )e1 6a1 +a2 b1e1 a2b1 6 a1d1 )b1e1 6a2b1 +a1d1;cond. 3 X b1e1 a2b1 6 b1e1 )0 6a2b1 b1e1 a2b1 6 a2b2 a2d2 +b1e1 )d2 6b1 +b2 From the fourth one: b1e1 a2d2 6 a1b1 )b1e1 6a1b1 +a2d2;cond. 1 X b1e1 a2d2 6 a1d1 )b1e1 6a1d1 +a2d2 b1e1 a2d2 6 b1e1 )0 6a2d2 b1e1 a2d2 6 a2b2 a2d2 +b1e1 )0 6a2b2 In the second equation, if we use a1d1 +a2d2 = b1e1 +b2e2, then we will get b1e1 6b1e1 +b2e2)0 6b2e2. 16 Su ciency: Proof. Assume there is bipartite graph (A; B) satisfying the necessary conditions and there are x edges in between the vertices of A1 and B1 like in gure 3.1. Therefore, we can nd the number of edges in between other vertices using the remaining edges like in table 3.1. Now using the construction in [1] on pg. 399, 1. distribute x edges on a1 vertices with balanced degrees. 2. distribute a1d1 x on a1 vertices with balanced degrees. So we will get two balanced vectors with the same number of entries. BalancedDistrubutionofxedgesona1vertices BalancedDistrubutionofa1d1?xedgesona1vertices 1less 1moreEqual BalancedBalancedBalanced Figure 3.2: Adding balanced distributions At the end, we will have one of these three cases from gure 3.2 and all of them will still have balanced distributions since both distributions were balanced to begin with. However, the rst two cases are impossible, since we have a balanced distribution of a1d1 edges on a1 vertices, this means that each vertex will be incident with d1 edges. In the same manner we can prove that we can distribute the remaining edges with the desired degrees. 17 3.3 Parity balanced Bipartite Graphs De nition 3.6. Let a; b2P and e2N , and let a; b2f0;1g. We say the bipartite graph G with e edges on bipartition (A;B), with jAj = a and jBj = b, is parity balanced with parameters (a; b; e; a; b) if 1. 8u2A, deg(u) a (mod 2) and further 8v2A, jdeg(u) deg(v)j6 2. 2. 8u2B, deg(u) a (mod 2) and further 8v2B, jdeg(u) deg(v)j6 2. Example 3.7. Let jAj= a = 6, jBj= b = 5, e = 14, a = 1 and b = 0. e=14Adeg=1 epsilon1a=1 deg=3 |A|=a=6 B deg=2 epsilon1b=0 deg=4 |B|=b=5 Figure 3.3: Example of a parity balanced bipartite graph De nition 3.8. If A and B are disjoint sets, we denote KA;B to be the complete bipartite graph on bipartition (A; B). De nition 3.9. Let KA;B be a complete bipartite graph on bipartition (A;B). A bipartite complement of a bipartite graph G on bipartition (A; B) with edge set E is the bipartite graph G0 on bipartition (A; B) with the edge set E0 where E0 = E(KA;B)nE. Fact 3.10. If G is a parity balanced bipartite graph with parameters (a; b; e; a; b), then G0 is a parity balanced bipartite graph with parameters (a; b; e0 = ab e; 0a; 0b) where a + 0a b (mod 2) and b + 0b a (mod 2) 18 Example 3.11. The bipartite complement of G is G0 with parameters (a = 6; b = 5; e0 = ab 14 = 30 14 = 16; 0a = 0; 0b = 0): eprime =16Adeg=4 epsilon1primea=0 deg=2 |A|=a=6 B deg=4 epsilon1primeb=0 deg=2 |B|=b=5 Figure 3.4: Example of a bipartite complement where a + 0a = 1 + 0 = 1 5 (mod 2) and b + 0b = 0 + 0 6 (mod 2). Theorem 3.12. Let a; b2P, e2N, a; b; 0a; 0b2f0;1g, a + 0a b (mod 2), b + 0b a (mod 2). Then, there is a parity balanced bipartite graph G on bipartition (A; B) with parameters (a; b; e; a; b) if and only if aa 6 e 6 ab 0aa , bb 6 e 6 ab 0bb, and all of these are congruent (mod 2), with the following exceptions: 19 e a b a 0a b 0b 2 2 2 0 0 0 0 2 3 0 1 0 0 3 2 0 0 0 1 odd> 3 odd> 3 0 1 0 1 odd> 3 even> 3 0 0 0 1 0 0 1 0 even> 3 odd> 3 0 1 0 0 1 0 0 0 even> 3 even> 3 1 1 1 1 0 0 0 0 ab 2 2 2 0 0 0 0 2 3 1 0 0 0 3 2 0 0 1 0 odd> 3 odd> 3 1 0 1 0 odd> 3 even> 3 0 0 1 0 0 0 0 1 even> 3 odd > 3 1 0 0 0 0 1 0 0 even> 3 even > 3 1 1 1 1 0 0 0 0 Table 3.2: Exceptions for Theorem 3.12 20 Necessity: Proof. For any u2A we have degG(u) + degG0(u) = b so degG(u) + degG0(u) b (mod 2) where degG(u) a (mod 2) and degG0 (u) 0a (mod 2) by de nition, and a + 0a b (mod 2) follows. In the same way, we can get b + 0b a (mod 2). To get aa6e6ab 0aa and bb6e6ab 0bb, if one of a; 0a; b; 0b is 1, then we have to have enough edges in either G or G0. Finally, to get aa; e; ab 0aa, bb; ab 0bb all congruent (mod 2); e = X u2A degG(u) a a (mod 2),and a + 0a b (mod 2))a a +a 0a ab (mod 2))a a ab a 0a (mod 2). In the same way we can get the other conditions. For the exceptions, it is easy to prove that there is no parity balanced bipartite graph with parameters given in table 4.1. Figure 3.6 shows all possible parity balanced bipartite graphs with 2 edges and and the ones with ab 2 edges will be bipartite complement of these graphs. Su ciency: Proof. We can use theorem 3.5 for this proof. De ne n; m; qa; ra; qb; rb2N by, e = 2n+ aa = 2m+ bb n = aqa +ra, m = bqb +rb 0 6ra 6a 1, 0 6rb 6b 1. So e = 2aqa + 2ra + aa = 2bqb + 2rb + bb. qa = e aa 2ra2a = e aa2a raa = e aa 2a . In the same way, qb = e bb 2b . Now let?s translate this problem into\bipartite graphs with four degrees" since we already know NASCs for those graphs ( gure 3.5). 21 A a1=a?rad 1=2qa+epsilon1a a2=rad 2=2qa+epsilon1a+2 B b1=b?rbe 1=2qb+epsilon1b b2=rbe 2=2qb+epsilon1b+2 Figure 3.5: Translating PBBG to a BGwFDs Note that ( ) holds since: (a ra)(2qa + a) +ra(2qa + a) = (b rb)(2qb + b) +rb(2qb + b) Case 1: Assume a2 = 0 = b2, then we will get a (d1; e1) regular bipartite graph. Since a2 = 0, and b2 = 0, we only need to prove 1, 5 and 7 in theorem 3.5. Let?s start proving conditions 5 and 7 which say: d1 6 b1 +b2 2qa + a 6 b rb +rb = b and e1 6 a1 +a2 2qb + b 6 a ra +ra = a So for 5 if we prove 2qa + a 6 b, we are done. Using 2qa = e aa 2raa = ea a 2raa ; we can get 2qa + a = ea a 2raa + a = ea 2raa 6 b 2raa < b. We can prove 7 in the same way. 22 Now, let?s prove 1: a1d1 6 a1b1 +b2e2 a1d1 6 a1b1 since b2 = 0 d1 6 b1 2qa + a 6 b and we just proved this in 5 Case 2: Assume a2 = 0 and b2 6= 0 (a2 6= 0 and b2 = 0 is just the symmetric case). Since a2 = 0, we only need to prove 1, 2, 5, 7 and 8 in theorem 3.5. 5 and 7 are the same as in Case 1. 1 and 2 will reduce to 7 and 8, respectively since a2 = 0. So just proving 8 is enough which says: e2 6 a1 +a2 2qb + b + 2 6 a1 = a since a2 = 0 So 2qb = eb b 2rbb , using this: 2qb + b + 2 = eb b 2rbb + b + 2 = eb 2rbb + 2 6a 0b 2rbb + 2 0; rb > 0; 2qb + b + 2 > 0. So we can assume rb >b 2qa a+1. In addition, recall that e = 2n+ aa = 2aqa+2ra+ aa. 24 Need to prove: a1d1 6 a1b1 +b2e2 (a ra)(2qa + a) 6 (a ra)(b rb) +rb(2qb + b + 2) 2aqa +a a ra(2qa + a) 6 ab arb bra +rarb +rb(2qb + b + 2) 2aqa +a a ra(2qa + a) + 2ra 2ra 6 ab arb bra +rarb +rb(2qb + b + 2) (2aqa +a a + 2ra) ra(2qa + a + 2) 6 ab arb bra +rarb +rb(2qb + b + 2) e+ra(b (2qa + a + 2)) +rb(a (2qb + b + 2)) rarb 6 ab So if we show e + ra(b (2qa + a + 2)) + rb(a (2qb + b + 2)) rarb 6 ab , we are done. Using rb >b 2qa a + 1, we can get ra(b (2qa + a + 2)) 0; (b rb) > 0; 2qb + b 0. We can assume 2qa + a + 1 >rb. We need to prove: a1d1 6 a1b2 +b1e1 (a ra)(2qa + a) 6 (a ra)rb + (b rb)(2qb + b) 2aqa +a a ra(2qa + a) 6 arb rarb + 2bqb +b b rb(2qb + b) 2aqa +a a ra(2qa + a) + 2ra 2ra 6 arb rarb + 2bqb +b b rb(2qb + b) + 2rb 2rb (2aqa +a a + 2ra) ra(2qa + a + 2) 6 arb rarb + (2bqb +b b + 2rb) rb(2qb + b + 2) e ra(2qa + a + 2) 6 arb rarb +e rb(2qb + b + 2) rarb +rb(2qb + b + 2) 6 arb +ra(2qa + a + 2) If we show rarb + rb(2qb + b + 2) 6 arb + ra(2qa + a + 2), then we have shown (2). Using 2qa + a + 1 >rb we can get rarb ra and 2qa + a + 2 >rb)2qa + a + 1 >rb. If we turn back to the problem and use the fact, which follows from 8, that 2qb + b + 2 6a, 27 then: rb(2qb + b + 2) 6 rba = rarb + (a ra)rb 6 rarb + (a ra)(2qa + a + 1) So the only problem is when rb = 2qa + a + 1. Similarly, we can assume ra = 2qb + b + 1. Need to show: b2e2 6 a2b2 +a1d1 rb(2qb + b + 2) 6 rarb + (a ra)(2qa + a) (2qa + a + 1)(2qb + b + 2) 6 (2qa + a + 1)(2qb + b + 1) + (a ra)(2qa + a) 2qa + a + 1 6 (a ra)(2qa + a) 1 6 (a ra 1)(2qa + a) 1 6 (a ra 1)(rb 1) Here rb > 1 since ra 6= 06= rb. In this case both are positive and we can assume a ra > 1 since 0 6 ra < a. Therefore, we only need to prove rb 6= 1 or a ra 6= 1. First, suppose rb = 1, then rb = 2qa + a + 1 = 1 so qa = 0 and a = 0. e = 2aqa + 2ra+a a = 2bqb + 2rb +b b 2ra = 2bqb + 2 +b b 2(2qb + b + 1) = b(2qb + b) + 2 2(2qb + b) = b(2qb + b) 0 = (b 2)(2qb + b) 0 = (b 2)(ra 1) 28 Therefore, in this case, either b = 2 or ra = 1. If ra = 1, then e = 2ra = 2 and this is not possible since when e = 2 there are only two bipartite graphs with 2 edges (see gure 3.6) and both of them have either b2 = 0 or a2 = 0 = b2, which contradicts the assumption a26= 06= b2. We can get the exceptions in table 4.1 with parameters (a; b; e = 2; a; 0a; b; 0b) easily since no other bipartite graphs exist with 2 edges but the ones in gure 3.6. A B A B Figure 3.6: Bipartite graphs with 2 edges Now, assume b = 2 where rb = 1 and ra > 2. BA d2=2 d1=0 Figure 3.7: Exception for b = 2 There are only two vertices in B and d2 = 2 which means every vertex in a2 will be adjacent to the vertices in B. This implies b1 = 2, and b2 = 0, and contradicts the assumption b26= 0. So we nished proving the case where rb6= 1. Therefore we can assume rb 2. 29 Now assume a = ra + 1: If ra = 1, then a = 2 and it will be the same case as b = 2. Assume ra > 2, so a> 3 where ra = 2qb + b + 1 = a 1. e = 2bqb + 2rb +b b = b(2qb + b) + 2rb = b(a 2) + 2rb = ab 2(b rb) On the other side, e = 2bqb + 2rb +b b = 2aqa + 2ra +a a (b rb)(2qb + b) +rb(2qb + b + 2) = 2aqa + 2(a 1) +a a (b rb)(a 2) +arb = a(2qa + a + 2) 2 (b rb)(a 2) +arb = a(rb + 1) 2 (b rb)(a 2) +arb = arb +a 2 (b rb)(a 2) = a 2 (b rb 1)(a 2) = 0 We know a> 3, b = rb + 1, which means e = ab 2(b rb) = ab 2, which is the bipartite complement of the exception e = 2. So we proved rb6= 1 or a ra6= 1. This completes the proof. 30 Chapter 4 Results 4.1 Complete Multipartite Graphs 4.1.1 Complete Tripartite Graph Theorem 4.1. For a complete tripartite graph K(A;B;C) withjAj= a,jBj= b andjCj= c, assume a>b>c, then the NASCs are: 1. 2j(ab+ac+bc) 2. ab6ac+bc A BC Figure 4.1: K(A;B;C) Necessity: Proof. 2j(ab+ac+bc) comes from the fact that the total number of edges must be divisible by 2 since there are two edges in P3. For ab6ac+bc: We have three kinds of paths, let x; y; z be the number of the paths C ! A ! B, A!B!C and A!C!B respectively, then 31 x+y = ac x+y = ab y +z = bc So x = 12(ac+ab bc))bc6ac+ab y = 12(ab+bc ac))ac6ab+bc z = 12(ac+bc ab))ab6ac+cb So if we have ab6ac+cb, the other two follow easily since a>b>c. Su ciency: Proof. Let A; B; C be sets of size a; b; c respectively. Assume the necessary conditions are satis ed, then we can nd proper x; y; z. Find subgraphs S1 of K(C;A) and S2 of K(A;B) with x edges, as in Lemma 3.4, so that their degrees agree on A (thus S1[S2 is a union of x gregarious paths). Do the same for y paths in K(A;B)[K(B;C) and z paths in K(A;C)[K(C;B). Now we take the union of these three collections of paths, taking care to rename vertices as in Lemma 3.3. Thus the resulting graph will be the required complete tripartite graph. 4.2 Star Multipartite Graphs De nition 4.2. A star is a tree consisting of one vertex (called the root) adjacent to the all others. So a star multipartite graph S = (A;B1;B2;:::;Bn) has jAj = a non-adjacent 32 vertices in the root which are adjacent to all the other sets of vertices (B1;B2;:::;Bn) where jBij= bi for any i. Theorem 4.3. Let S = (A;B1;B2;:::;Bn) be a star multipartite graph and assume b1 >b2 > >bn. The NASCs are: 1. 2j(b1 +b2 + +bn) 2. b1 6b2 +b3 + +bn A B1 B2 ? ? ? ? ? ? Bn Figure 4.2: Multipartite Star S(A;B1;B2;:::;Bn) Necessity: Proof. Let v be a vertex in A. So all the gregarious paths passing through v have both ends in B1[B2[ [Bn. So 2j(b1 + b2 + + bn). For the second condition, the number of the vertices in any bi should be less than the number of remaining vertices, because if you x a vertex, say v in a, then the gregarious paths passing through v gives a one-to-one matching in between vertices. So the number of vertices in any part, bi, should be less than the sum of the number of vertices in the remaining parts. So for any 1 6 i 6 n, bi 6b2 + +bi 1 +bi+1 + +bn. Therefore, if b1 6b2 +b3 + +bn is true, then for any 1 6i6n, bi 6b2 + +bi 1 +bi+1 + +bn is also true since b1 >b2 > >bn. Su ciency: 33 Proof. First, take any vertexv ina, then nd the gregarious decomposition of (v; b1; b2; :::; bn). Afterwards, we put the copies of this decomposition on the remaining vertices in A (every vertex in a has the same degree). To nd the gregarious decomposition of (v; b1; b2; :::; bn): 1. take a P3 between the rst (biggest) two parts. 2. reorder (b1 1; b2 1; :::; bn) so it is non-increasing. 3. repeat steps 1 and 2 until there are no edges left. Now we need to prove that in each step the graph we get still satis es the necessary conditions. The proof of the rst condition is easy since we start with an even number of vertices and in each step we just remove two vertices, so in the next step we should still have an even number of vertices. Now we need prove that in each step we preserve the second condition. We will use induction. Assume that in the kth step we have (b(k)1 ; b(k)2 ;:::;b(k)n ). For k = 1 the second condition holds since (b(1)1 ; b(1)2 ;:::;b(1)n ) = (b1;b2;:::;bn) and for any 1 6i6n, bi 6b2 + +bi 1 +bi+1 + +bn . To use induction, assume the condition holds for k: for any 1 6i6n, b(k)i 6b(k)2 + +b(k)i 1 +b(k)i+1 + +b(k)n . So, we need to prove it holds for k + 1: for any 1 6i6n, b(k+1)i 6b(k+1)2 + +b(k+1)i 1 +b(k+1)i+1 + +b(k+1)n Fix i, 1 6i6n. Case 1: b(k+1)i = b(k)i 1: If we remove one vertex from bki , there exists an m with 1 6m6n such that b(k+1)m = bkm 1. In addition, b(k+1)j = bkj for any j except j = m; i. So, b(k+1)i = b(k)i 1 6 b(k)1 + +b(k)m 1 + +b(k)n 6 b(k+1)1 + +b(k+1)m + +b(k+1)n 34 Case 2: b(k+1)i = b(k)i : Since we removed two vertices in each step, there exist b(k)p and b(k)q such that b(k)p >b(k)q >b(k)i . If b(k)i > 2, then b(k+1)i = 2 6b(k+1)p +b(k+1)q + . If b(k)i = 1 and b(k)p = b(k)q = 1, then we should have at least one more b(k)w = 1 since we have an even number of vertices in each step. So b(k+1)i = 1 6 b(k+1)p +b(k+1)q +b(k+1)w + 6 b(k)p 1 +b(k)q 1 +b(k)w + 6 1 1 + 1 1 + 1 + 6 1 + Note that the following are equivalent: 1. There is a gregarious P3 decomposition of S(A;B1;B2;:::;Bn). 2. There is a loopless multigraph with degree sequence (b1;b2;:::;bn). 3. The complete multigraph K(B1;B2;:::;Bn) has a perfect matching. 4.3 Cycle Multipartite Graphs 4.3.1 Even Cycles Theorem 4.4. For an even cycle multipartite graph C(B1;:::;B2n), the NASCs are: 1. b1b2 +b3b4 + +b2n 1b2n = b2b3 +b4b5 + +b2nb1 2. for any 1 6i6 2n, bibi+1 6bi 1bi +bi+1bi+2 35 C2n B1 B2 B3 B4B2n?1 B2n ? ? ? Figure 4.3: Multipartite Even Cycle C2n Necessity: Proof. For any 1 6i6 2n let xi be the number of gregarious paths that have their middle vertex in Bi. Then, x1 +x2 = b1b2 x2 +x3 = b2b3 ... x2n 1 +x2n = b2n 1b2n x2n +x1 = b2nb1 If we add the rst, third, fth, ..., and (2n 1)th equations, we get, x1 +x2 + +x2n = b1b2 +b3b4 + +b2n 1b2n 36 and if we add the second, fourth, sixth, ..., and (2n)th equations and rearrange the xi?s, we get: x1 +x2 + +x2n = b2b3 +b4b5 + +b2nb1 So these two equations give the rst condition. For the second condition, let x1 = x and x> 0, then: x2 = b1b2 x x3 = b2b3 x2 x4 = b3b4 x3 ... x2n = b2n 1b2n x2n 1 and if we get all equations in terms of x, x2 = b1b2 x x3 = b2b3 b1b2 +x x4 = b3b4 b2b3 +b1b2 x ... x2n = b2n 1b2n b2n 2b2n 1 + +x If we use x> 0 and the equations we have above, then we get: bibi+1 6bi 1bi +bi+1bi+2 for any 1 6i6 2n. Su ciency: 37 Proof. If the necessary conditions are satis ed, we can nd all the xi?s for 1 6i6 2n, then we use the same technique that we used in the proof of Theorem 4.1 to nd gregarious a P3 decomposition. 4.3.2 Odd Cycles Theorem 4.5. For an odd cycle multipartite graph C(B1;:::;B2n+1), the NASCs are: 1. 2j i=2nX i=1 bibi+1 (# of the edges) 2. for any 1 6i6 2n+ 1, bibi+1 6bi 1bi +bi+1bi+2 3. for any 1 6i6 2n+ 1, bi+1bi+2 + bi+3bi+4 + + bi+2n 2b(i+1)+2n 2 6 bibi+1 + bi+2bi+3 + + bi+2nb(i+1)+2n where the subscripts of the b?s are taken (mod 2n+ 1). C2n+1 B0 B1 Bi?1 BiBi+1 Bi+2 B2n ??? ??? Figure 4.4: Multipartite Odd Cycle C2n+1 Necessity: Proof. The rst condition comes from the fact that the total number of edges is divisible by 2. To get the second condition, for any 1 6 i 6 2n + 1 let xi be the number of gregarious 38 paths that have their middle vertex in Bi . Then x1 +x2 = b1b2 x2 +x3 = b2b3 ... x2n +x2n+1 = b2nb2n+1 x2n+1 +x1 = b2n+1b1 To nd x1; (+)x1 +x2 = b1b2 ( )x2 +x3 = b2b3 ... ( )x2n +x2n+1 = b2nb2n+1 (+)x2n+1 +x1 = b2n+1b1 then we get x1 = b1b2 b2b3 +b3b4 b2nb2n+1 +b2n+1b12 = b1b2 +b3b4 + +b2n+1b1 (b2b3 + +b2nb2n+1)2 Using the same technique we can get all the xi?s along with condition 3 since each xi > 0. Condition 2 is the same as the even cycle case. Su ciency: Proof. After nding xi, constructing the gregarious P3 decomposition is the same as for the even cycle case. 39 4.4 Path Multipartite Graphs Theorem 4.6. For a path multipartite graph P(B1;B2;:::;Bn), the NASCs are: 1. b3 >b1 and bn 2 >bn 2. b1b2 +b3b4 +bk 1bk = b2b3 +b4b5 + +bl 1bl 3. for any 2 6i6n 2, bibi+1 6bi 1bi +bi+1bi+2 where k is the largest even number such that k 6 n and l is the largest odd number such that l6n. Pn ? ? ?B1 B2 B3 Bn?2 Bn?1 Bn Figure 4.5: Multipartite Path Pn 40 Necessity: Proof. For any 2 6i6n 1 let xi be the number of gregarious paths that have the middle vertex in Bi . x2 = b1b2 x2 +x3 = b2b3 x3 +x4 = b3b4 ... xn 2 +xn 1 = bn 2bn 1 xn 1 = bn 1bn The rst condition comes from the fact that x3 = b2b3 x2 = b2b3 b1b2 = b2(b3 b1). So we get b3 >b1 since x2 > 0. We can get bn >bn 2 in the same way. We can nd the remaining xi?s easily. If we add the rst, third, fth,... , and (k 1)th equations, we get, x2 +x3 +xn 1 = b1b2 +b3b4 + +bk 1bk and if we add the second, fourth, sixth,... , and (l 1)th equations, we get: x2 +x3 + +xn 1 = b2b3 +b4b5 + +bl 1bl So these two equations give the second condition. The third condition is the same as the condition in the cycle case. 41 Su ciency: Proof. If the necessary conditions are satis ed, we can nd all the xi?s for 2 6 i 6 n 1, then we use the same technique that we used in the proof of Theorem 4.1 to nd gregarious a P3 decomposition. 4.5 Some Tree Multipartite Graphs De nition 4.7. Let T(C1;:::Cm;A1;A2;B1;:::;Bn) be a multipartite graph such that two multipartite stars S(A1;C1;:::;Cm) and S(A2;B1;:::;Bn) are attached to each other via putting a complete bipartite graph on bipartition (A1;A2). See gure 4.6. C1 C2 Cm A1 A2 B1 B2 Bn Figure 4.6: T(C1;:::Cm;A1;A2;B1;:::;Bn) De nition 4.8. De neT(A1;A2;A3;B1;:::;Bn) by using de nition 4.7 asT(A1;A2;A3;B1;:::;Bn). See gure 4.7. 42 ... A1 A2 A3 B1 B2 Bn Figure 4.7: T(A1;A2;A3;B1;:::;Bn) Lemma 4.9. Let G = (E;V) be a graph. There is an orientation of G such that for all v2V, jout(v) in(v)j6 1. Proof. We can assume that G is connected. Case 1: If all vertices have even degree, then there exists an Euler trail, we can orient the graph this way. Case 2: If G has some vertices with odd degree, make an extra vertex u and connect all those vertices to u, then nd an Euler trail on G[fug and remove the edges at the end. For all v2V, we still have jout(v) in(v)j6 1 since we remove one edge from each vertex with odd degree . G odd u Figure 4.8: Orientation of G 43 Theorem 4.10. [14] Let A;B;I be nite non-empty sets, let f : B I!N be such that for all t2B, Pi2I f(t;i) = jAj. Then the edges of K(A;B) can be partitioned into spanning subgraphs Gi, i2I, such that for each i2I, Gi is balanced on A, and for each t2B, the degree of t in Gi is f(t;i). Proof. If jAj= 1, then the proof is trivial. Now suppose jAj= 2. Let A =fs1;s2g. Form a graph H on vertex set I as follows: For each t2B, H has an edge et: If f(t;i) = 2, (and so f(t;j) = 0 for all other j2I) then et is a loop at vertex i of H. If f(t;i) = 1 = f(t;j), i6= j, (f(t;k) = 0 for the other k2I), then et joins the vertices i and j in H. Orient H so that at each vertex of H the indegree and outdegree di er by at most 1 using Lemma 4.9. For each t2B, if et is directed from i to j in the oriented H, place the edge between t and s1 in Gi, and the edge between t and s2 in Gj (see example 4.11). If jAj > 3, then partition the edges of K(A;B) into spanning subgraphs Gi whose degrees on B are given by f (this is certainly possible by the sum condition on f). If everything is balanced onjAj, then we are done. Otherwise degrees in some Gi di er by 2 or more. Fix i, and let s1;s2 be two vertices in A, whose degrees di er by 2 or more in Gi. So use the previous case where jAj= 2 on this graph to nd the balanced distribution. Using this method repeatedly for each unbalanced pair of vertices of Gi in A, nally we can get the balanced distribution on A. Afterwards, we can repeat the same process for the other Gj for each j2I. Now we need to prove that this process will stop after nitely many steps. Let V1 = (a1;:::;ai;:::;aj;:::;an) be a integer vector with xed sum Pai = a. So the shortest integer vector with respect to the Euclidean metric with the xed sum of the entries is the balanced one. To see this assume aj >ai + 2, then if we balance ai and aj, we get 44 V2 = (a1;:::;ai + 1;:::;aj 1;:::;an) and jV2j2 6jV1j2 2 since, jV2j2 = a21 + + (ai + 1)2 + + (aj 1)2 + +a2n = a21 + +a2i + 2ai + 1 + +a2j 2aj + 1 + +a2n = (a21 + +a2i + +a2j + +a2n) + 2(ai aj) + 2 = jV1j2 + 2(ai aj) + 2 6 jV1j2 + 2( 2) + 2 6 jV1j2 2 This means that when we balance a pair of entries in the vector at a time, the vector gets shorter, and after nitely many steps we will nd the shortest one. This completes the proof. Example 4.11. Let G be a bipartite graph on bipartition (A;B) where A = fs1;s2g and B =fv1;v2;v3;v4g. Let I =fgreen, blue, redg. We want to get green and blue balanced on A without changing the color census on B (see the rst picture in Figure 4.9). Then using the method de ned in Theorem 4.10 build a graph H (see the second picture in Figure 4.9) and orient H so that jin(w) out(w)j6 1 for every vertex w in H. Finally, we can swap edges of G with respect to the orientation on H to get a balanced coloring on A. 45 s1 s2 v1 v2 v3 v4 G v2 v4 v1 v3 H v2 v4 v1 v3 Oriented H s1 s2 v1 v2 v3 v4 Colors are balanced on A Figure 4.9: An Example for Theorem 4.10 4.5.1 Necessary And Su cient Conditions for T(A1;A2;A3;B1;:::;Bn) Theorem 4.12. For a graph T(A1;A2;A3;B1;:::;Bn) assume bn 6 6 b2 6 b1, the NASCs are: 1. 2j[a2(a1 +a3) +a3(b1 +b2 + +bn)] 2. a1 6a3 3. a1a2 +b1a3 6a3(a2 +b2 +b3 + +bn) 4. a2a3 6a1a2 +a3(b1 +b2 + +bn) 5. If a2 + (b1 + +bn) is even, then a1a2 is even. a2 + (b1 + +bn) is odd, then a1a2 a3 is even and non-negative. 46 Necessity: Proof. Let G = T(A1;A2;A3;B1;:::;Bn). Condition 1 comes from the fact that the number of edges is even. We can get conditions 2 - 4 using Tutte?s f-factor Theorem on L(G). L(G) is union of a complete graph on n + 1 vertices and an edge attached at the vertex A2A3. If we check all the possible L(G) triples B = (S;T;U) where T is independent and (T;U) = 0 from theorem 2.12, all will reduce to the the following three cases in gure 4.10. We need to check k(B;h) + h(T) 6 h(S) for each case. From the rst picture in the gure 4.10, we will get a2a3 6 a1a2 which gives condition 2. From the second picture, we get a1a2 +b1a3 6a2a3 +b2a3 + +bna3 which gives condition 3. From the last picture, we get a2a3 6a1a2 +a3b1 +a3b2 + +a3bn which gives condition 4. S T U a1a2 a2a3 S T U a1a2 b1a3 a2a3 b2a3 bna3 S T U a1a2 b1a3 a2a3b2a3 bna3 Figure 4.10: How to get conditions 2 - 4 For condition 5, we need to consider all the types of paths we have and the degree of any vertex in A3. Firstly, the degree of any vertex v in A3 is deg(v) = a2 +b1 + +bn. Let x1 be the number of paths passing through the sets of vertices A1 !A2 !A3 so x1 = a1a2. In the same way, yi : A2 ! A3 ! Bi for any 1 6 i 6 n, and wij : Bi ! A3 ! Bj for any 1 6 i 6 j 6 n. Here, both yi and wij have their middle vertices in A3, so if deg(v) is even, then x1 must be even. If deg(v) is odd, then we should have enough x1 type paths which means a1a2 > a3. That gives a1a2 a3 non-negative. To see that a1a2 a3 is even, consider the vertices in A3 and distribution of a1a2 edges on A3. There are i?s for 47 1 6 i 6 a3 such that a3X i=1 i = a1a2 where each i = 2 i + 1, an odd number. i = i 12 . a3X i=1 i = a3X i=1 i 1 2 = 1 2(a1a2 a3). Therefore a1a2 a3 is an even number. Su ciency: Proof. If the necessary conditions are satis ed we can nd proper x1, yi?s and wij?s. In between pairs of sets (A1;A2) and (A3;Bi) for any i, we can nd balanced edge distributions with the required numbers as we did for the su ciency case of the Theorem 4.1. The only problem is nding a construction for (A2;A3) since we need to nd a parity balanced distribution of x1 edges on A3 with respect to the parity of a2 + (b1 + +bn) (see condition 5 in Theorem 4.12). We also need to nd a balanced distribution for the remaining yi?s. To be able to nd this special distribution we can use theorem 4.10 and choose the degrees on A3 to get balanced degrees on A2. 4.5.2 Necessary And Su cient Conditions for T(C1;:::;Cm;A1;A2;B1;:::;Bn) Theorem 4.13. For a graph T(C1;:::;Cm;A1;A2;B1;:::;Bn) assume cm 6 6 c2 6 c1 and bn 6 6b2 6b1, and let C = C1[C2[ [Cm and jCj= c, B = B1[B2[ [Bn, jBj= b and d1 = c+a2, d2 = b+a1. The NASCs are: 1. 2j[a1(c1 +c2 + +cm) +a1a2 +a2(b1 +b2 + +bn)] 2. c1 6a2 + (c2 + +cm) and b1 6a1 + (b2 + +bn) 3. a1c1 +a2b1 6a1(c2 + +cm) +a1a2 +a2(b2 + +bn) 4. a1a2 6a1(c1 +c2 + +cm) +a2(b1 +b2 + +bn) 5. If d1 and d2 are even, then a1a2 is even. 48 d1 is even and d2 is odd, then either both a1 and a2 are odd, both even or a1 is odd and a2 even. In addition, ca1 a2 > 0. d1 is odd and d2 is even, then either both a1 and a2 are odd, both even or a1 is even and a2 odd. In addition, ba2 a1 > 0. d1 and d2 are odd, then both a1 and a2 are even. In addition, ca1 a2 > 0 and ba2 a1 > 0. with the following exceptions: d1 d2 a1 a2 c1 & b1 even even 2 2 any c1 with 1 + (b2 + +bn) 6b1 6 2 + (b2 + +bn) even 1 any c1 with 1 + (b2 + +bn) 6b1 6a1 + (b2 + +bn) 1 even any b1 with 1 + (c2 + +cm) 6c1 6a2 + (c2 + +cm) even odd odd 1 any c1 with 1 + (b2 + +bn) 6b1 6a1 + (b2 + +bn) 1 even any c1 with b1 = 1 + (b2 + +bn) odd even 1 odd any b1 with 1 + (c2 + +cm) 6c1 6a2 + (c2 + +cm) even 1 any b1 with c1 = 1 + (c2 + +cm) Table 4.1: Exceptions for Theorem 4.13 Necessity: Proof. Let G = T(C1;:::;Cm;A1;A2;B1;:::;Bn). Condition 1 comes from the fact that the number of edges is even. We can get conditions 2 - 4 using Tutte?s f-factor Theorem on L(G). L(G) is union of two complete graphs on m and n vertices attached at the vertex A1A2. If we check all the possible L(G) triples B = (S;T;U) where T is independent and (T;U) = 0 from theorem 2.12, all will reduce to the the following three cases in gure 4.11. We need to check k(B;h) + h(T) 6 h(S) for each case. From the rst picture in the gure 4.11, we will get c1 6a2 + (c2 + +cm) and in the same picture if we replace B?s with C?s 49 and C?s with B?s then we get b1 6 a1 + (b2 + + bn) which gives condition 2. From the second picture, we get a1c1 +a2b1 6a1(c2 + +cm) +a1a2 +a2(b2 + +bn) which gives condition 3. From the last picture, we get a1a2 6a1(c1 +c2 + +cm)+a2(b1 +b2 + +bn) which gives condition 4. S TA1C2 A1A2 A1C1A1C3 U A2B1 A2Bn S T U A1C2 A1C1 A2B1 A2Bn A1A2 S T U A1C1 A1Cm A2B1 A2Bn A1A2 Figure 4.11: How to get conditions 2 - 4 For condition 5, we need to consider all the types of paths we have and the degree of any vertex in A1 and A2 . Firstly, the degree of any vertex v1 in A1 is: d1 = deg(v1) = a2 +c1 + +cm = a2 +c and the degree of any vertex v2 in A2 is: d2 = deg(v2) = a1 +b1 + +bn = a1 +b. Let xi be the number of paths passing through the sets of vertices Ci !A1 !A2 for any 1 6 i 6 m and let x = Pmi=1xi. In the same way, yj : Bj !A2 !A1 for any 1 6 j 6 n and y = Pnj=1yj. So x + y = a1a2. In addition, we have wij : Ci ! A1 ! Cj for any 1 6i6j 6m and zkl : Bk !A2!Bl for any 1 6k 6l6n. Here wij?s have their middle vertex in A1 and zkl?s have their middle vertex in A2, so we have four cases with respect to the parity of d1 and d2. So the parity of x and d2, and y and x1 must be consistent (see gure 4.12). 50 A1 A2 wij xi yj zkl C B Figure 4.12: Types of paths Case 1: If d1 and d2 are even, then y and x are even so a1a2 is even since x+y = a1a2. Case 2: If d1 is even and d2 is odd, then y is even and x a2 (mod 2) and x>a2. So we can get ca1 a2 > 0 since ca1 >x. To get either both a1 and a2 odd, both even or or a1 is odd and a2 even, see: x+y = a1a2 x+y a1a2 (mod 2) x a1a2 (mod 2) since y is even Case 3: If d1 is odd and d2 is even, then this is the same as case 2, just replace a2 with a1. Case 4: If d1 is odd and d2 is odd, then y a1 (mod 2) and y > a1, and x a2 (mod 2) and x>a2. We can get ca1 a2 > 0 and ba2 a1 > 0 in the same way as in case 2. To get both a1 and a2 even, see: x+y = a1a2 x+y a1a2 (mod 2) a1 +a2 a1a2 (mod 2) since x a2 (mod 2) and y a1 (mod 2) 51 a1 +a2 a1a2 (mod 2) is only satis ed when both a1 and a2 are even. Note that theorem 4.12 is a special case of theorem 4.13. In theorem 4.13, if we get c2 = c3 = = cm = 0 and replace c1 with a1, a1 with a2 and a2 with a3 we will get exactly the same conditions as in theorem 4.12. Su ciency: Proof. If the necessary conditions are satis ed we can nd proper xi?s, yj?s, wij?s and vkl?s. First we nd a proper x and y then we will nd wij?s and vkl?s since we have more restriction on x and y. In between pairs of sets (Ci;A1) for any 1 6 i 6 m, and (A2;Bj) for any 1 6j 6n, we can nd balanced edge distributions with the required numbers as we did for the su ciency case of theorem 4.1. The only problem is nding a construction for (A1;A2) since we need to nd a parity balanced distribution of x+y edges on A1 and A2 with respect to the parity of d1 and d2 (see condition 5 in theorem 4.13). To nd this parity balanced distribution, we will use theorem 3.12. Case 1: Assume d1 and d2 are even, then y and x are even so a1a2 is even since x+y = a1a2. So there are three cases for (a1;a2): (even, even), (even, odd) and (odd, even). If a1 and a2 are both even, then we need to nd a parity balanced bipartite graph (PBBG) with pararameters (a = a1;b = a2;e = x; a = 0; b = 0) with bipartite complement (a = a1;b = a2;e = ab x = y; 0a = 0; 0b = 0) so that the distribution of x on A2 has even parity ( b = 0) and the distribution of y on A1 has even parity ( 0a = 0). We can we can nd such a PBBG since the necessary conditions of theorem 3.12 are satis ed. a + 0a = 0 + 0 = 0 b (mod 2) and b + 0b = 0 + 0 = 0 a (mod 2) aa 6 e6ab 0aa)0 6x6a1a2 bb 6 e6ab 0bb)0 6x6a1a2 aa ab 0aa e = x bb ab 0bb 0 (mod 2) 52 For the exceptions in table 4.1 the only problem concerning this case is when a = a1 =even, b = a2 = even, e = x = 2, a = 0, 0a = 0, b = 0, 0b = 0. We can solve this problem by choosing x > 4 since a1 > 2 and a2 > 2 in the exceptions. In the case of a1 = 2 = a2, we will not have any y?s which means we need to put a gregarious P3 decomposition of star multipartite graph on S = (A2;B2;B2;:::;Bn). The rst condition of theorem 4.3 is satis ed since 2jb = b1 +b2 +:::+bn (d1 =even= a1 +b and a1 is even so b is even). For the second condition of theorem 4.3, we can get b1 6 2+b2 +:::+bn from condtion 2 of theorem 4.13. From here we get two exceptions: b1 = 1 + b2 + + bn and b1 = 2 + b2 + + bn. So T(C1;:::Cm; 2;2;B1;:::;Bn) doesn?t exist when either b1 = 1 + b2 + + bn or b1 = 2 +b2 + +bn. If a1 is even and a2 is odd, then we need to nd a PBBG with pararameters (a = a1;b = a2;e = x; a = 1; b = 0) with bipartite complement (a = a1;b = a2;e = ab x = y; 0a = 0; 0b = 0) so that the distribution of x edges on a2 has even parity ( b = 0) and the distribution of y edges on a1 has even parity( 0a = 0). We can we can nd such a PBBG since the necessary conditions of theorem 3.12 are satis ed. a + 0a = 1 + 0 = 1 b (mod 2) and b + 0b = 0 + 0 = 0 a (mod 2) aa 6 e6ab 0aa)a1 6x6a1a2 bb 6 e6ab 0bb)0 6x6a1a2 aa ab 0aa e = x bb ab 0bb 0 (mod 2) If we check the exceptions in table 4.1, then we see (a = even> 4;b = odd> 3;e = 2; a = 1; 0a = 0; b = 0; 0b = 0). However, in this case e = x>a1 and a1 > 4 so we don?t have any exception for e = 2. There are other exceptions coming from x>a1. If a2 = 1, then we don?t have any y?s which means we need to put a gregarious P3 decomposition of a star multipartite graph on S = (A2 = 1;B2;B2;:::;Bn). The rst condition of theorem 4.3 is satis ed since 2 jb = b1 + b2 + ::: + bn (d2 =even= a1 + b and a1 is even so b is even). For the second 53 condition of theorem 4.3, we can get b1 6 a1 + (b2 + ::: + bn) from condition 2 of theorem 4.13. From here we get exceptions when 1 + (b2 + + bn) 6 b1 6 a1 + (b2 + + bn). So T(C1;:::Cm;A1;1;B1;:::;Bn) doesn?t exist when 1+(b2+ +bn) 6b1 6a1+(b2+ +bn). If a1 is odd and a2 is even, then this case is the same as the previous case, just switch a2 with a1. Case 2: If d1 is even and d2 is odd, then y is even and x a2 (mod 2) and x > a2. So there are three cases for (a1;a2): (even, even), (odd, odd) and (odd, even). If a1 and a2 are both even, then x and y are both even. We need to nd a PBBG with parameters (a = a1;b = a2;e = x; a = 0; b = 1) with bipartite complement (a = a1;b = a2;e = a1a2 x = y; 0a = 0; 0b = 1) so that the distribution of x on A2 has odd parity ( b = 1) and the distribution of y on A1 has even parity ( 0a = 0). We can we can nd such a PBBG since the necessary conditions of theorem 3.12 are satis ed. a + 0a = 0 + 0 = 0 b (mod 2) and b + 0b = 1 + 1 = 0 a (mod 2) aa 6 e6ab 0aa)0 6x6a1a2 bb 6 e6ab 0bb)a2 6x6a1a2 a2 aa ab 0aa e = x bb ab 0bb 0 (mod 2) If we check the exceptions in table 4.1, we see that we don?t have any exception for this case. If a1 and a2 are both odd, then x is odd and y is even. We need to nd a PBBG with parameters (a = a1;b = a2;e = x; a = 1; b = 1) with bipartite complement (a = a1;b = a2;e = a1a2 x = y; 0a = 0; 0b = 0) so that the distribution of x on A2 has odd parity ( b = 1) and the distribution of y on A1 has even parity ( 0a = 0). We can we can nd such 54 a PBBG since the necessary conditions of theorem 3.12 are satis ed. a + 0a = 0 + 1 = 1 b (mod 2) and b + 0b = 1 + 0 = 1 a (mod 2) aa 6 e6ab 0aa)a1 6x6a1a2 bb 6 e6ab 0bb)a2 6x6a1a2 aa ab 0aa e = x bb ab 0bb 1 (mod 2) If we check the exceptions in table 4.1, then we see (a = odd > 3;b = odd > 3;e = 2; a = 1; 0a = 0; b = 1; 0b = 0). However, in this case e = x > maxfa1;a2g and a1;a2 > 3 so we don?t have any exception fore = 2. There are other exceptions coming fromx>maxfa1;a2g. If a2 = 1, then x = a1 = a1a2 so we don?t have any y?s which means we need to put a gregarious P3 decomposition of a star multipartite graph on S = (A2 = 1;B2;B2;:::;Bn). The rst condition of theorem 4.3 is satis ed since 2 jb = b1 + b2 + ::: + bn (d2 =odd= a1 + b and a1 is odd so b is even). For the second condition of theorem 4.3, we can get b1 6a1 +(b2 +:::+bn) from condition 2 of theorem 4.13. From here we get exceptions when 1 + (b2 + + bn) 6 b1 6 a1 + (b2 + + bn). So T(C1;:::Cm;A1;1;B1;:::;Bn) doesn?t exist when 1 + (b2 + +bn) 6b1 6a1 + (b2 + +bn). If a1 is odd and a2 is even, then x and y are both even. We need to nd a PBBG with parameters (a = a1;b = a2;e = x; a = 0; b = 1) with bipartite complement (a = a1;b = a2;e = a1a2 x = y; 0a = 0; 0b = 0) so that the distribution of x on A2 has odd parity ( b = 1) and the distribution of y on A1 has even parity ( 0a = 0). We can we can nd such a PBBG since the necessary conditions of theorem 3.12 are satis ed. a + 0a = 0 + 0 = 0 b (mod 2) and b + 0b = 1 + 0 = 1 a (mod 2) aa 6 e6ab 0aa)0 6x6a1a2 bb 6 e6ab 0bb)a2 6x6a1a2 aa ab 0aa e = x bb ab 0bb 0 (mod 2) 55 If we check the exceptions in table 4.1, then we see (a = odd > 3;b = even > 3;e = 2; a = 0; 0a = 0; b = 1; 0b = 0). However, in this case e = x > a2 and a2 > 4 so we don?t have any exception for e = 2. There is an exception coming from x > a2. If a1 = 1, then x = a2 = a1a2 so we don?t have any y?s which means we need to put a gregarious P3 decomposition of a star multipartite graph on S = (A2;B2;B2;:::;Bn). The rst condition of theorem 4.3 is satis ed since 2jb = b1 +b2 +:::+bn (d2 =odd= a1 +b and a1 is odd so b is even). For the second condition of theorem 4.3, we can get b1 6a1 + (b2 +:::+bn) from condition 2 of theorem 4.13. From here we get exceptions when b1 = 1 + (b2 + +bn). So T(C1;:::Cm; 1;A2;B1;:::;Bn) doesn?t exist when b1 = 1 + (b2 + +bn). Case 3: If d1 is odd and d2 is even, then this case is the same as case 2, just switch a1 and a2. Case 4: If d1 and d2 are both odd, then x;y;a1;a2 are even and y > a1, x > a2. We need to nd a PBBG with parameters (a = a1;b = a2;e = x; a = 1; b = 1) with bipartite complement (a = a1;b = a2;e = a1a2 x = y; 0a = 1; 0b = 1) so that the distribution of x on A2 has odd parity ( b = 1) and the distribution of y on A1 has odd parity too ( 0a = 1). We can we can nd such a PBBG since the necessary conditions of theorem 3.12 are satis ed. a + 0a = 1 + 1 = 0 b (mod 2) and b + 0b = 1 + 1 = 0 a (mod 2) aa 6 e6ab 0aa)a1 6x6a1a2 a1 bb 6 e6ab 0bb)a2 6x6a1a2 a2 aa ab 0aa e = x bb ab 0bb 0 (mod 2) If we check the exceptions in table 4.1, we see that we don?t have any exception for this case. 56 Bibliography [1] D.G Ho man, Cores of Class II Graphs, Journal of Graph Theory, Vol. 20, No. 3, 397-402 (1995) [2] Douglas B. West, Introduction to Graph Theory, Prentice Hall 2001. [3] Elizabeth J. Billington, Dean G. Ho man, Short path decompositions of arbitrary com- plete multipartite graphs, Proc. of the 38th Southeastern Int. Conf. on Comb., Graph Theo. and Comp., Congr. Numer. 187 (2007), 161 - 173. [4] W.T. Tutte, Graph Factors, Combinatorica 1 (1981) 79-97 [5] Billington, Elizabeth J. ; Ho man, D. G. , Decomposition of complete tripartite graphs into gregarious 4-cycles. Papers on the occasion of the 65th birthday of Alex Rosa. Discrete Math. 261 (2003), no. 1-3, 87{111. [6] Billington, Elizabeth J. ; Ho man, D. G. , Equipartite and almost-equipartite gregarious 4-cycle systems. Discrete Math. 308 (2008), no. 5-6, 696{714. [7] Smith, Benjamin R. , Equipartite gregarious 5-cycle systems and other results. Graphs Combin. 23 (2007), no. 6, 691{711. [8] Billington, Elizabeth J. ; Smith, Benjamin R. ; Ho man, D. G. Equipartite gregarious 6- and 8-cycle systems. Discrete Math. 307 (2007), no. 13, 1659{1667. [9] Cho, Jung R. ; Gould, Ronald J. Decompositions of complete multipartite graphs into gregarious 6-cycles using complete di erences. J. Korean Math. Soc. 45 (2008), no. 6, 1623{1634. [10] Cho, Jung Rae . A note on decomposition of complete equipartite graphs into gregarious 6-cycles. Bull. Korean Math. Soc. 44 (2007), no. 4, 709{719. [11] Smith, Benjamin R. Some gregarious cycle decompositions of complete equipartite graphs. Electron. J. Combin. 16 (2009), no. 1, Research Paper 135, 17 pp. [12] Billington, Elizabeth J. ; Ho man, D. G. ; Rodger, C. A., Resolvable gregarious cycle decompositions of complete equipartite graphs. Discrete Math. 308 (2008), no. 13, 2844{ 2853. [13] El-Zanati, Saad I. ; Punnim, Narong ; Rodger, Chris A. Gregarious GDDs with two associate classes. Graphs Combin. 26 (2010), no. 6, 775{780. [14] Bryant, Darryn; Private Communication 57