Girth, degree and transversals of longesth paths.
Hortensia Galeana Sánchez,
Ricardo Gómez and Juan José Montellano
AKCE International Journal of Graphs and Combinatorics 7, No. 1, (2010) 61-72.
Abstract. We provide conditions on the minimum degree, the girth and the length of a longest path for a digraph to have the following property: Every longest path intersects every maximal independent set. Digraphs with this property satisfy, in a strong sense, the Laborde-Payan-Xuong conjecture.