Smaller embeddings of partial k-star decompositions

DOI10.37236/10759MaRDI QIDQ6378755arXivFDO

Authors Ajani De Vas Gunasekara, Daniel Horsley

Publication date 28 September 2021

Published in arXiv

Full work available at URL https://doi.org/10.37236/10759

Mathematics Subject Classification ID

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)

arXiv classification

math.CO

Abstract: 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 $mathcalA$ of a graph $G$ is a partial $k$-star decomposition $mathcalB$ of another graph $H$ such that $mathcalAsubseteqmathcalB$ 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 Noble and Richardson, itself an improvement of a result of Hoffman and Roberts, 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<frac94k$ when $k$ is odd and $s<(6-2sqrt2)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$.

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 Q6378755)