Disjoint directed cycles

Noga Alon

doi:10.1006/jctb.1996.0062

Disjoint directed cycles

Noga Alon

Research output: Contribution to journal › Article › peer-review

42 Scopus citations

Abstract

It is shown that there exists a positive ε so that for any integer k, every directed graph with minimum outdegree at least k contains at least ε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.

Original language	English (US)
Pages (from-to)	167-178
Number of pages	12
Journal	Journal of Combinatorial Theory. Series B
Volume	68
Issue number	2
DOIs	https://doi.org/10.1006/jctb.1996.0062
State	Published - Nov 1996
Externally published	Yes

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
Discrete Mathematics and Combinatorics
Computational Theory and Mathematics

Access to Document

10.1006/jctb.1996.0062

Cite this

@article{e60cca2f0e984a428cade1d4ba00b46b,

title = "Disjoint directed cycles",

abstract = "It is shown that there exists a positive ε so that for any integer k, every directed graph with minimum outdegree at least k contains at least ε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.",

author = "Noga Alon",

note = "Funding Information: * E-mail: noga math.tau.ac.il. Research supported in part by U.S.A. Israel BSF grant and by the Fund for Basic Research administered by the Israel Academy of Sciences.",

year = "1996",

month = nov,

doi = "10.1006/jctb.1996.0062",

language = "English (US)",

volume = "68",

pages = "167--178",

journal = "Journal of Combinatorial Theory. Series B",

issn = "0095-8956",

publisher = "Academic Press Inc.",

number = "2",

}

TY - JOUR

T1 - Disjoint directed cycles

AU - Alon, Noga

N1 - Funding Information: * E-mail: noga math.tau.ac.il. Research supported in part by U.S.A. Israel BSF grant and by the Fund for Basic Research administered by the Israel Academy of Sciences.

PY - 1996/11

Y1 - 1996/11

N2 - It is shown that there exists a positive ε so that for any integer k, every directed graph with minimum outdegree at least k contains at least ε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.

AB - It is shown that there exists a positive ε so that for any integer k, every directed graph with minimum outdegree at least k contains at least ε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.

UR - https://www.scopus.com/pages/publications/0030295782

UR - https://www.scopus.com/pages/publications/0030295782#tab=citedBy

U2 - 10.1006/jctb.1996.0062

DO - 10.1006/jctb.1996.0062

M3 - Article

AN - SCOPUS:0030295782

SN - 0095-8956

VL - 68

SP - 167

EP - 178

JO - Journal of Combinatorial Theory. Series B

JF - Journal of Combinatorial Theory. Series B

IS - 2

ER -

Disjoint directed cycles

Abstract

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this