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