Back to Search
Start Over
Transversals of Longest Paths.
- Source :
- Electronic Notes in Discrete Mathematics; Nov2017, Vol. 62, p135-140, 6p
- Publication Year :
- 2017
-
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. [ABSTRACT FROM AUTHOR]
Details
- Language :
- English
- ISSN :
- 15710653
- Volume :
- 62
- Database :
- Supplemental Index
- Journal :
- Electronic Notes in Discrete Mathematics
- Publication Type :
- Academic Journal
- Accession number :
- 125922133
- Full Text :
- https://doi.org/10.1016/j.endm.2017.10.024