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