Longest Path and Cycle Transversals in Chordal Graphs
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_ | 1866910766471315456 |
|---|---|
| author | Long Jr., James A. Milans, Kevin G. Wigal, Michael C. |
| author_facet | Long Jr., James A. Milans, Kevin G. Wigal, Michael C. |
| contents | We show that if $G$ is a $n$-vertex connected chordal graph, then it admits a longest path transversal of size $O(\log^2 n)$. Under the stronger assumption of 2-connectivity, we show $G$ admits a longest cycle transversal of size $O(\log n)$. We also provide longest path and longest cycle transversals which are bounded by the leafage of the chordal graph. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2412_20729 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Longest Path and Cycle Transversals in Chordal Graphs Long Jr., James A. Milans, Kevin G. Wigal, Michael C. Combinatorics 05C38 (Primary) 05C35 (Secondary) We show that if $G$ is a $n$-vertex connected chordal graph, then it admits a longest path transversal of size $O(\log^2 n)$. Under the stronger assumption of 2-connectivity, we show $G$ admits a longest cycle transversal of size $O(\log n)$. We also provide longest path and longest cycle transversals which are bounded by the leafage of the chordal graph. |
| title | Longest Path and Cycle Transversals in Chordal Graphs |
| topic | Combinatorics 05C38 (Primary) 05C35 (Secondary) |
| url | https://arxiv.org/abs/2412.20729 |