Connectivity for bridge-addable monotone graph classes

Details Connectivity for bridge-addable monotone graph classes Connectivity for bridge-addable monotone graph classes

2011-09-30

arxiv.org/abs/1110.0009v1

Mathematics

Combinatorics

11 pages

Scientific paper

A class A of labelled graphs is bridge-addable if for all graphs G in A and all vertices u and v in distinct connected components of G, the graph obtained by adding an edge between u and u is also in A; the class A is monotone if for all G in A and all subgraphs H of G, H is also in A. We show that for any bridge-addable, monotone class A whose elements have vertex set 1,...,n, the probability that a uniformly random element of A is connected is at least (1-o_n(1)) e^{-1/2}, where o_n(1) tends to zero as n tends to infinity. This establishes the special case of a conjecture of McDiarmid, Steger and Welsh when the condition of monotonicity is added. This result has also been obtained independently by Kang and Panagiotiou (2011).

Affiliated with

Also associated with

No associations

Rating

Connectivity for bridge-addable monotone graph classes 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 Connectivity for bridge-addable monotone graph classes, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Connectivity for bridge-addable monotone graph classes will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-236283