Abstract
We show that, for each natural numberk, these exists a (smallest) natural numberf(k) such that any digraph of minimum outdegree at leastf(k) containsk disjoint cycles. We conjecture thatf(k)=2k−1 and verify this fork=2 and we show that, for eachk≧3, the determination off(k) is a finite problem.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
J.-C. Bermond andC. Thomassen, Cycles in digraphs—a survey,J. Graph Theory 5 (1981), 1–43.
K. Corrádi andA. Hajnal, On the maximal number of independent circuits of a graph,Acta Math. Acad. Sci. Hungar 14 (1963), 423–443.
G. A. Dirac andP. Erdős, On the maximal number of independent circuits in a graph,Acta Math. Acad. Sci. Hungar 14 (1963), 79–94.
P. Erdős andL. Pósa, On independent circuits contained in a graph,Canad. J. Math. 17 (1965), 347–352.
S. Fortune, J. Hopcroft andJ. Wyllie, The directed subgraph homeomorphism problem,Theor. Comput. Sci. 10 (1980), 111–121.
R. Häggkvist, Equicardinal disjoint cycles in sparse graphs,to appear.
N. Robertson andP. D. Seymour,to appear.
C. Thomassen, Even cycles in digraphs,to appear.
C. Thomassen, Girth in graphs,J. Comb. Th., to appear.
Author information
Authors and Affiliations
Additional information
Dedicated to Paul Erdős on his seventieth birthday