Density of Traceable Graphs
Fuente:
arXiv
Guardado en:
| Autores principales: | , , , , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2025
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866909765215453184 |
|---|---|
| author | Dvořák, Michal Knop, Dušan Opler, Michal Pokorný, Jan Suchý, Ondřej Szilágyi, Krisztina |
| author_facet | Dvořák, Michal Knop, Dušan Opler, Michal Pokorný, Jan Suchý, Ondřej Szilágyi, Krisztina |
| contents | We establish tight lower and upper bounds on the number of edges in traceable graphs in several classes of dense graphs. A graph is traceable if it has a Hamiltonian path. We show that the bound is: - quadratic for the class of graphs of bounded neighborhood diversity, bounded size of maximum induced matching or bounded cluster vertex deletion number; - n log n for the class of cographs or, more generaly, bounded modular-width, and for the class of bounded distance to cograph; and - sligthly superlinear for the class of bounded shrub-depth. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2506_22269 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Density of Traceable Graphs Dvořák, Michal Knop, Dušan Opler, Michal Pokorný, Jan Suchý, Ondřej Szilágyi, Krisztina Combinatorics We establish tight lower and upper bounds on the number of edges in traceable graphs in several classes of dense graphs. A graph is traceable if it has a Hamiltonian path. We show that the bound is: - quadratic for the class of graphs of bounded neighborhood diversity, bounded size of maximum induced matching or bounded cluster vertex deletion number; - n log n for the class of cographs or, more generaly, bounded modular-width, and for the class of bounded distance to cograph; and - sligthly superlinear for the class of bounded shrub-depth. |
| title | Density of Traceable Graphs |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2506.22269 |