Independent sets which meet all longest paths
A directed graph is said to have property \(P\) if it contains an independent set which meets every longest directed path. In 1982, \textit{J. M. Laborde}, \textit{Ch. Payan} and \textit{Nguyen Huy Xuong} [Teubner-Texte Math. 59, 173-177 (1983; Zbl 0528.05034)] conjectured that every directed graph has property \(P\). In this paper, the authors prove some sufficient conditions for a directed graph to have property \(P\).
scientific article; zbMATH DE number 897573
scientific article