Embedding partial 3-star designs

Noble, Matt (Middle Georgia State University)
Nochumson, Shayne (Auburn University)

Electronic Journal of Graph Theory and Applications (EJGTA)
Vol 12, No 2 (2024): Electronic Journal of Graph Theory and Applications

Define a 3-star decomposition of Kn as being a collection of subgraphs, each isomorphic to K1,3, with the property that each edge of Kn 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 Kn can be embedded into a decomposition of Kn+s where s ≤ 4. Furthermore, we determine, for any maximal partial 3-star decomposition P of Kn, the minimum s ∈{1,2,3,4} such that P can be embedded into a decomposition of Kn+s.