On perfect subdivision tilings

Abstract

For a given graph $H$, we say that a graph $G$ has a perfect $H$-subdivision tiling if $G$ contains a collection of vertex-disjoint subdivisions of $H$ covering all vertices of $G.$ Let $\hat{I}{´}_{\mathrm{sub}}(n,H)$ be the smallest integer $k$ such that any $n$-vertex graph $G$ with minimum degree at least $k$ has a perfect $H$-subdivision tiling. For every graph $H$, we asymptotically determined the value of $\hat{I}{´}_{\mathrm{sub}}(n,H)$. More precisely, for every graph $H$ with at least one edge, there is an integer ${\mathrm{hcf}}_{\hat{I}}¾(H)$ and a constant $1<\hat{I}{¾}^{\ast }(H)\le 2$ that can be explicitly determined by structural properties of $H$ such that $\hat{I}{´}_{\mathrm{sub}}(n,H)=\left(1-\frac{1}{\hat{I}{¾}^{\ast }(H)}+o(1)\right)n$ holds for all $n$ and $H$ unless ${\mathrm{hcf}}_{\hat{I}}¾(H)=2$ and $n$ is odd. When ${\mathrm{hcf}}_{\hat{I}}¾(H)=2$ and $n$ is odd, then we show that $\hat{I}{´}_{\mathrm{sub}}(n,H)=\left(\frac{1}{2}+o(1)\right)n$.

Accepted version