Embedding partial 3-star designs

Abstract

Define a 3-star decomposition of K_n as being a collection of subgraphs, each isomorphic to K_1,3, with the property that each edge of K_n appears in exactly one of the subgraphs. A partial 3-star decomposition is similarly defined except each edge appears in at most one of the subgraphs. In this work, it is shown that any partial 3-star decomposition of K_n can be embedded into a decomposition of K_n+s where s ≤ 4. Furthermore, we determine, for any maximal partial 3-star decomposition P of K_n, the minimum s ∈{1,2,3,4} such that P can be embedded into a decomposition of K_n+s.