Name
Abstract | ||
|---|---|---|
A class of graphs is bridge-addable if given a graph G in the class, any graph obtained by adding an edge between two connected components of G is also in the class. We prove a conjecture of McDiarmid, Steger, and Welsh, that says that if Gn is any bridge-addable class of graphs on n vertices, and Gn is taken uniformly at random from Gn, then Gn is connected with probability at least e−12+o(1), when n tends to infinity. This lower bound is asymptotically best possible since it is reached for forests. |
Year | DOI | Venue |
|---|---|---|
2019 | 10.1016/j.jctb.2018.09.004 | Journal of Combinatorial Theory, Series B |
Keywords | DocType | Volume |
Bridge-addable classes,Random graphs,Random forests,Connectivity | Journal | 136 |
ISSN | Citations | PageRank |
0095-8956 | 0 | 0.34 |
References | Authors | |
0 | 2 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Guillaume Chapuy | 1 | 73 | 11.25 |
| Guillem Perarnau | 2 | 51 | 13.17 |