Smaller embeddings of partial \(k\)-star decompositions (Q2684891)

Summary: 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 \(\mathcal{A}\) of a graph \(G\) is a partial \(k\)-star decomposition \(\mathcal{B}\) of another graph \(H\) such that \(\mathcal{A} \subseteq \mathcal{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 \textit{M. Noble} and \textit{S. N. Richardson} [Discrete Math. 342, No. 12, Article ID 111600, 4 p. (2019; Zbl 1422.05087)], itself an improvement of a result of \textit{D. G. Hoffman} and \textit{D. Roberts} [J. Comb. Des. 22, No. 4, 161--170 (2014; Zbl 1290.05120)], 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 \(s < \frac{9}{4}k\) when \(k\) is odd and \(s < (6-2\sqrt{2})k\) 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\).