Random graphs with few disjoint cycles

Details Random graphs with few disjoint cycles Random graphs with few disjoint cycles

2010-10-29

arxiv.org/abs/1010.6278v1

Mathematics

Combinatorics

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Random graphs with few disjoint cycles does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Random graphs with few disjoint cycles, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Random graphs with few disjoint cycles will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-616174