Independent sets which meet all longest paths (Q1917489): Difference between revisions
From MaRDI portal
Set profile property. |
ReferenceBot (talk | contribs) Changed an Item |
||
| Property / cites work | |||
| Property / cites work: Q4099676 / rank | |||
Normal rank | |||
| Property / cites work | |||
| Property / cites work: Une généralisation du théorème de Richardson sur l'existence de noyaux dans les graphes orientes / rank | |||
Normal rank | |||
| Property / cites work | |||
| Property / cites work: On kernels and semikernels of digraphs / rank | |||
Normal rank | |||
| Property / cites work | |||
| Property / cites work: On kernel-perfect critical digraphs / rank | |||
Normal rank | |||
| Property / cites work | |||
| Property / cites work: Q5545303 / rank | |||
Normal rank | |||
| Property / cites work | |||
| Property / cites work: Maximal chains and antichains / rank | |||
Normal rank | |||
| Property / cites work | |||
| Property / cites work: Q3309863 / rank | |||
Normal rank | |||
| Property / cites work | |||
| Property / cites work: Nombre chromatique et plus longs chemins d'un graphe / rank | |||
Normal rank | |||
Latest revision as of 13:12, 24 May 2024
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
