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

Ajani De Vas Gunasekara¹ ; Daniel Horsley¹

¹Monash University

The electronic journal of combinatorics, Tome 30 (2023) no. 1

Résumé

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 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 < \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$.

Détail

DOI : 10.37236/10759

Classification : 05C70, 05C60, 05C51, 05B30
Mots-clés : embedding, 2-star decomposition