Sublinear Longest Path Transversals
Fuente:
arXiv
Salvato in:
| Autori principali: | , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2020
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866916699842805760 |
|---|---|
| author | Long Jr., James A. Milans, Kevin G. Munaro, Andrea |
| author_facet | Long Jr., James A. Milans, Kevin G. Munaro, Andrea |
| contents | We show that connected graphs admit sublinear longest path transversals. This improves an earlier result of Rautenbach and Sereni and is related to the fifty-year-old question of whether connected graphs admit longest path transversals of constant size. The same technique allows us to show that $2$-connected graphs admit sublinear longest cycle transversals. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2005_02716 |
| institution | arXiv |
| publishDate | 2020 |
| record_format | arxiv |
| spellingShingle | Sublinear Longest Path Transversals Long Jr., James A. Milans, Kevin G. Munaro, Andrea Combinatorics Discrete Mathematics We show that connected graphs admit sublinear longest path transversals. This improves an earlier result of Rautenbach and Sereni and is related to the fifty-year-old question of whether connected graphs admit longest path transversals of constant size. The same technique allows us to show that $2$-connected graphs admit sublinear longest cycle transversals. |
| title | Sublinear Longest Path Transversals |
| topic | Combinatorics Discrete Mathematics |
| url | https://arxiv.org/abs/2005.02716 |