2025/10/20 by Paloma T. Lima, de Lima, Paloma T., Amir Nikabadi +3
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #Complexity and Algorithms in Graphs #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Limits and Structures in Graph Theory
paper · pdf · doi:10.48550/arxiv.2510.17312
openalex publication_date 2025/10/20 · openalex created_date 2025/10/22 · openalex updated_date 2026/07/28
The longest path transversal number of a connected graph G, denoted by lpt(G), is the minimum size of a set of vertices of G that intersects all longest paths in G. We present constant upper bounds for the longest path transversal number of hereditary classes of graphs, that is, classes of graphs closed under taking induced subgraphs. Our first main result is a structural theorem that allows us to refine a given longest path transversal in a graph using domination properties. This has several consequences: First, it implies that for every t ∈ \5,6\, every connected Pt-free graph G satisfies lpt(G) ≤ t-2. Second, it shows that every (bull, chair)-free graph G satisfies lpt(G) ≤ 5. Third, it implies that for every t ∈ ℕ, every connected chordal graph G with no induced subgraph isomorphic to Kt \mat Kt satisfies lpt(G) ≤ t-1, where Kt \mat Kt is the graph obtained from a t-clique and an independent set of size t by adding a perfect matching between them. Our second main result provides an upper bound for the longest path transversal number in H-intersection graphs. For a given graph H, a graph G is called an H-graph if there exists a subdivision H' of H such that G is the intersection graph of a family of vertex subsets of H' that each induce connected subgraphs. The concept of H-graphs, introduced by Biró, Hujter, and Tuza, naturally captures interval graphs, circular-arc graphs, and chordal graphs, among others. Our result shows that for every connected graph H with at least two vertices, there exists an integer k = k(H) such that every connected H-graph G satisfies lpt(G) ≤ k.