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.