Random graphs with few disjoint cycles


Kurauskas, V
McDiarmid, C


Combinatorics, Probability and Computing

Last Updated: 







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; concerning uniqueness of the blocker,
connectivity, chromatic number and clique number. A key step in the proof of
the main theorem is to show that there must be a blocker as in the
Erd\H{o}s-P\'{o}sa theorem with the extra `redundancy' property that B-v is
still a blocker for all but at most k vertices v in B.

Symplectic id: 


Download URL: 

Submitted to ORA: 

Not Submitted

Publication Type: 

Journal Article