For a connected graph G, the longest path transversal number of G, denoted by lpt(G), is the minimum cardinality of a set of vertices that intersects all longest paths in G. It is an open problem whether any graph admits a longest path transversal of constant size. This question remains open even when restricted to claw-free graphs and \(P_5\) -free graphs. In this work, we investigate these two graph classes. We show that, given a connected graph G, \(lpt(G)=1\) if G is a \((P_5, H)\) -free graph, when H is a triangle, a paw, or a diamond. We also provide a complete characterization of the graphs H on at most five vertices for which for any (claw, H)-free graph G it holds that \(lpt(G)=1\) . Moreover, in each of these cases, we present a polynomial-time algorithm which finds a vertex in G that belongs to all its longest paths.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Longest Path Transversals in Claw-Free and  \(P_5\) -Free Graphs

  • Paloma T. Lima,
  • Amir Nikabadi

摘要

For a connected graph G, the longest path transversal number of G, denoted by lpt(G), is the minimum cardinality of a set of vertices that intersects all longest paths in G. It is an open problem whether any graph admits a longest path transversal of constant size. This question remains open even when restricted to claw-free graphs and \(P_5\) -free graphs. In this work, we investigate these two graph classes. We show that, given a connected graph G, \(lpt(G)=1\) if G is a \((P_5, H)\) -free graph, when H is a triangle, a paw, or a diamond. We also provide a complete characterization of the graphs H on at most five vertices for which for any (claw, H)-free graph G it holds that \(lpt(G)=1\) . Moreover, in each of these cases, we present a polynomial-time algorithm which finds a vertex in G that belongs to all its longest paths.