Independent sets which meet all longest paths (Q1917489)
From MaRDI portal
 | This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: Independent sets which meet all longest paths |
scientific article; zbMATH DE number 897573
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Independent sets which meet all longest paths |
scientific article; zbMATH DE number 897573 |
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
0.8798193
0 references
0 references
0.85392594
0 references
0.83886963
0 references
0.8366748
0 references
0 references
0.82958066
0 references
