On perfect subdivision tilings
Fuente:
arXiv
Guardado en:
| Autor principal: | |
|---|---|
| Formato: | Preprint |
| Publicado: |
2023
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866910920988426240 |
|---|---|
| author | Lee, Hyunwoo |
| author_facet | Lee, Hyunwoo |
| contents | 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 $δ_{\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 $δ_{\mathrm{sub}}(n, H)$. More precisely, for every graph $H$ with at least one edge, there is an integer $\mathrm{hcf}_ξ(H)$ and a constant $1 < ξ^*(H)\leq 2$ that can be explicitly determined by structural properties of $H$ such that $δ_{\mathrm{sub}}(n, H) = \left(1 - \frac{1}{ξ^*(H)} + o(1) \right)n$ holds for all $n$ and $H$ unless $\mathrm{hcf}_ξ(H) = 2$ and $n$ is odd. When $\mathrm{hcf}_ξ(H) = 2$ and $n$ is odd, then we show that $δ_{\mathrm{sub}}(n, H) = \left(\frac{1}{2} + o(1) \right)n$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2302_09393 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | On perfect subdivision tilings Lee, Hyunwoo Combinatorics 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 $δ_{\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 $δ_{\mathrm{sub}}(n, H)$. More precisely, for every graph $H$ with at least one edge, there is an integer $\mathrm{hcf}_ξ(H)$ and a constant $1 < ξ^*(H)\leq 2$ that can be explicitly determined by structural properties of $H$ such that $δ_{\mathrm{sub}}(n, H) = \left(1 - \frac{1}{ξ^*(H)} + o(1) \right)n$ holds for all $n$ and $H$ unless $\mathrm{hcf}_ξ(H) = 2$ and $n$ is odd. When $\mathrm{hcf}_ξ(H) = 2$ and $n$ is odd, then we show that $δ_{\mathrm{sub}}(n, H) = \left(\frac{1}{2} + o(1) \right)n$. |
| title | On perfect subdivision tilings |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2302.09393 |