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...

Publication status:
Published

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: