Smaller embeddings of partial k-star decompositions

Ajani De Vas Gunasekara, Daniel Horsley

Research output: Contribution to journalArticleResearchpeer-review

Abstract

A k-star is a complete bipartite graph K1,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 Kn can be embedded in a k-star decomposition of Kn+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 Kn can be embedded in a k-star decomposition of Kn+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.

Original languageEnglish
Article numberP1.19
Number of pages20
JournalThe Electronic Journal of Combinatorics
Volume30
Issue number1
DOIs
Publication statusPublished - 2023

Cite this