Transversals of Longest Paths and Cycles

2013/02/22 by Dieter Rautenbach, Rautenbach, Dieter, Jean‐Sébastien Sereni +2 · 4 citations
Computer Science · Mathematics · #Advanced Graph Theory Research #Computational Geometry and Mesh Generation #Limits and Structures in Graph Theory #cs.DM #math.CO

paper · pdf · doi:10.48550/arxiv.1302.5503

arxiv created 2013/02/22 · arxiv updated 2013/02/25

Abstract

Let G be a graph of order n. Let lpt(G) be the minimum cardinality of a set X of vertices of G such that X intersects every longest path of G and define lct(G) analogously for cycles instead of paths. We prove that lpt(G) ≤ ceiling(n/4-n^2/3/90), if G is connected, lct(G) ≤ ceiling(n/3-n^2/3/36), if G is 2-connected, and \lpt(G) ≤ 3, if G is a connected circular arc graph. Our bound on lct(G) improves an earlier result of Thomassen and our bound for circular arc graphs relates to an earlier statement of Balister et al. the argument of which contains a gap. Furthermore, we prove upper bounds on lpt(G) for planar graphs and graphs of bounded tree-width.

Cited by

• Hitting all longest paths in H-free graphs and H-graphs
• Intersections of longest cycles in vertex-transitive and highly connected graphs
• Small hitting sets for longest paths and cycles
• Longest Paths in Circular Arc Graphs

Related

• Transversals of Longest Paths
• Transversals of Longest Cycles in Partial k-Trees and Chordal Graphs
• Small hitting sets for longest paths and cycles
• Hitting all longest paths in H-free graphs and H-graphs
• Intersecting longest paths in chordal graphs