Journal article icon

Journal article

Random graphs with few disjoint cycles

Abstract:

The classical Erd\H{o}s-P\'{o}sa theorem states that for each positive integer k there is an f(k) such that, in each graph G which does not have k+1 disjoint cycles, there is a blocker of size at most f(k); that is, a set B of at most f(k) vertices such that G-B has no cycles. We show that, amongst all such graphs on vertex set {1,..,n}, all but an exponentially small proportion have a blocker of size k. We also give further properties of a random graph sampled uniformly from this class; conc...

Expand abstract
Publication status:
Published

Actions


Access Document


Publisher copy:
10.1017/S0963548311000186

Authors


Journal:
Probability and Computing
Volume:
20
Issue:
5
Pages:
763-775
Publication date:
2010-10-29
DOI:
EISSN:
1469-2163
ISSN:
0963-5483
URN:
uuid:620d4ee6-42c7-4630-be1a-a86beb87201b
Source identifiers:
102316
Local pid:
pubs:102316
Language:
English
Keywords:

Terms of use


Metrics


Views and Downloads






If you are the owner of this record, you can report an update to it here: Report update to this record

TO TOP