Intersecting longest paths in chordal graphs
| Autor: | Harvey, Daniel J., Payne, Michael S. |
|---|---|
| Rok vydání: | 2020 |
| Předmět: | |
| Druh dokumentu: | Working Paper |
| Popis: | We consider the size of the smallest set of vertices required to intersect every longest path in a chordal graph. Such sets are known as longest path transversals. We show that if $\omega(G)$ is the clique number of a chordal graph $G$, then there is a transversal of order at most $4\lceil\frac{\omega(G)}{5}\rceil$. We also consider the analogous question for longest cycles, and show that if $G$ is a 2-connected chordal graph then there is a transversal intersecting all longest cycles of order at most $2\lceil\frac{\omega(G)}{3}\rceil$. Comment: 11 pages |
| Databáze: | arXiv |
| Externí odkaz: |
|