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<k. So we have
nm
k  n
jm
k
k
+m
jn
k
k
(kp+s)(kq +r)
k  (kp+s)
 kq +r
k
 
+ (kq +r)
 kp+s
k
 
kpq +sq +pr + srk  kpq +sq +kpq +pr
sr k2pq
But we know that rs<k2, so we only require
If either p = 0 or q = 0; then either r = 0 or s = 0
But m;n> 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 ?<n 1. Then we have that
?X
i=1
mi <k(n 2)+
 n
2
 
 k(n 1) =
 n
2
 
 k,
which contradicts (i). For p = 1;2;:::;n 1 we have that ?  p, and upon examining
condition (ii), we need to show that
pX
i=1
mi 
pX
i=1
(n i)
pk pn p(p+ 1)2
p(p+ 1)
2  pn pk
We have
p(p+ 1)
2  
pn
2  p(n k) = pn pk
where the  rst inequality holds because p + 1 n and the second inequality holds because
n=2 n k. Thus, (ii) holds and we conclude that Kn can be decomposed into ? 1 k-stars
and one star of size smaller than k.
Lemma 2.1 shows that for n 2k a maximum packing of Kn with k-stars has less than
k edges in the leave. However, it does not prove that the only con guration of these leave
edges is a star, but merely  nds a maximum packing with this (very desirable) property. It
is not known to the author what other types of graphs the leave might be. On the contrary,
lemma 2.3 exactly characterizes the leave graph of a maximum packing for the case when
n< 2k. We must  rst state the results for the trivial cases.
Lemma 2.2. 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. If n k then there are no k-stars in Kn, because a k-star has k + 1 vertices. So a
maximum packing with k-stars has no stars in it, and the leave is Kn.
9
Lemma 2.3. Let n;k2N with k < n < 2k. There are 2n 2k 1 stars in a maximum
packing of Kn with k-stars. Moreover, the leave graph must be K2k n+1.
Proof. The crucial observation we make is that when n< 2k, we can have at most one star
centered at any given vertex. To see this, note that a star which is centered at vertex  
must contain edges of the form  x for k other vertices x. Having 2 stars centered at  would
requirejV(Kn)nf gj 2k, however we know thatjV(Kn)nf gj< 2k 1. Thus, there can
be at most one star centered at vertex  . In  gure 2.1 there are n 1 total vertices on the
right side of the graph.
k
<k
?
V(Kn)\{?}
Figure 2.1: At most one star centered at each vertex.
Now, let b be the number of k-stars in a maximum packing of Kn. For notational purposes,
we partition the vertices of Kn into two sets B and N, where B is the set of vertices that
are the center of a star, and N is the set of vertices that are not the center of any star. It
may be useful to note thatjBj= b andjNj= n b. Let v2B, then there are k edges used
in the star centered at v. These edges can be of two types: either one endpoint is v and the
other endpoint is in B, or one endpoint is v and the other endpoint is in N. (See  gure 2.2).
10
B
N
Figure 2.2: The di erent types of edges used in stars.
This argument holds for every v2B, so we get the inequality
bk 
 b
2
 
+b(n b)
b(k n+b) b(b 1)2
2(k n+b) b 1
b 2n 2k 1
In a maximum packing we have b maximum. Therefore, if we can  nd a construction which
achieves equality, i.e. b = 2n 2k 1, then we know it must be the best possible. We
will  nd such a construction by  nding an orientation of the edges within B as well as the
edges with one endpoint in B and the other endpoint in N. The edges with both endpoints
in N can?t be used in any star, as there are no stars centered in N, so we need not orient
them. In the construction, a star with center v2B will be guaranteed by d+(v) = k in the
orientation. The pendant vertices of the star are the heads of the arcs with tail v.
The construction: First, take a regular tournament on B, where for each v2B we have
d+(v) = b 12 = n k 1. Note that we can always  nd such a regular tournament
because B is a complete graph on an odd number of vertices. Also, notice that k n+b =
k n + (2n 2k 1) = n k 1, so for any given v2B we have used the least possible
11
number of edges in B for the star centered at v. Therefore, for this star we must use all
n b edges with one endpoint at v and the other endpoint in N. So the next step in the
construction is to orient all of the edges with one endpoint in B and the other endpoint in
N so that their tails are in B and their heads are in N.
We have that n b = 2k n + 1, so for each v 2 B, d+(v) = (n k 1) + (n b) =
n k 1 + 2k n+ 1 = k. Thus, we have exactly one star centered at each vertex in B. We
have oriented all edges in Kn except those with both endpoints in N, and hence the leave is
K2k n+1.
Now that we have studied maximum packings of Kn, we can study these structures for
higher values of  .
2.2 The case when  > 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, because the
partial decomposition is maximal.
Let G be the graph with vertex partition N = fv1;:::;vng and T = fvn+1;:::;vn+tg, and
two vertices are adjacent in G if and only if they are not both in N. An orientation of G
26
such that every vertex in N has outdegree k(d0 c(v)) f(v) and every vertex in T has
outdegree kd0 corresponds to an orientation of Kn+t such that every vertex has outdegree
kd0. Thus,  nding such an orientation implies embedding our partial decomposition of Kn
into a decomposition of Kn+t. We must apply lemma 3.3 with d(v) = k(d0 c(v)) f(v) and
the outdegree in T being kd0. To show (i), note that d(v) is maximum when kc(v) +f(v) is
minimum, and this value might be 0. Thus, d(v) kd0. Now, by assumption we have:
n 1
k  d0
0 kd0 + 1 n
kd0 2kd0 + 1 n
Hence, d(v) kd0 2kd0 + 1 n = t and (i) is true. To show (ii):
tkd0 +
X
v2N
d(v) = tkd0 +
X
v2N
k(d0 c(v)) f(v)
= tkd0 +k
X
v2N
d0 
X
v2N
(kc(v) +f(v))
= tkd0 +nkd0 
 n
2
 
=
 n+t
2
 
 
 n
2
 
=
 t
2
 
+tn
Hence, (ii) is true. Our orientation is guaranteed by lemma 3.3.
27
3.2 A Small Embedding
The main goal of this section is to produce an embedding of a partial k-star decomposi-
tion in which the number of new vertices depends only on k. We would also like the number
of new vertices to be as small as possible. To this end, we make the following de nition. Let
G and H be graphs. If G and H have disjoint vertex sets, then let G_H denote the graph
with vertex set V(G)SV(H) and edge set E(G)SE(H)Sfuv : u2V(G) and v2V(H)g.
The  rst lemma is an embedding of a partial system into another partial system. While it
is not the main result that we desire, it is a step in the right direction because the number
of new vertices depends only on k. The construction also shrinks the leave down into a
manageable number of vertices.
Lemma 3.5. Any partial k-star decomposition of Kn can be embedded into a partial k-star
decomposition of Kn+2k 1 in such a way that the new leave is restricted to the 2k 1 new
vertices.
Proof. Let B be a partial k-star decomposition of Kn with leave L. Let T be a complete
graph on 2k 1 vertices, and let G = Kn_T. Our goal is to build another collection, B0, of
k-stars in G that can be put together with B to form our embedding. We can assume that B
is maximal, i.e. that every degree in L is at most k 1. (If there were some vertex v2V(L)
with degree k or more, then we could center another k-star at v and include that star in the
collection B0.) Now, place an arbitrary orientation on the edges of L. For each v2L, use
k dL(v) edges going from Kn to T with tails at v to form a k-star, and include this star in
B0. (See  gure 3.4.) Note that this is possible because dL(v) k 1 andjV(T)j= 2k 1.
28
vKn
T
L
Figure 3.4: Extending the orientation of the leave to k-stars.
Now, let w2T. For the rest of the edges with one end at w and the other end in Kn that
haven?t been used, orient them with tail at w. Form as many k-stars as possible with these
edges, and include these edges in B0. We will have some number i < k of them left over.
(See  gure 3.5.)
Kn
T
k ki
w
Figure 3.5: Using almost all edges between Kn and T.
At this point we have d+(w) = i < k. We also have the edges with both ends in T yet
to use in k-stars. To this end, take a regular tournament on T. Notice that now d+(w) =
i+ 2k 22 = i+k 1. We will use as many of these edges as possible in k-stars and include
them in B0. If i 1 then we can center at least one more k-star at w. In this case we will
have used all the edges with one end in Kn and the other end in T. Otherwise, i = 0 and all
of these edges were used in the previous steps. We now have the partial k-star decomposition
BSB0 of Kn_T, whose leave is a subset of T.
29
The following is a generalization of theorem 3.4, but we tailor it to make it useful for
theorem 3.9. The major di erence is that lemma 3.6 does not require that we begin with a
partial k-star decomposition, but only that our number of edges is a multiple of k. Let Z+
denote the set of positive integers.
Lemma 3.6. Fix n;k 2Z+. Let N be a complete graph on n vertices with a subgraph L
which has the property that k divides jE(N)nE(L)j. Let f : V(N)!N and g : V(L)!N
be functions such that
X
v2N
kf(v) +g(v) =
 n
2
 
. For each d02N such that
(i) For every v2V(N) kf(v) +g(v) kd0, and
(ii) For every v2V(N) n 1 kf(v) g(v) kd0
then Kt_N has a k-star decomposition where t = 2kd0 n+ 1 and every vertex has d0 stars
centered at it.
Proof. Let G be the graph with vertex set V(Kt)SV(N) and edge set E(Kt_N)nE(N).
For every v2N, de ne the function d : V(N) !N such that d(v) = d0k kf(v) g(v).
Note that from condition (i) we obtain that for every v2N
0 kd0 kf(v) g(v) = d(v)
Thus, d(v) is non-negative. Notice that a k-star decomposition of Kt_N in which every
vertex has d0 stars centered at it corresponds to an orientation of G in which every vertex
in V(Kt) has outdegree kd0 and every vertex in V(N) has outdegree d(v).
We must choose t with the property that Kt_N has a k-star decomposition, so the number
30
of edges must be divisible by k. Thus, we obtain that
 n+t
2
 
= (n+t)kd0
(n+t)(n+t 1)
2 = (n+t)kd0
n+t 1 = 2kd0
t = 2kd0 + 1 n
By adding together the inequalities of conditions (i) and (ii) we get
kf(v) +g(v) +n 1 kf(v) g(v) kd0 +kd0
0 2kd0 n+ 1 = t
Thus, t is non-negative. Now we must show that d satis es the conditions of lemma 3.3. By
applying condition (ii) we see that for every v2G
n 1 kf(v) g(v) kd0
 kf(v) g(v) kd0 +n 1
kd0 kf(v) g(v) 2kd0 +n 1
d(v) t
31
To see the condition on the total number of edges:
tkd0 +
X
v2N
d(v) = tkd0 +
X
v2N
(kd0 kf(v) g(v))
= tkd0 +nkd0 
X
v2N
(kf(v) +g(v))
= (n+t)kd0 
 n
2
 
=
 n+t
2
 
 
 n
2
 
=
 t
2
 
+tn
Therefore, both conditions of lemma 3.3 are satis ed and G has the desired orientation.
For the rest of this chapter we will use the following notation:
k :=
8
><
>:
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 ?<n m+ 1, then there are at least n (n m) = m vertices which
are not infv1;:::;v?g. These m vertices form an edge E with the property P(E)TC = ?,
a contradiction. Therefore (1) and (i) are equivalent.
Now we show that (3) and (iii) are equivalent. Let T  C with jTj = j. Since C
is a set of singletons we have that T(E;C) = fE 2E : P1(E)TC  Tg, which means
that T(E;C) = fE2E : P1(E)T(CnT) = ?g = fE2E : ET(S(CnT)) = ?g. Thus
T(E;C) induces a complete m-uniform hypergraph on n (? j) = n ?+j vertices. Hence,
jT(E;C)j=
 n ?+j
m
 
. Assume that (3) holds and let j2f1;:::;? 1g. By (3) we have
that for all T  C with jTj= j
 n ?+j
m
 
=jT(E;C)j 
X
fvig2T
 (fvig) =
X
fvig2T
mi:
Taking T =ffv? j+1g;:::;fv?gg produces
 n ?+j
m
 
 
?X
i=? j+1
mi =
 n
m
 
 
? jX
i=1
mi:
Thus,
? jX
i=1
mi 
 n
m
 
 
 n ?+j
m
 
. Settingk = ? j implies that
kX
i=1
mi 
 n
m
 
 
 n k
m
 
for k = 1;:::;? 1. Now, assume that (iii) holds and let T  C with jTj = j. Then (iii)
yields
? jX
i=1
mi 
 n
m
 
 
 n ?+j
m
 
=
 n
m
 
 jT(E;C)j:
So
jT(E;C)j 
 n
m
 
 
? jX
i=1
mi =
?X
i=? j+1
mi 
X
fvig2T
 (fvig)
44
where the last inequality holds because the mi?s form a decreasing sequence. Therefore (iii)
and (3) are equivalent.
Case 2: ? n+1. First suppose that Kmn can be decomposed into hyperstarsSm1;:::;Sm?.
The necessity of (i) and (ii) is su ciently obvious. By combining all the stars at the same
center, one can obtain a decomposition of Kmn into hyperstars Sm001;:::;Sm00n, where m001  
    m00n, and each m00i , 1  i  n, is obtained by adding some of the mj?s, 1  j  ?.
Therefore by Case 1, it is necessary that for k = 1;:::;n 1
kX
i=1
mi 
kX
i=1
m00i  
 n
m
 
 
 n k
m
 
:
Now assume (i){(iii). Apply Lemma 4.4 ? n times to the sequence m1;:::;m? to obtain
a new sequence m01     m0n of positive integers with the property that for k = 1;:::;n 1
nX
i=1
m0i =
 n
m
 
and
kX
i=1
m0i 
 n
m
 
 
 n k
m
 
:
Applying Case 1 to m01;:::;m0n with C =ffv1g;:::;fvngg, we obtain anfSm0i : 1 i ng-
decomposition of Kmn . Note that each m0i is a sum of at least one of the mj?s. So for each
i2f1;:::;ng,Sm0i can be split into hyperstars with sizes in the setfm1;:::;m?g. Also, note
that m1;:::;m? are each included as a summand for some m0i, which means that for each
i2f1;:::;?g, Smi is a hyperstar in our decomposition. Thus, we have an fSmi : 1 i ?g
decomposition.
It is worth noting that Theorem 4.5 implies the result of Lin and Shyu, which is presented
as Theorem 1.4 in this work.
Corollary 4.6. Let m1      m? be positive integers. Then Kn can be decomposed into
stars Sm1;:::;Sm? if and only if
(1) ? n 1,
45
(2)
?X
i=1
mi =
 n
2
 
, and
(3)
kX
i=1
mi 
kX
i=1
(n i) for k = 1;2;:::;n 1.
Proof. Apply Theorem 4.5 with m = 2. There are obvious equivalencies between (i) and
(1), and between (ii) and (2). To show that (iii) and (3) are equivalent notice that for
k = 1;:::;n 1 we have:
kX
i=1
mi 
 n
2
 
 
 n k
2
 
=
 k
2
 
+k(n k) = nk k(k + 1)2 =
kX
i=1
(n i):
Hence, (iii) and (3) are equivalent.
4.3 Decomposing Complete Hypergraphs into Hyperstars
The complete hypergraph on n vertices has as its edge set all non-empty subsets of an
n-set. The number of hyperedges in this hypergraph is 2n 1. The main result of this section
is much like the main result of the last section, namely, the result for complete m-uniform
hypergraphs.
Theorem 4.7. Let m1     m? be positive integers. Then the hypergraph G = (V;P(V)n
?) with jVj= n 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.
Proof. Let V =fv1;:::;vng and C =ffv1g;:::;fvngg. There are two cases:
Case 1: ? = n. Let  (fvig) = mi for each i = 1;:::;n. By Theorem 4.2 there is an
fSmi : 1 i ng-decomposition of G if and only if
46
(1) P(E)
\
C 6= ? for all E2E,
(2) jEj=
X
C2C
 (C), and
(3) jT(E;C)j 
X
C2T
 (C) for all T  C.
The equivalence of (1) and (i) is due to the fact that we have all of the hyperedges of size
1 in our hypergraph. Thus, every vertex must be the center of at least one hyperstar. The
equivalence of (2) and (ii) is due to the fact thatjEj= 2n 1. Now, let T  C withjTj= k.
It is easy to see that jT(E;C)j = 2k 1, since T(E;C) = fE 2E : P1(E)TC  Tg =
fE2E : P1(E) Tg. By the same reasoning used in the proof of Case 1 of Theorem 4.5
we have (3) is equivalent with (iii).
Case 2: ? n+ 1. First suppose that G can be decomposed into hyperstars Sm1;:::;Sm?.
The necessity of (i) and (ii) is obvious. By combining all the stars at the same center, one
can obtain a decomposition of G into hyperstars Sm001;:::;Sm00n, where m001      m00n, and
each m00i , 1  i  n, is obtained by adding some of the mj?s, 1  j  ?. Therefore by
Case 1, it is necessary that for k = 1;2;:::;n 1,
kX
i=1
m00i  2k 1 which is equivalent to
nX
i=k+1
mi 
nX
i=k+1
m00i  2n 2k. Thus,
kX
i=1
mi 2k 1 for k = 1;2;:::;n 1.
Now assume (i){(iii). Let m01     m0? 1 be a rearrangement of m1 +m2;m3;:::;m?.
It is easy to see that
m0i =
8
><
>:
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 <n< 2k. Then there are 2n 2k 1 stars in a maximum
packing of Kn with k-stars. Moreover, the leave graph must be K2k n+1.
Result 3. 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 4. Let  ;n;k2N 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.
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