Connectivity for Bridge-Addable Monotone Graph Classes
- 30 July 2012
- journal article
- research article
- Published by Cambridge University Press (CUP) in Combinatorics, Probability and Computing
- Vol. 21 (6) , 803-815
Abstract
A class of labelled graphs isbridge-addableif, for all graphsGin and all verticesuandvin distinct connected components ofG, the graph obtained by adding an edge betweenuandvis also in ; the class ismonotoneif, for allG∈ and all subgraphsHofG, we haveH∈ . 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−½, whereon(1) → 0 asn→ ∞. 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.Keywords
This publication has 15 references indexed in Scilit:
- On the connectivity of random graphs from addable classesJournal of Combinatorial Theory, Series B, 2013
- Asymptotic enumeration and limit laws for graphs of fixed genusJournal of Combinatorial Theory, Series A, 2011
- 3-Connected Cores In Random Planar GraphsCombinatorics, Probability and Computing, 2011
- Growth constants of minor-closed classes of graphsJournal of Combinatorial Theory, Series B, 2010
- Counting planar graphs and related families of graphs2009
- Asymptotic enumeration and limit laws of planar graphsJournal of the American Mathematical Society, 2008
- Connectivity of addable graph classesJournal of Combinatorial Theory, Series B, 2008
- Enumeration and limit laws for series–parallel graphsEuropean Journal of Combinatorics, 2007
- Graph classes with given 3-connected components: asymptotic counting and critical phenomenaElectronic Notes in Discrete Mathematics, 2007
- Random planar graphsJournal of Combinatorial Theory, Series B, 2005