Dirac's theorem for graphs of bounded bandwidth
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2024
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866917274872446976 |
|---|---|
| author | Díaz, Alberto Espuny Gupta, Pranshu Cecchelli, Domenico Mergoni Parczyk, Olaf Sgueglia, Amedeo |
| author_facet | Díaz, Alberto Espuny Gupta, Pranshu Cecchelli, Domenico Mergoni Parczyk, Olaf Sgueglia, Amedeo |
| contents | We provide an optimal sufficient condition, relating minimum degree and bandwidth, for a graph to contain a spanning subdivision of the complete bipartite graph $K_{2,\ell}$. This includes the containment of Hamilton paths and cycles, and has applications in the random geometric graph model. Our proof provides a greedy algorithm for constructing such structures. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2407_05889 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Dirac's theorem for graphs of bounded bandwidth Díaz, Alberto Espuny Gupta, Pranshu Cecchelli, Domenico Mergoni Parczyk, Olaf Sgueglia, Amedeo Combinatorics We provide an optimal sufficient condition, relating minimum degree and bandwidth, for a graph to contain a spanning subdivision of the complete bipartite graph $K_{2,\ell}$. This includes the containment of Hamilton paths and cycles, and has applications in the random geometric graph model. Our proof provides a greedy algorithm for constructing such structures. |
| title | Dirac's theorem for graphs of bounded bandwidth |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2407.05889 |