Name
Abstract | ||
|---|---|---|
A class of labelled graphs is bridge-addable if, for all graphs G in and all vertices u and v in distinct connected components of G, the graph obtained by adding an edge between u and v is also in ; the class is monotone if, for all G ∈ and all subgraphs H of G, we have H ∈ . We show that for any bridge-addable, monotone class whose elements have vertex set {1,.ï戮 .ï戮 .,n}, the probability that a graph chosen uniformly at random from is connected is at least (1-on(1))e-ï戮陆, where on(1) â聠聮 0 as n â聠聮 ∞. This establishes the special case of the conjecture of McDiarmid, Steger and Welsh when the condition of monotonicity is added. This result has also been obtained independently by Kang and Panagiotou. |
Year | DOI | Venue |
|---|---|---|
2012 | 10.1017/S0963548312000272 | Combinatorics, Probability & Computing |
Keywords | Field | DocType |
special case,labelled graph,graphs g,subgraphs h,distinct connected component,monotone class,vertices u,bridge-addable monotone graph class,connected component | Random regular graph,Discrete mathematics,Graph toughness,Modular decomposition,Combinatorics,Bound graph,Neighbourhood (graph theory),Algebraic connectivity,Strongly connected component,Mathematics,Complement graph | Journal |
Volume | Issue | ISSN |
21 | 6 | 0963-5483 |
Citations | PageRank | References |
8 | 1.12 | 8 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| L. Addario-Berry | 1 | 78 | 16.06 |
| Colin McDiarmid | 2 | 1071 | 167.05 |
| Bruce A. Reed | 3 | 1311 | 122.69 |