Disjoint directed cycles (Q1125942): Difference between revisions
From MaRDI portal
Set profile property. |
Set OpenAlex properties. |
||
(2 intermediate revisions by 2 users not shown) | |||
Property / full work available at URL | |||
Property / full work available at URL: https://doi.org/10.1006/jctb.1996.0062 / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W1974181313 / rank | |||
Normal rank |
Latest revision as of 09:35, 20 March 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Disjoint directed cycles |
scientific article |
Statements
Disjoint directed cycles (English)
0 references
8 December 1996
0 references
It is shown that there exists a positive \(\varepsilon\) so that for any integer \(k\), every directed graph with minimum outdegree at least \(k\) contains at least \(\varepsilon k\) vertex disjoint cycles. On the other hand, for every \(k\) there is a digraph with minimum outdegree \(k\) which does not contain two vertex or edge disjoint cycles of the same length.
0 references
probabilistic method
0 references
digraph
0 references
disjoint cycles
0 references