Transversals of longest paths

Abstract Let lpt ( G ) be the minimum cardinality of a transversal of longest paths in G , that is, a set of vertices that intersects all longest paths in a graph  G . There are several results in the literature bounding the value of lpt ( G ) in general or in specific classes of graphs. For instance, lpt ( G ) = 1 if G is a connected partial 2-tree, and a connected partial 3-tree  G is known with lpt ( G ) = 2 . We prove that lpt ( G ) ≤ 3 for every connected partial 3-tree  G ; that lpt ( G ) ≤ 2 for every planar 3-tree G ; and that lpt ( G ) = 1 if  G is a connected bipartite permutation graph or a connected full substar graph. Our first two results can be adapted for broader classes, improving slightly some known general results: we prove that lpt ( G ) ≤ k for every connected partial k -tree G and that lpt ( G ) ≤ max { 1 , ω ( G ) − 2 } for every connected chordal graph G , where ω ( G ) is the cardinality of a maximum clique in G .