Stars and Hyperstars
by
Dan Roberts
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 4, 2012
Keywords: graph decompositions, stars, maximum packings, embeddings
Copyright 2012 by Dan Roberts
Approved by
Dean Ho man, Professor of Mathematics and Statistics
Curt Lindner, Distinguished University Professor of Mathematics and Statistics
Peter Johnson, Professor of Mathematics and Statistics
George Flowers, Dean of the Graduate School and Professor of Mechanical Engineering
Abstract
A k-star is a complete bipartite graph K1;k, and a hypergraph G = (X;E) is a hyperstar
with center C if C
\
E2E
E. Given (hyper)graphs G and H, an H-decomposition of G
is a partition of the edges of G into copies of H. In this work, we investigate di erent
decomposition-like properties of stars and hyperstars. We discuss maximum packings of
Kn with k-stars, embeddings of partial k-star decompositions of Kn, and decompositions
of complete hypergraphs and complete uniform hypergraphs into hyperstars with center-size
1.
We characterize the number of edges in a maximum packing of Kn with k-stars for the
cases = 1 for any n, and > 1 for n 2k. For the case where > 1 with n< 2k we give
partial results. Our main result for an embedding of a partial k-star decomposition of Kn is
a small embedding in which the number of new vertices depends only on k. The question of
decomposing both complete hypergraphs and complete uniform hypergraphs into hyperstars
has already been solved by Lonc [9], but we give an alternative proof.
ii
Acknowledgments
I thank my advisor for helping me become both a better mathematician and guitar
player, my family for being very supportive, and the many others who have helped me along
the way.
iii
Table of Contents
Abstract . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ii
Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iii
List of Figures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . v
List of Tables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . vii
1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
2 Packing Kn with k-stars . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
2.1 The case when = 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
2.2 The case when > 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
2.2.1 What to do when > 1 and n 2k . . . . . . . . . . . . . . . . . . . 12
2.2.2 Partial Results for when > 1 and n< 2k . . . . . . . . . . . . . . . 14
3 Embedding Partial k-star Decompositions . . . . . . . . . . . . . . . . . . . . . 19
3.1 A Balanced Embedding . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
3.2 A Small Embedding . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
4 Hyperstar Decompositions of Hypergraphs . . . . . . . . . . . . . . . . . . . . . 37
4.1 What is a hyperstar? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
4.2 Decomposing Complete Uniform Hypergraphs into Hyperstars . . . . . . . . 41
4.3 Decomposing Complete Hypergraphs into Hyperstars . . . . . . . . . . . . . 46
5 Concluding Remarks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52
iv
List of Figures
1.1 A multigraph. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2 A k-star. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.3 A directed edge, or arc. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
2.1 At most one star centered at each vertex. . . . . . . . . . . . . . . . . . . . . . 10
2.2 The di erent types of edges used in stars. . . . . . . . . . . . . . . . . . . . . . 11
2.3 Strategic placement of the leave stars in order to build an edge-balanced multistar. 14
2.4 The number of k-stars centered at each vertex. . . . . . . . . . . . . . . . . . . 15
2.5 How the stars are constructed. . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
2.6 Organizing the leave edges into an edge-balanced multistar. . . . . . . . . . . . 18
3.1 A k-star corresponds to an orientation. . . . . . . . . . . . . . . . . . . . . . . . 19
3.2 Di erent types of edges. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
3.3 The orientation guaranteed by Lemma 3.3. . . . . . . . . . . . . . . . . . . . . . 24
3.4 Extending the orientation of the leave to k-stars. . . . . . . . . . . . . . . . . . 29
3.5 Using almost all edges between Kn and T. . . . . . . . . . . . . . . . . . . . . . 29
3.6 Choosing the set, X, of vertices. . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
v
3.7 A k-star decomposition of the remaining bipartite graph with partition (T,Y). . 35
4.1 A hypergraph. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
4.2 A hyperstar of size 3 with center size 2. . . . . . . . . . . . . . . . . . . . . . . 38
4.3 Determining whether a hyperedge is an element of T(E;C) or not. . . . . . . . . 39
vi
List of Tables
4.1 Categorizing the edges of gure 4.3. . . . . . . . . . . . . . . . . . . . . . . . . . 39
vii
Chapter 1
Introduction
Let N denote the set of non-negative integers f0;1;2;:::g. A graph, G, is a pair
(V(G);E(G)) where V(G) is a set whose elements are called vertices, and E(G) (whose
elements are called edges) is a collection of 1- or 2-element subsets of V(G). The 1-element
subsets included in E(G) are called loops. We call G a multigraph if E(G) is a multiset, i.e.
E(G) contains repeated elements. The standard way to represent a vertex is by a dot, and
edges are represented by curves connecting dots. In gure 1.1 the black edges f1;2g and
f2;3g are 2-elements subsets of the vertex set f1;2;3;4g. The red edge f2g is a loop, and
the blue edge f3;4g is a repeated edge. It is also possible for a vertex not to be included in
any edges, in which case the vertex is called isolated.
1
2 3
4
Figure 1.1: A multigraph.
An edge is said to be incident with all vertices that are endpoints of it. The degree of a
vertex v2G, denoted by dG(v), is the number of edges that are incident with that vertex
(loops count as 2). If it is clear from the context what the graph G is, then we shorten the
notation to d(v).
There are many important classes of graphs. Here are a few that are studied in this work.
The complete graph on n vertices, denoted Kn, is a graph with n vertices such that any pair
1
of distinct vertices are joined by exactly one edge. We can generalize the complete graph by
de ning the -fold complete graph on n vertices, denoted Kn, to be a graph on n vertices
such that any pair of distinct vertices are joined by exactly edges. A bipartite graph is
de ned to be a graph without any cycles of odd length. Notice that a bipartite graph has
the property that its vertices can be partitioned into two sets A and B such that there are
no edges with both endpoints in one set in the partition. The complete bipartite graph with
parts size n and m, denoted Kn;m, is a bipartite graph with bipartition (M;N) withjMj= m
andjNj= n whose edge set is all edges with one end in M and one end in N. The graph that
plays a central role in this work is the k-star, denoted Sk. A k-star is a complete bipartite
graph with one part size 1 and one part size k. In gure 1.2 the blue vertex is called the
center of the star. The other vertices are called pendant.
kvertices
Figure 1.2: A k-star.
An orientation on a graph is an assignment of exactly one direction to each edge of
the graph. This can be represented as an arrow on each edge (see gure 1.3). An edge
that has been oriented is referred to as a directed edge, or sometimes called an arc. For a
given directed edge, the vertex which the arrow is pointing away from is called the tail and
the vertex which the arrow is pointing towards is called the head. A graph in which all of
the edges have been oriented is called a digraph. Similarly to how we de ned the degree
of a vertex, we de ne the outdegree of a vertex v in a digraph G, denoted d+G(v), to be the
2
number of directed edges in G that have tail v. If the graph being referred to is clear from
the context then we shorten the notation to d+(v).
Tail Head
Figure 1.3: A directed edge, or arc.
A structure of central importance to the eld of design theory is called a graph de-
composition. Let G and H be two graphs. We de ne an H-decomposition of G to be a
partition of the edges of G into copies of H. This is sometimes read as \a decomposition of
G into H?s". Graph decompositions have been widely studied for many di erent classes of
graphs. In this work we will be studying problems related to decomposing complete graphs
into k-stars. The problem of decomposing a complete graph into k-stars has been settled
since 1979, and is stated as theorem 1.1. It should be noted that in 1975, Yamomoto et al.
[13] independently published the result for = 1.
Theorem 1.1. (Tarsi [11]) Let n;k; 2N. There is a k-star decomposition of Kn if and
only if
1. n(n 1) 0 (mod 2k)
2. n 2k for = 1
3. n k + 1 for even
4. n k + 1 + k for 3 odd.
After characterizing the complete graphs that can be decomposed into k-stars, we next
ask which complete bipartite graphs have this property. This problem was solved in much
more generality by Ho man and Liatti [7] in 1995. They actually characterized which com-
plete bipartite graphs can be decomposed into a given (smaller) complete bipartite graph.
As a k-star is a complete bipartite graph, their result solves our problem.
3
Theorem 1.2. (D.G. Ho man and Liatti [7]) Let a;b;n;m be positive integers. Let g =
gcd(a;b), e;f be non-negative integers satisfying ae bf = g and let h = ae+bf. For each
integer x, let:
(x) =
xf
a
; (x) =
jxe
b
k
; and (x) = xab:
Then there is a Ka;b-decomposition of Kn;m if and only if the following conditions are true:
abjnm
gjn and (n) (n)
gjm and (m) (m)
n (m) +m (n) h (nm) n (m) +m (n)
The fact that theorem 1.2 can be used to characterize those complete bipartite graphs
which can be decomposed into k-stars is not trivial, and requires proof. This result is
presented as corollary 1.3.
Corollary 1.3. Kn;m has a k-star decomposition if and only if
1. kjmn, and
2. if k>m then kjn and
if k>n then kjm.
Proof. We apply theorem 1.2 with a = 1 and b = k. We get g = 1, which yields that e = 1,
f = 0 and h = 1. So for each integer x we have (x) = 0, (x) = bxkc and (x) = xk. The
conditions are now:
kjnm
1jn and 0
jn
k
k
1jm and 0
jm
k
k
0 nmk n
jm
k
k
+m
jn
k
k
4
The rst condition is the same as condition (1) as stated in the theorem. The middle two
conditions are trivially satis ed, so we need to show the following:
If k>m then kjn; and
if k>n then kjm
()
0 nmk n
jm
k
k
+m
jn
k
k
To show this, we examine the latter inequality. Let n = kp + s where 0 s < k, and
m = kq +r where 0 r 0 so:
If p = 0 then r = 0, and if q = 0 then s = 0, which is another way of saying: If k >m then
kjn, and if k>n then kjm.
Thus far, all of the results deal with decomposing graphs into k-stars. That is, all of
the stars have the same size. A natural generalization is to ask when we can decompose
a graph into stars of di erent sizes. Theorem 1.4 characterizes those complete graphs that
can be decomposed into stars with prescribed sizes m1;m2;:::;m?. This result turns out
to be very useful when we study structures called maximum packings (de ned in chapter
5
2). It is interesting to note that this wasn?t published until 1996, roughly 20 years after the
publication of the solution to the case where all stars have the same size.
Theorem 1.4. (Lin and Shyu [8]) Let m1 m2 m? be nonnegative integers
with n 2m1. Necessary and su cient conditions for Kn to be decomposed into stars
Sm1;Sm2;:::;Sm? are
(i)
?X
i=1
mi =
n
2
and
(ii)
pX
i=1
mi
pX
i=1
(n i) for p = 1;2;:::;n 1.
We now turn to the topic of computational complexity. We are interested in the decision
question: Given a graph G and an integer k> 1, can G be decomposed into k-stars? To this
end, we state the well-known result of Dor and Tarsi [2], published in 1997.
Theorem 1.5. (Dor and Tarsi [2]) Given graphs G and H, deciding whether G has an H-
decomposition is NP-complete whenever H contains a connected component with 3 or more
edges.
Therefore, our problem of deciding whether a given graph G has a k-star decomposition
is NP-complete whenever k 3. However, the complexity can be reduced given a little more
information. To this end, we de ne the central function of a k-star decomposition of a graph
G to be a function c : V(G) !N such that for each v 2V(G), c(v) gives the number of
k-stars centered at the vertex v. Ho man [6] showed that the following decision question
can be decided in polynomial time: Given a graph G and a central function c : V(G)!N,
does G have a k-star decomposition with central function c ?
Given a graph G and a subset S of V(G), let "(S) denote the number of edges with both
ends in S.
Theorem 1.6. (D.G. Ho man [6]) Let k2N, G = (V;E) be a loopless graph, and c : V !
N. Then there is a k-star decomposition of G with central function c if and only if
6
1. k
X
v2G
c(v) = "(G)
2. For all fx;yg2 V2 , (xy) c(x) +c(y)
3. For all S V, k
X
v2S
c(v) "(S) +
X
x2S
y2VnS
min(c(x); (xy))
where V2 denotes the set of 2-element subsets of V, and (xy) denotes the number of edges
with one endpoint x and the other endpoint y.
7
Chapter 2
Packing Kn with k-stars
The problem of decomposing Kn into k-stars has been solved. So if a k-star decom-
position isn?t possible, then how close can we get? This question gives rise to the following
de nition. Given graphs G and H, we de ne an H-packing of G to be a partition of the edges
of G into some copies of H along with a set of edges L, called the leave. An H-packing is
sometimes referred to as a partial H-decomposition. An H-packing is called maximum when
jLj is minimum, or equivalently, if the H-packing contains as many copies of H as possible.
Our main question for this chapter is: Given ;n;k2N how many edges are in the leave
of a maximum packing of Kn with k-stars? In some cases, we will not only answer this
question, but characterize what the leave graph looks like. We break it into two major cases:
= 1 and > 1.
2.1 The case when = 1
Lemma 2.1. Let n;k2N where n 2k. Then there are
j n
2
k
k
stars in a maximum packing
of Kn with k-stars. Moreover, it is possible to have the leave graph be a star of size less than
k.
Proof. We must show that conditions (i) and (ii) hold from Theorem 1.4 with m1 = m2 =
= m? 1 = k and m? = n2 k(? 1) where ? =
j n
2
k
k
+ 1. To verify (i) we see that
?X
i=1
mi =
? 1X
i=1
mi +m? = k(? 1) +
n
2
k(? 1) =
n
2
8
To show (ii) let p2f1;:::;n 1g. First, note that ? n 1. To see this, suppose, to the
contrary, that ? 1
When > 1 we have a higher density of edges to deal with, but we also have considerably
more freedom to center multiple stars at a vertex. While this allows for more creative
constructions, it also complicates the problem of nding a maximum packing. Perhaps that
is why the author nds the rst main result of the section (theorem 2.5) both elegant and
surprising.
2.2.1 What to do when > 1 and n 2k
First we need a de nition. A multistar, denoted S( 1;:::; n), is a star with n pendant
vertices in which there are i edges incident with the ith pendant vertex. A multistar is
called edge-balanced if max
i6=j
j i jj 1. The following lemma will help us to prove theorem
2.5.
Lemma 2.4. If n k then the edge-balanced multistar S( 1;:::; n) has a maximum packing
with k-stars in which the leave is a star of size less than k.
12
Proof. Let S = S( 1;:::; n) be an edge-balanced multistarfv1;:::;vng. The edge-balanced
property implies that there can only be two distinct edge multiplicities. To justify this,
assume that there are three distinct edges multiplicities. So there are three distinct integers
i, j and k such that j < k < ?. But then ? j > 1, contradicting our assumption. Thus,
there are only two values for the edges multiplicities, and they must be exactly one apart. So
for each 1 i n, i2f ; +1gfor some 2N. We can assume without loss of generality
that 1 2 n. To obtain the desired decomposition, for 0 t
jjE(S)j
k
k
1
we remove the stars with pendant vertices vtk+1;vtk+2;:::;vtk+k where the subscripts are
considered mod n. This method of removing stars ensures that at each step, what remains
is an edge-balanced multistar. Therefore, after the last star is removed we are left with an
edge-balanced multistar with multiplicities 0 and 1, which is a star of size smaller than k.
Theorem 2.5. Let ;n;k2N with n 2k. Then there are
j n
2
k
k
stars in a maximum
packing of Kn with k-stars. Moreover, it is possible to have the leave graph be a star of size
smaller than k.
Proof. We rst view Kn as di erent copies of Kn, but all on the same vertex set
fv0;v1;:::;vn 1g. Let b =
j n
2
k
k
be the number of stars that are in a maximum pack-
ing of Kn. On each copy of Kn we apply lemma 2.1 with m1 = m2 = = mb = k
and mb+1 = n2 bk to obtain a maximum packing with leave a star of size mb+1. We
denote the leave star in the ith copy of Kn by Si. It is important to note that we have
the freedom to choose the center and pendant vertices of Si in each copy of Kn. To
this end, for each 0 i 1 let Si have central vertex vn 1 and pendant vertices
vimb+1;vimb+1+1;:::;v(i+1)mb+1 1 (note that the subscripts are considered mod n 1). (See
gure 2.3). This ensures that Si+1 begins where Si ends, i.e. that the leave edges are dis-
tributed over the vertices v0;:::;vn 2 as evenly as possible.
So we end up with an edge-balanced multistar centered at vn 1, to which we can apply
lemma 2.4 to obtain a maximum packing of with k-stars. Since the rest of the edges of Kn
are already partitioned into k-stars, the leave of the maximum packing of the edge-balanced
13
S0 S1 S??1
Figure 2.3: Strategic placement of the leave stars in order to build an edge-balanced multi-
star.
multistar is the leave of the maximum packing of Kn. And we know that this leave is a
star of size less than k; thus, we obtain the desired maximum packing.
2.2.2 Partial Results for when > 1 and n< 2k
We will rst take care of the trivial cases with an analog of lemma 2.2.
Lemma 2.6. Let ;n;k2N with n k. Then there are 0 stars in a maximum packing of
Kn with k-stars. Moreover, the leave must be Kn.
Proof. A k-star requires k+1 vertices. Therefore, we have no k-stars in Kn. So a maximum
packing must have leave Kn.
Our rst partial result deals with the smallest non-trivial case, which is when there are
k + 1 vertices.
Theorem 2.7. Let ;n;k 2N with > 1 and n = k + 1. If is even then Kn can be
decomposed into k-stars. If is odd then there are k
1
2
+ + 12 stars in a maximum
packing of Kn with k-stars. Moreover, the leave graph must be Kk.
Proof. Case 1: is even.
In this case we need only check conditions (1) and (3) from Theorem 1.1, which will guaran-
tee a decomposition. Condition (3) is trivially satis ed since in this case n = k + 1 k + 1.
To show condition (1) we will substitute n = k + 1 to obtain n(n 1) = (k + 1)k. We
14
have that is even, so 2kj (k + 1)k, and thus (1) holds.
Case 2: is odd.
First, notice that every k-star must contain every vertex, since n = k + 1. For any vertex
v2V(Kn), let c(v) denote the number of k-stars centered at v. Now, for any two vertices,
u;v2V(Kn), there are total edges between u and v, so c(u) + c(v) . This leads us
to note that there can be at most one vertex, w2V(Kn), such that c(w) > 2 . We claim
that the number of k-stars is maximum when c(w) = + 12 , and for every vertex u6= w,
c(u) = 12 (see gure 2.4).
k verts.
w
?+1
2
??1
2centered centered
Figure 2.4: The number of k-stars centered at each vertex.
To show that this claim is true, rst notice that all of the vertices in V(Kn)nfwg have the
maximum number of k-stars centered at them. The only parameter that can change is c(w).
If c(w) increases by 1, then we would have to decrease c(u) by one for every u6= w. But this
would result in a net decrease of k-stars. So a maximum packing has the central function
shown in gure 2.4. Now we must show that such a packing is possible.
The center of a star completely determines that star, since every vertex must be included in
it. So we remove + 12 stars centered at w. For each u2V(Kn)nfwg, we remove 12
stars centered at u. Between u and w we have used + 12 + 12 = edges. Between u
and v2V(Kn)nfwg, for u6= v, we have used 12 + 12 = 1 edges. So we have
exactly one edge left between any two vertices in V(Kn)nfwg, and since there are exactly k
15
of these vertices our leave is a complete graph on k vertices. Our leave of Kk is represented
as the blue vertices in gure 2.4. Thus we have obtained the desired maximum packing.
Our next partial result concerns the largest number of vertices that we can have before
the more general theorems take over. This is when there are 2k 1 vertices, but rst we
need a lemma.
Lemma 2.8. Let n;k2N with n = 2k 1. There are
j n
2
k
k
stars in a maximum packing
of Kn with k-stars. Moreover, the leave graph is a single edge.
Proof. We begin by investigating the upper bound on the number of stars in a maximum
packing of Kn.
n
2
= (2k 1)(2k 2)2 = 4k
2 6k + 2
2 = 2k
2 3k + 1 = k(2k 3) + 1
The number of edges is 1 (mod k), so if we can nd a construction that has 2k 3 stars
then we know it is a maximum packing. To this end, we group the vertices of Kn into two
sets, A and B. We let jAj = 2k 3 and jBj = 2, recognizing that jASBj = 2k 1 = n,
so in fact A and B form a partition of the vertices of Kn. We wish to nd a construction
where each vertex of A is the center of exactly one k-star. Take a regular tournament on
A, the existence of which was justi ed in the proof of lemma 2.3. Now for each v2A we
have, from the regular tournament, that d+(v) = 2k 3 12 = k 2. Next, we orient all of
the edges between A and B with tails in A and heads in B. This adds 2 to the outdegree of
every vertex in A, making d+(v) = k. (See gure 2.5).
16
A
B
k?2edges
Figure 2.5: How the stars are constructed.
Every vertex in A has outdegree k so there is a star centered at each of them. The regular
tournament ensures that we use every edge with both ends in A in a k-star, while the
orientation on the edges between A and B ensures that we use all edges of that type. The
only edges we haven?t used are those with both ends in B. There is only one edge of that
type, since jBj = 2. Thus, our leave is a single edge, and we have the desired maximum
packing.
It is important to note that in the proof of lemma 2.8, the set B is arbitrary. Thus we
have control over which edge is the leave edge.
Theorem 2.9. Let 2N and k> 1 be an integer. For n = 2k 1, a maximum packing of
Kn with k-stars has as its leave a loopless graph with (mod k) edges.
Proof. We rst view Kn as copies of Kn, each on the same vertex set. Now, on each copy
of Kn we apply lemma 2.8 to obtain a k-star decomposition in which the leave has a single
edge. We have the freedom to choose which edge becomes the leave edge. Let = kr + s
where r;s2N and 0 s k 1. In kr of the copies of Kn we will choose the leave edge
to have one xed endpoint u2V(Kn). The other endpoints of the edges will be the next
k vertices in Kn. We take care to make sure that each one of these edges has multiplicity
r (see gure 2.6). Clearly r since k > 1 and s 0, so the multiplicity won?t exceed .
17
This edge-balanced multistar can be trivially decomposed into r copies of Sk.
u
multiplicityr
kvertices
Figure 2.6: Organizing the leave edges into an edge-balanced multistar.
There are s more edges in the leave that we are free to arrange however we want, so long
as they form a subgraph of Kn. Note that s (mod k), thus we obtain the desired
leave.
18
Chapter 3
Embedding Partial k-star Decompositions
In this chapter we will investigate how to extend a partial decomposition to a decom-
position. Given graphs G and H, let A be a partial H-decomposition of G { also called an
H-packing of G. Let B be a partial H-decomposition of a graph G0. Then B is called an
embedding of A if A B and G is a subgraph of G0. We are interested in the speci c case
when H is a k-star, and G and G0 are complete graphs. We would also like to nd the small-
est possible graph G0. So our main question becomes: Given a partial k-star decomposition
of Kn, nd the smallest integer, t, in which we can embed the partial decomposition into a
decomposition of Kn+t.
3.1 A Balanced Embedding
It was previously noted that k-stars correspond to orientations in which the center of
the star is the tail of every edge (see gure 3.1). Therefore, in order to construct embeddings
we will rst give some results on the existence of certain types of orientations.
??0
1
2
k
1
2
k
0
Figure 3.1: A k-star corresponds to an orientation.
19
Let Z denote the set of integers. If f : V(G) !Z is a function, then let f(S) denote
X
v2S
f(v). Recall that for any subset S V(G), "(S) denotes the number of edges with both
ends in S.
We now de ne a well-known operation that can be performed on the edge set of a graph.
Given a graph G, and some edge e of G, the graph Gne is the graph with vertex set V(G) and
edge set E(G)nfeg. This operation is called \deletion by e," and the new graph obtained
is referred to as \G delete e".
Lemma 3.1. (D.G. Ho man [5]) Let G be any graph and f : V(G) ! Z. Then G has
an orientation in which each vertex v 2V(G) has outdegree f(v) if and only if for every
S V(G),
"(S) f(S)
with equality if S = V(G).
Proof. First we will discuss the necessity. Let S V(G) and f be de ned as stated above.
Every edge with both ends in S must be oriented, which means that each such edge con-
tributes exactly 1 to the outdegree of some vertex in S. So the largest possible number of
edges with both ends in S which can be oriented is f(S). Therefore, the inequality holds.
As for the case when S = V(G), we must have all of the edges in G oriented, which means
f(S) "(S), and equality follows.
Next, we turn to su ciency. Suppose the conditions on f and G hold. Let v2V(G), then
we note that "(fvg) is the number of loops at v. So 0 "(fvg) f(v). We will continue by
induction on "(G). If "(G) = 0, then f(G) = 0. So f(v) = 0 for every v2V(G), thus there
are no edges to orient and we are done. Let e2E(G) have endpoints u and v.
Case 1: u = v, i.e. e is a loop. Let G0 = Gne and de ne f0 : V(G0)!N by
f0(x) =
8
><
>:
f(v) 1 if x = v
f(x) if x6= v:
20
So we get that for every S V(G)
X
x2S
f0(x) =
8
><
>:
f(S) 1 if v2S
f(S) if v =2S
and "0(S) =
8
><
>:
"(S) 1 if v2S
"(S) if v =2S
where "0(S) denotes the number of edges in G0 with both ends in S. So f0 satis es the
hypotheses for G0 which means that G0 has an orientation with d+G0(v) = f0(v) for every
v2G0. Now, orient e the only way possible, which produces the desired orientation on G.
Case 2: u6= v, i.e. e is not a loop. For A V(G), we de ne A to be critical if "(A) = f(A).
Claim 3.2. Let A and B be critical, then
(I) ATB is critical,
(II) ASB is critical, and
(III) No edge of G has one end in AnB and the other end in BnA.
Proof of claim: Assume A and B are critical. We make the following de nitions, a :=
f(AnB), b := f(BnA), c := f(ATB), 1 is the number of edges with both ends in AnB,
2 is the number of edges with one end in AnB and one end in ATB, 1 is the number of
edges with both ends in B, 2 is the number of edges with one end in BnA and one end
in ATB, is the number of edges with both ends in ATB, and is the number of edges
with one end in AnB and one end in BnA. (See gure 3.2). We get the following equations
A Ba b
c
?
?1 ?1
?2 ?2?
Figure 3.2: Di erent types of edges.
21
and inequalities since f satis es the hypotheses of the lemma and A and B are critical
1 a (EQ1)
1 b (EQ2)
c (EQ3)
1 + 2 + = a+c (EQ4)
1 + 2 + = b+c (EQ5)
1 + 2 + 1 + 2 + + a+b+c (EQ6)
From (EQ4) and (EQ5) we get 1 + 2 = a + c and 1 + 2 = b + c + , which we can
substitute into (EQ6) to get
1 + 2 + 1 + 2 + + a+b+c
a+c +b+c + + a+b+c
c + 0
c+ (EQ7)
But counts some number of edges, which forces 0. Combining this fact with (EQ3)
and (EQ7) we obtain
c c+ c:
So it must be the case that both = c and = 0. These two equations prove (I) and (III)
from Claim 3.2, respectively. We also have that 1+ 2+ 1+ 2+ = a+c+b+c = a+b+c,
and thus (II) is true. Therefore, we have proven Claim 3.2.
Back to the proof of Case 2. Again, let G0 = Gne. Try orienting e with tail u and head v.
22
De ne f0 on V(G0) as follows:
f0(x) =
8
><
>:
f(u) 1 if x = u
f(x) if x6= u:
Let S V(G), and we are interested in when the inequality "0(S) f0(S) is true. Notice
that "(S) f(S), and both
"0(S) =
8
><
>:
"(S) 1 if u;v2S
"(S) otherwise
and f0(S) =
8
><
>:
f(S) 1 if u2S
f(S) if u =2S:
The only situation in which "0(S) >f0(S) is when u2S, v =2S, and S is critical in G. So if
our choice of orienting e with tail u and head v results in failure of our desired inequality, then
we nd a critical set S in G which contains u and not v. The argument works symmetrically
if we choose to orient e with tail v and head u. In that case we nd a critical set T in G
which contains v and not u. It can?t be the case that both choices fail, because that would
result in two critical sets S and T in which there is an edge with one end, u, in SnT and
one end, v, in TnS. Thus, we can nd an orientation of e which results in "0(S) f0(S).
Using our inductive hypothesis we get an orientation on G0, and then by adding e back in {
oriented appropriately { we nd our desired orientation on G.
We now turn our attention towards complete graphs. Lemma 3.3 gives conditions for
a complete graph on n + t vertices with a hole of size n to obtain an orientation in which
the vertices have prescribed outdegrees (see gure 3.3). This will allow us to embed partial
k-star decompositions by considering them as being removed from a complete graph, thereby
creating a hole. The function d will serve as the \patch" for the hole.
23
NT
NoEdges
inN
d+(u)=d0
d+(v)=d(v)
Figure 3.3: The orientation guaranteed by Lemma 3.3.
Lemma 3.3. Let G be a graph whose vertex set is partitioned into sets N and T, and a pair
of distinct vertices in G are adjacent if and only if they are not both in N. Let jTj= t and
jNj = n, d : N !N and d0 2N. Then G has an orientation in which each vertex v2N
has outdegree d(v) and each vertex in T has outdegree d0 if and only if
(i) 8v2N d(v) t, and
(ii) td0 +
X
v2N
d(v) =
t
2
+tn.
Proof. Assume G has such an orientation. To show (i) let v2N. The only edges which can
be oriented outwards from v are of the form vx where x2T. There are only t such vertices
in T, so d(v) t. To show (ii) we note that the LHS counts the total number of edges in G
by counting all of the outdegrees of the vertices, while the RHS counts the total number of
edges in G because we have a complete graph on t vertices along with a complete bipartite
graph with parts of size t and n.
Now assume that (i) and (ii) hold. We will apply lemma 3.1 with
f(v) =
8
><
>:
d(v) for v2N
d0 for v2T:
24
Let S V(G). Then S = ISJ where I = STT and J = STN, and we will say that
jIj= i andjJj= j. We have that "(S) =
i
2
+ij and
X
v2S
f(v) = d0i+d(J), so we get the
following:
"(S)
X
v2S
f(v) ()
i
2
+ij d0i+d(J) (A)
() 0 12i2 + (d0 +j 12)i+d(J)
The last inequality involves a concave-down quadratic in i, so we need only check the end-
points. When i = 0 we get
0
2
+ 0 d(J), which is true. When i = t we rst note that
td0 +d(J) = tn+
t
2
X
v2NnJ
d(v). And, to show that (A) holds, we must show that
t
2
+tj d0t+d(J)
t
2
+
X
v2J
t tn+
t
2
X
v2NnJ
d(v)
X
v2J
t+
X
v2NnJ
d(v) tn
and we have that
X
v2J
t+
X
v2NnJ
d(v)
X
v2J
t+
X
v2NnJ
t =
X
v2N
t = tn
The above line shows that (A) is true. Now we must show that equality holds when S =
V(G), in which case we get
"(S) =
t
2
+tn =|{z}
by(ii)
td0 +
X
v2N
d(v) =
X
v2S
f(v)
25
The next theorem is our rst result on embeddings. The type of decomposition con-
structed is sometimes referred to as \balanced" because the number of k-stars centered at
each vertex is the same. We will utilize the tools we have developed for orientations to prove
it.
Theorem 3.4. Given a partial k-star decomposition of Kn and some d0 2 N such that
d0 n 1k , the partial decomposition can be embedded into a k-star decomposition of Kn+t
where t = 2kd0 n+ 1 and every vertex has d0 k-stars centered at it.
Proof. Let c : V(Kn)!N be the central function of the partial k-star decomposition of Kn.
We must choose t such that Kn+t has a k-star decomposition. The number of edges in Kn+t
must equal the sum of the edges used in all of the stars, and we obtain the following:
n+t
2
= (n+t)kd0
(n+t)(n+t 1)
2 = (n+t)kd0
n+t 1 = 2kd0
t = 2kd0 + 1 n
Let V(Kn) = fv1;:::;vng. Notice that 8v 2 Kn the maximum number of k-stars that
can be centered at v is bn 1k c, so we can assume that the partial decomposition of Kn is
maximal, i.e. the number of edges incident with v which are not used in the partial k-star
decomposition is less than k. Take an arbitrary orientation of the edges in the compliment
of the partial k-star decomposition of Kn. Let f : V(Kn) !N be de ned such that f(v)
equals the outdegree of v in this orientation. Notice that8v2V(Kn) f(v) <
>:
k if k is odd
2k if k is even
We now state some results on the periodic nature of
n
2
(mod k). This will assist us with
obtaining a small embedding.
Lemma 3.7. For every n 2 Z+, the equivalence
n
2
n+p
2
(mod k) has smallest
non-negative integer solution p = k .
Proof. We rst expand each side of the equivalence to obtain
n(n 1)
2
(n+p)(n+p 1)
2 (mod k)
n(n 1) (n+p)(n+p 1) (mod 2k)
n2 n n2 + 2np+p2 n p (mod 2k)
0 2np+p2 p (mod 2k)
32
So for all n2Z+ we require that 2kjp(p+ 2n 1), which implies that
2kjpgcdfp+ 2n 1 : n2Z+g
To nd the gcd we notice that fp + 2n 1 : n 2 Z+g = fp + 1;p + 3;p + 5;:::g. So
gcdfp+ 2n 1 : n2Z+g= gcdfp+ 1;p+ 3;p+ 5;:::g=
8
><
>:
2 if p is odd
1 if p is even
Thus, we require that
2k divides
8
><
>:
2p if p is odd
p if p is even
If p is even, then the smallest value is p = 2k. If p is odd, then there is no solution for k
even, but if k is odd then the smallest value is p = k.
Corollary 3.8. If x n 1 (mod k ) then
x
2
n+ 2k 1
2
(mod k)
Proof. Assume that x n 1 (mod k ).
We have from Lemma 3.7 that
n 1
2
(mod k) is periodic with period k . So, no matter
the parity of k, we have
x
2
(mod k)
n 1
2
(mod k)
n 1 + 2k
2
(mod k):
Recall that we de ned k =
8
><
>:
k if k is odd
2k if k is even
.
Theorem 3.9. A partial k-star decomposition of Kn can be embedded into a k-star decom-
position of Kn+s where s 6k +k 4
Proof. Let N be a complete graph on n vertices with a partial k-star decomposition A. So
A is a set of edge-disjoint copies of k-stars in N.
33
Step 1: Apply lemma 3.5 to embed A into a partial k-star decomposition, B, of N_M
where M is a complete graph on 2k 1 vertices. Note that B is guaranteed to have the
property that its leave is contained in M.
Step 2: Choose a set, X, of x vertices from V(N_M) with the following properties:
(a) V(M) X
(b) x n 1 (mod k )
(c) x is minimum with respect to the above properties.
N
M
Leave
X
Figure 3.6: Choosing the set, X, of vertices.
Notice that by applying Corollary 3.8 to condition (b) we have that
x
2
n+ 2k 1
2
(mod k). LetB denote the edges which are not used in copies of k-stars inB. We also have
that B E(M) E(X), which means that
x
2
jBj
n+ 2k 1
2
jBj (mod k) ()
x
2
n+ 2k 1
2
(mod k):
SinceB is a partial k-star decomposition we have that
n+ 2k 1
2
jBj 0 (mod k). So
condition (b) guarantees that
x
2
jBj 0 (mod k).
Step 3: We will embed the partial k-star decomposition on X into a k-star decomposition
34
of a complete graph. Let L denote the leave. Let g : V(L) !N represent the outdegrees
of an arbitrary orientation on E(L). Since we have condition (b), we can de ne a function
f : V(X) !N such that
X
v2X
kf(v) = jE(X)nE(L)j and for each v2X we have kf(v) +
g(v) x 1. In order to apply lemma 3.6 with d0 x 1k we note that for every v2V(X)
kf(v) +g(v) x 1 x 1k k d0k;
which implies that
x 1 kf(v) g(v) x 1 d0k:
Thus, the partial k-star decomposition on X can be embedded into a k-star decomposition
on T_X where T is a complete graph on t vertices.
Step 4: Finish the decomposition. The only thing we have left to show is that we can
decompose the complete bipartite graph whose vertices come from T and V(N)nV(X),
which we will call Y, into k-stars.
N
M
X
T
Y
Figure 3.7: A k-star decomposition of the remaining bipartite graph with partition (T,Y).
Let y = jV(N)TV(X)j, and we have that x = y + 2k 1. From corollary 1.3 we see that
this complete bipartite graph has a decomposition into k-stars if and only if the following
35
two conditions hold:
kjt(n y)
and
If k> (n y) then kjt; and if k>t then kj(n y)
To show the rst condition, we note n y = n x + 2k 1 = (n 1) x + 2k, and recall
that x n 1 (mod 2k). Therefore, n 1 x 0 (mod 2k). Hence, kj(n y), which
implies that kjt(n y). To show the second condition, we rst note that if k > t then
we?re done, because kj(n y). Also, due also to the fact that kj(n y), it can?t be the case
that k > (n y) so the second part of the second condition is trivially satis ed. Thus, our
complete bipartite graph can be decomposed into k-stars, and this nishes the embedding.
Step 5: Count the total number of vertices. The smallest value for t is achieved when
d0 =dx 1k e, so
t = 2kd0 x+ 1 2k(x 1 +kk ) x+ 1 = 2k +x 1:
Also, from condition (b) we have
x 2k 1 +k 1
which means that
t 4k +k 3
We have n+ 2k 1 +t total vertices, and
n+ 2k 1 +t n+ 6k +k 4
36
Chapter 4
Hyperstar Decompositions of Hypergraphs
4.1 What is a hyperstar?
The results in this section are all joint work with M. A. Bahmanian [1]. They have
previously been obtained by Lonc [10], but we give an alternative proof.
In order to de ne what a hyperstar is we must rst de ne a hypergraph. A hypergraph is a
pair (X;E) where X is a set and E is a collection of subsets of X. We refer to the elements
of X as vertices and the elements of E as hyperedges. Note that a graph is, in fact, a
hypergraph where the size of each edge is 2 { allowing that loops be considered as multisets.
A multigraph is also a hypergraph where E is considered as a multiset. A hypergraph can
also have multi-hyperedges, which means that a hyperedge can be repeated multiple times.
Figure 4.1 is a hypergraph with vertex setf1;2;3;4;5;6;7;8g, with a repeated edgef1;2;3g,
and a loop f8g.
1
2
3
4
5 6
78
Figure 4.1: A hypergraph.
We can now de ne a hyperstar, which is a generalization of a star. A hypergraph G = (X;E)
is a hyperstar with center C if C
\
E2E
E. The size of G isjEjand we say that G has center
37
size jCj. A hyperstar of size k with center C is denoted bySk(C). For brevity,Sk(v) denotes
Sk(fvg), and Sk denotes a hyperstar of size k and center size 1. A hyperstar can have more
than one center, for example the hyperstar in gure 4.2 has centers f3;4g, f3g, f4g and ?.
An interesting distinction between stars and hyperstars is that the edges of a hyperstar can
intersect outside of the center. The edgesf3;4;5;6gandf3;4;6;7gin the hyperstar in gure
4.2 have the vertex 6 in their intersection, but 6 is not in any center of the hyperstar.
1
2 3 4 5
67
Figure 4.2: A hyperstar of size 3 with center size 2.
We can de ne a decomposition of a hypergraph much like how we de ned it for a graph.
Let G = (X;E) be a hypergraph and let H = fHigi2I be a family of hypergraphs where
Hi = (Xi;Ei). We say that G has an H-decomposition if fEi : i2Ig partitions E and each
Ei forms an isomorphic copy of Hi.
For a positive integer r and a set Y, P(Y) denotes the set of all subsets of Y and
Pr(Y) denotes the set of all r-subsets of Y. Let G = (X;E) be a hypergraph, and let
C
[
E2E
P(E). For every T C we de ne the set
T(E;C) =fE2E : P(E)
\
C Tg:
The collection C will play the role of the set of centers of hyperstars in the desired hyperstar
decomposition. For each T C the relationship of the set T(E;C) with the hyperstar
decomposition is a bit more subtle. Therefore, we will examine this set via an example.
38
(See example 4.1). For any given T C, the set T(E;C) is the set of all hyperedges whose
intersection with C is a subset of T { this includes hyperedges whose intersection with C is
empty, as the empty set is always a subset of T.
Example 4.1. Examining T(E;C) where G = K36, C = ff1g;f2g;f3;4gg, and T =
ff2g;f3;4gg.
1
2
3
4
5
6 T
Figure 4.3: Determining whether a hyperedge is an element of T(E;C) or not.
The orange vertices are the vertices covered by C. The way we can determine if a
hyperedge is in T(E;C) or not is by looking at the intersection of P(E) with C. This
intersection will consist of subsets of vertices, and if these are all elements of T (blue subsets)
then the edge is in T(E;C). In gure 4.3 the green edges are in T(E;C) and the red edges
are not. This information is presented in table 4.1.
E P(E)TC Element of T(E;C)?
f1;2;3g ff1g;f2gg no
f2;3;5g ff2gg yes
f3;5;6g ? yes
Table 4.1: Categorizing the edges of gure 4.3.
This concludes the example.
Now we turn back to hyperstar decompositions. We will need the following theorem
which gives necessary and su cient conditions for a hypergraph to be decomposed into
39
hyperstars with given sizes and centers. This is the result in which the set T(E;C) realizes
its full potential.
Theorem 4.2. (Lonc [9]) Let G = (V;E) be a hypergraph. Let C
[
E2E
P(E), and : C !
Z+ be a function. Then G has an fS (C)(C) : C2Cg-decomposition if and only if
(i) P(E)
\
C 6= ? for all E2E,
(ii) jEj=
X
C2C
(C), and
(iii) jT(E;C)j
X
C2T
(C) for all T C.
For the proof we refer the reader to Lonc [9], but we remark that the proof relies on a
clever application of Hall?s Marriage Theorem, which is a classical result in graph theory. It
deals with nding matchings in bipartite graphs. A matching in a graph is a set of edges
which have no common endpoints. Let G be a bipartite graph with bipartition (A;B). A
matching in G saturating A is a matching in which each vertex of A is incident with exactly
one edge. Hall?s Theorem can be used to characterize those bipartite graphs which have a
perfect matching, which is de ned to be a matching which saturates all of the vertices. We
state this theorem for the reader?s mathematical enjoyment:
Theorem 4.3. (P. Hall [3])
Let G be a nite bipartite graph with vertex bipartition (A;B). Then G has a matching
saturating A if and only if for every subset S A, jSj jN(S)j.
where N(S) { called the neighbor set of S { denotes the set of vertices which are adjacent
to at least one vertex in S. Note that when jAj=jBj we get a matching saturating both A
and B, which is a perfect matching. The original formulation of Hall?s theorem was stated
in the language of systems of distinct representatives. This result has been extended by M.
Hall [4] to include an in nite number of sets.
40
4.2 Decomposing Complete Uniform Hypergraphs into Hyperstars
The complete m-uniform hypergraph on n vertices, denoted Kmn , is a hypergraph with
n vertices which has as its edge set all m-subsets of its vertices.
We start with a technical lemma which aids in the proof of the main result of this section:
Lemma 4.4. Let n;? be positive integers with ? n + 1. Suppose m1 m? is a
sequence of positive integers such that for k = 1;:::;n 1
?X
i=1
mi =
n
m
and
kX
i=1
mi
n
m
n k
m
:
If m01 m0? 1 is a rearrangement of m1;:::;mn 1;mn + m?;:::;m? 1, then for k =
1;:::;n 1
? 1X
i=1
m0i =
n
m
and
kX
i=1
m0i
n
m
n k
m
:
Proof. It is obvious that
? 1X
i=1
m0i =
?X
i=1
mi =
n
m
. Suppose m0t = mn + m? where t n. It
is easy to see that
m0i =
8
><
>:
mi for i = 1;:::;t 1
mi 1 for i = t+ 1;:::;n:
Therefore, for j < t, we have
jX
i=1
m0i =
jX
i=1
mi
n
m
n j
m
. Now, suppose to the
contrary that there is some j with t j n 1, such that
jX
i=1
m0i
n
m
n j
m
+ 1.
41
Then we have
2mn mn +m? = m0t =
jX
i=1
m0i
j 1X
i=1
mi
n
m
n j
m
+ 1
n
m
+
n j + 1
m
=
n j
m 1
+ 1:
But
n
m
=
? 1X
i=1
m0i =
jX
i=1
m0i +m0j+1 + +m0? 1
n
m
n j
m
+ 1 + (mj + +mn 1) + (mn+1 + +m? 1)
n
m
n j
m
+ 1 + (n j)mn + (mn+1 + +m? 1)
n
m
n j
m
+ 1 + 12(n j)
n j
m 1
+ 1
: (M1)
Now we show that
1
2(n j)
n j
m 1
+ 1
+ 1 >
n j
m
: (M2)
This together with (M1) implies that
n
m
>
n
m
, a contradiction. Let p = n j. Note
that since j n 1, we have p 1. To prove (M2) it is enough to show that
p
p
m 1
+p+ 1 2
p
m
:
42
If p 2m 1 then
p
m
p
m 1
which implies p
p
m 1
+ p + 1 2
p
m
. If
p> 2m 1, then because m 2 we have the following sequence of inequalities:
p(m 2) + 2(m 1) + (p+ 1)m!p(p 1):::(p m+ 2) 0 ()
pm+ (p+ 1)m!p(p 1):::(p m+ 2) 2(p m+ 1) ()
pmp(p 1):::(p m+ 2) + (p+ 1)m! 2p(p 1):::(p m+ 1) ()
p
p(p 1):::(p m+ 2)
(m 1)!
+p+ 1 2
p(p 1):::(p m+ 1)
m!
()
p
p
m 1
+p+ 1 2
p
m
:
This completes the proof.
Theorem 4.5. Let m1 m? be positive integers. Then Kmn can be decomposed into
hyperstars Sm1;:::;Sm? if and only if
(i) ? n m+ 1,
(ii)
?X
i=1
mi =
n
m
, and
(iii)
kX
i=1
mi
n
m
n k
m
for k = 1;:::;? 1.
Proof. Let Kmn = (V;E) where V =fv1;:::;vng. There are two cases:
Case 1: ? n. Let C = ffv1g;:::;fv?gg, and let : C ! Z+ be a function with
(fvig) = mi for 1 i ?. By Theorem 4.2, there is an fSmi(vi) : fvig2C;1 i ?g-
decomposition of Kmn if and only if
(1) P(E)
\
C 6= ? for all E2E,
(2) jEj=
X
fvig2C
(fvig), and
(3) jT(E;C)j
X
fvig2T
(fvig) for every T C.
43
It is easy to see that
n
m
= jEj and
X
fvig2C
(fvig) =
?X
i=1
mi and thus (2) and (ii) are
equivalent. Now, we show that (1) and (i) are equivalent. If (i) holds, then we havejP1(V)n
Cj n (n m+ 1) = m 1, so there can be no edge which does not meet C. Suppose (1)
holds. If by contrary ?<
>:
mi+2 for i = 1;:::;t 1
mi+1 for i = t+ 1;:::;? 1:
It is clear that
? 1X
i=1
m0i =
?X
i=1
mi = 2n 1:
Notice that for every i 2 f1;:::;? 1g we have that m0i mi. Thus, for every k 2
f1;:::;n 1g we get
kX
i=1
m0i
kX
i=1
mi 2k 1:
47
Again, we can use lemma 4.4 ? n times to obtain an appropriate sequence of m0i?s which
produces an fSm0i : 1 i ng-decomposition of our complete hypergraph. All we have
left to do is to split the hyperstar centered at each vertex into an appropriate number of
hyperstars of smaller sizes. The rest of the proof is analogous to the proof of Case 2 of
Theorem 4.7.
As mentioned earlier, Lonc [10] obtained these results in 1992. His method of proof
involved looking at packings and coverings of hypergraphs with hyperstars. He then used
these structures to nd the results of theorems 4.5 and 4.7.
48
Chapter 5
Concluding Remarks
We present a brief summary of the main results and open problems from each chapter.
From chapter 2:
Result 1. Let n;k2N with n 2k. Then there are
j n
2
k
k
stars in a maximum packing
of Kn with k-stars. Moreover, it is possible to have the leave graph be a star of size smaller
than k.
Result 2. Let n;k2N with k 1 and n = k+1. If is even then Kn can be decomposed
into k-stars. If is odd then there are k
1
2
+ + 12 stars in a maximum packing of
Kn with k-stars. Moreover, the leave graph must be Kk.
Result 5. Let ;n;k 2 N with > 1 and n = 2k 1. Then there are
j n
2
k
k
stars in
a maximum packing of Kn with k-stars. Moreover, the leave can be any subgraph of Kn
which has (mod k) edges.
For some of the above cases we have characterized the leave graph(s), but for some cases
only the number of stars and at least one con guration of the leave is known. The astute
reader will notice that there is a gap in the full solution of this problem. We must confront
the following:
49
Open Problem 1. Given ;n;k 2 N such that > 1 and k + 2 n 2k 2, nd a
maximum packing of Kn with k-stars.
The author suggests attacking open problem 1 via orientations. There is a natural
generalization of this question where we allow stars of di erent sizes. This is analogous to
generalizing the theorem of Yamomoto [13] and Tarsi [12] to the theorem of Lin and Shyu
[8]. We present it as an open problem.
Open Problem 2. Given m1;m2;:::;m?2Z+ and ;n2N, characterize the leave graph
of a maximum packing of Kn with stars of sizes m1;m2;:::;m?.
In chapter 3 our quest was to nd a small embedding of a partial k-star decomposition
of Kn which depended only on k. We achieved that feat, and here we state the main result.
Result 6. A partial k-star decomposition of Kn can be embedded into a k-star decomposition
of Kn+s where s
8>
<
>:
7k 4 if k is odd
8k 4 if k is even
.
The satisfying part of this result is that the number of new vertices depends only on k.
The embedding is on a relatively small number of vertices; however, this is not the smallest
possible number. The author believes that it can be reduced. The methods used in this work
may be of some use in reducing the number of new vertices, namely, relaxing the \balanced"
condition of theorem 3.4. We note that any decomposition of Kn+s requires
n+s
2
0 (mod k). Combining this with the periodic nature of
n
2
(mod k) (lemma
3.7) gives a good estimate for the smallest possible value of s to be about 2k.
Open Problem 3. Given a partial k-star decomposition of Kn, nd an embedding into a
k-star decomposition of Kn+s where s is no more than approximately 2k.
In chapter 4 we provided alternative proofs to some results obtained by Lonc [9]. Recall
that we denote a hyperstar of size mi with center size 1 by Smi.
Result 7. Let m1 m? be positive integers. Then the complete m-uniform hypergraph
on n vertices, Kmn , can be decomposed into hyperstars Sm1;:::;Sm? if and only if
50
(i) ? n m+ 1,
(ii)
?X
i=1
mi =
n
m
, and
(iii)
kX
i=1
mi
n
m
n k
m
for k = 1;:::;? 1.
Recall that the complete hypergraph on n vertices is de ned to be a hypergraph on n
vertices whose edge set is all non-empty subsets of those vertices.
Result 8. Let m1 m? be positive integers. Then the complete hypergraph on n
vertices can be decomposed into hyperstars Sm1;:::;Sm? if and only if
(i) ? n,
(ii)
?X
i=1
mi = 2n 1, and
(iii)
kX
i=1
mi 2k 1 for k = 1;2;:::;n 1.
It is easy to generalize this problem by allowing hyperstars with di erent center sizes.
However, it should be noted that even allowing centers of size 2 greatly complicates the
problem. The author would suggest rst looking into the following problem:
Open Problem 4. Given m1;m2;:::;m?, nd necessary and su cient conditions for the
complete multipartite uniform hypergraph to obtain a decomposition into hyperstars of sizes
m1;m2;:::;m? with centers of size 1.
The above problem is more complicated than those problems solved in results 7 and 8,
but it seems to be easier than allowing larger centers.
It is the author?s decision to omit a summary of the results of chapter 5 to avoid the
cycle of length @0 that would ensue.
51
Bibliography
[1] M. A. Bahmanian, Personal Communication.
[2] Dorit Dor and Michael Tarsi, Graph Decomposition is NP-Complete: A Complete Proof
of Hoyler?s Conjecture, SIAM J. Comput., 26, 1997, no. 4, 1166-1187.
[3] Phillip Hall, On Representatives of Subsets, J. London Math. Soc., 10 (1), 26-30, 1935.
[4] Marshall Hall, Distinct Representatives of Subsets, Bull. Amer. Math. Soc., 54, 1948,
922-926.
[5] D.G. Ho man, Personal Communication.
[6] D.G. Ho man, The real truth about star designs, Discrete Math., 284, 2004, 177-180.
[7] D.G. Ho man and Mark Liatti, Bipartite Designs, Journal of Combinatorial Designs,
3, 1995, no. 6, 449-454.
[8] Chiang Lin and Tay-Woei Shyu, A Necessary and Su cient Condition for the Star
Decomposition of Complete Graphs, Journal of Graph Theory, 23, no. 4, 1996, 361-364.
[9] Zbigniew Lonc, Decompositions of Hypergraphs into Hyperstars, Discrete Math., 66,
1987, no. 1-2 157-168.
[10] Zbigniew Lonc, Partitions, Packings and Coverings by Families with Nonempty Inter-
sections, Journal of Combinatorial Theory A, 61, 263-278, 1992.
[11] M. Tarsi, Decomposition of complete multigraphs into stars, Discrete Math., 26, 1979,
273-278.
[12] M. Tarsi, On the decomposition of a graph into stars, Discrete Math., 36, 1981, 299-304.
[13] S. Yamamoto et. al., On claw-decomposition of complete graphs and complete bigraphs,
Hiroshima Math. J., 5, 1975, 33-42.
52