2020/12/14 by Daniel J. Harvey, Harvey, Daniel J., Michael S. Payne +1 · 1 citation
Computer Science · Mathematics · #Advanced Graph Theory Research #Interconnection Networks and Systems #Limits and Structures in Graph Theory
paper · pdf · doi:10.48550/arxiv.2012.07221
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 ω(G) is the clique number of a chordal graph G, then there is a transversal of order at most 4\lceil(ω(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(ω(G))/(3)\rceil.