Intersection of longest paths in graph classes

Abstract

The problem of the intersection of longest paths consists in determining the size of a smallest subset of vertices of a graph such that every longest path contains at least one vertex of the set. Given a graph G, we denote the size of this subset by lpt(G). In this work, we show a number of results that enable us to conclude that lpt(G)=1 if G is a chain graph, a P4-sparse graph, a starlike graph, a (P5,K1,3)-free graph, a graph that is the join of two other graphs or a graph whose blocks are split graphs, interval graphs or graphs with a universal vertex. We also provide upper bounds on lpt(G) for (P5,cricket)-free graphs and graphs that are intersection graphs of subtrees of a spider graph.