Smaller embeddings of partial k-star decompositions

A k-star is a complete bipartite graph K_1,k. For a graph G, a k-star decomposition of G is a set of k-stars in G whose edge sets partition the edge set of G. If we weaken this condition to only demand that each edge of G is in at most one k-star, then the resulting object is a partial k-star decomposition of G. An embedding of a partial k-star decomposition A of a graph G is a partial k-star decomposition B of another graph H such that A ⊆ B and G is a subgraph of H. This paper considers the problem of when a partial k-star decomposition of K_n can be embedded in a k-star decomposition of K_n+s for a given integer s. We improve a result of Noble and Richardson, itself an improvement of a result of Hoffman and Roberts, by showing that any partial k-star decomposition of K_n can be embedded in a k-star decomposition of K_n+s for some s such that (formula presented) whenkis odd ands (formula presented) when k is even. For general k, these constants cannot be improved. We also obtain stronger results subject to placing a lower bound on n.