Faces in girth-saturated graphs on surfaces
Fuente:
arXiv
Guardado en:
| Autores principales: | , , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2024
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866915292206071808 |
|---|---|
| author | Axenovich, Maria Kießle, Leon Sagdeev, Arsenii Zhukovskii, Maksim |
| author_facet | Axenovich, Maria Kießle, Leon Sagdeev, Arsenii Zhukovskii, Maksim |
| contents | What is the maximum length ${\rm f}_{\rm max}(\ell, Σ)$ of a facial cycle of an inclusion-maximal graph with girth at least $\ell$ embedded on a given surface $Σ$? If $Σ=\mathcal{P}$ is a plane, we show that $3\ell-11\leq {\rm f}_{\rm max}(\ell, \mathcal{P})\leq 8\ell-13$. We also prove that ${\rm f}_{\rm max}(\ell, Σ)$ is bounded for any integer $\ell$ and any closed surface $Σ$. For a fixed $Σ$, we show that $Ω(\ell) ={\rm f}_{\rm max}(\ell, Σ) = O(\ell^2)$, while for a fixed $\ell\ge 6$, ${\rm f}_{\rm max}(\ell, Σ)=Θ(g)$, where $g$ is the genus of $Σ$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2410_13481 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Faces in girth-saturated graphs on surfaces Axenovich, Maria Kießle, Leon Sagdeev, Arsenii Zhukovskii, Maksim Combinatorics 05C10, 05C35, 57M15 What is the maximum length ${\rm f}_{\rm max}(\ell, Σ)$ of a facial cycle of an inclusion-maximal graph with girth at least $\ell$ embedded on a given surface $Σ$? If $Σ=\mathcal{P}$ is a plane, we show that $3\ell-11\leq {\rm f}_{\rm max}(\ell, \mathcal{P})\leq 8\ell-13$. We also prove that ${\rm f}_{\rm max}(\ell, Σ)$ is bounded for any integer $\ell$ and any closed surface $Σ$. For a fixed $Σ$, we show that $Ω(\ell) ={\rm f}_{\rm max}(\ell, Σ) = O(\ell^2)$, while for a fixed $\ell\ge 6$, ${\rm f}_{\rm max}(\ell, Σ)=Θ(g)$, where $g$ is the genus of $Σ$. |
| title | Faces in girth-saturated graphs on surfaces |
| topic | Combinatorics 05C10, 05C35, 57M15 |
| url | https://arxiv.org/abs/2410.13481 |