Smaller embeddings of partial k-star decompositions
Other designs, configurations (05B30) Graph designs and isomorphic decomposition (05C51) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)
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\).
- Embedding partial k-star designs
- Balls, bins, and embeddings of partial \(k\)-star designs
- Star decomposition of graphs
- Balanced star decompositions of regular multigraphs and \(\lambda\)-fold complete bipartite graphs
- A decomposition of complete bipartite graphs into edge-disjoint subgraphs with star components
- Balls, bins, and embeddings of partial \(k\)-star designs
- Decomposition of complete multigraphs into stars
- Decompositions of complete multigraphs into stars of varying sizes
- Embedding partial k-star designs
- Graph Decomposition is NP-Complete: A Complete Proof of Holyer's Conjecture
- scientific article; zbMATH DE number 4010553 (Why is no real title available?)
- scientific article; zbMATH DE number 3710196 (Why is no real title available?)
- Maximum packings of K_n with k-stars
- On claw-decomposition of complete graphs and complete bigraphs
- On the decomposition of a graph into stars
- The real truth about star designs
This page was built for publication: Smaller embeddings of partial \(k\)-star decompositions
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2684891)
