Independent sets which meet all longest paths (Q1917489)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Independent sets which meet all longest paths |
scientific article |
Statements
Independent sets which meet all longest paths (English)
0 references
7 July 1996
0 references
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\).
0 references
property \(P\)
0 references
independent set
0 references
longest directed path
0 references
0 references