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 $\delta _{\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 $\delta _{\mathrm {sub}}(n, H)$ . More precisely, for every graph $H$ with at least one edge, there is an integer $\mathrm {hcf}_{\xi }(H)$ and a constant $1 \lt \xi ^*(H)\leq 2$ that can be explicitly determined by structural properties of $H$ such that $\delta _{\mathrm {sub}}(n, H) = \left (1 - \frac {1}{\xi ^*(H)} + o(1) \right )n$ holds for all $n$ and $H$ unless $\mathrm {hcf}_{\xi }(H) = 2$ and $n$ is odd. When $\mathrm {hcf}_{\xi }(H) = 2$ and $n$ is odd, then we show that $\delta _{\mathrm {sub}}(n, H) = \left (\frac {1}{2} + o(1) \right )n$ .
Authors
- Hyun-Woo Lee (ORCID: https://orcid.org/0009-0003-7212-2162)
Institutions
- Institute for Basic Science (KR)
Publication Details
- Journal
- Combinatorics Probability Computing
- Published
- 2025-01-27
- DOI
- https://doi.org/10.1017/s0963548324000452
- Primary Topic
- Quasicrystal Structures and Properties
- Type
- article
- Field-Weighted Citation Impact
- 0.00