Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
8903503 | Electronic Notes in Discrete Mathematics | 2017 | 6 Pages |
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
Márcia R. Cerioli, Cristina G. Fernandes, Renzo Gómez, Juan Gutiérrez, Paloma T. Lima,