Longest Path and Cycle Transversals in Chordal Graphs

2024/12/30 by Long, James A., Milans, Kevin G., Wigal, Michael C. · 1 citation
#05C38 (Primary) 05C35 (Secondary) #Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.2412.20729

Abstract

We show that if G is a n-vertex connected chordal graph, then it admits a longest path transversal of size O(log² 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.

Cited by

• Hitting all longest paths in H-free graphs and H-graphs

Related

• Intersecting longest paths in chordal graphs
• Transversals of Longest Paths
• Chords of longest cycles in graphs with large circumferences
• Optimal-size clique transversals in chordal graphs
• Chords of longest cycles passing through a specified small set