A note on short cycles in digraphs (Q580357)
From MaRDI portal
scientific article
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | A note on short cycles in digraphs |
scientific article |
Statements
A note on short cycles in digraphs (English)
0 references
1987
0 references
Caccetta and Häggkvist have conjected that a directed graph \(D_ n\) with minimum out-degree k must contain a directed cycle of length at most \(\lceil n/k\rceil\). The conjecture is known to be true when \(k\leq 3\). The authors of the present paper describe a proof for the cases when \(k\leq 5\).
0 references
digraph
0 references
dicycle
0 references
short cycles
0 references
degrees
0 references
directed graph
0 references
directed cycle
0 references
