Disjoint directed cycles (Q1125942)

From MaRDI portal
Revision as of 09:35, 20 March 2024 by Openalex240320080334 (talk | contribs) (Set OpenAlex properties.)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
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
    0 references
    probabilistic method
    0 references
    digraph
    0 references
    disjoint cycles
    0 references
    0 references
    0 references
    0 references