Article ID Journal Published Year Pages File Type
8903503 Electronic Notes in Discrete Mathematics 2017 6 Pages PDF
Abstract
Let lpt(G) be the minimum cardinality of a set of vertices that intersects all longest paths in a connected graph G. We show that, if G is a chordal graph, then lpt(G)≤max⁡{1,ω(G)−2}, where ω(G) is the size of a largest clique in G; that lpt(G)≤tw(G), where tw(G) is the treewidth of G; and that lpt(G)=1 if G is a bipartite permutation graph or a full substar graph.
Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Authors
, , , , ,