Connectivity for Bridge-addable monotone graph classes

DOI10.1017/S0963548312000272MaRDI QIDQ3168442zbMATH OpenFDO

Authors Louigi Addario-Berry, Colin McDiarmid, Bruce Reed

Publication date 31 October 2012

Published in Combinatorics, Probability and Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1110.0009

zbMATH Keywords

addable graph classesprobabilistic results

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Connectivity (05C40) Structural characterization of families of graphs (05C75) Random graphs (graph-theoretic aspects) (05C80) Combinatorial probability (60C05)

Abstract: 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).

Recommendations

• Connectivity in bridge-addable graph classes: the McDiarmid-Steger-Welsh conjecture
• On the connectivity of random graphs from addable classes
• Connectivity in bridge-addable graph classes: the McDiarmid-Steger-Welsh conjecture
• Bridge-addability, edge-expansion and connectivity
• Connectivity of random addable graphs

Cites work

• 3-Connected Cores In Random Planar Graphs
• Asymptotic enumeration and limit laws for graphs of fixed genus
• Connectivity of addable graph classes
• Enumeration and limit laws for series-parallel graphs
• Graph classes with given 3-connected components: asymptotic counting and critical phenomena
• Growth constants of minor-closed classes of graphs
• scientific article; zbMATH DE number 3340110 (Why is no real title available?)
• Random planar graphs

Cited in

(15)

• Logical limit laws for minor-closed classes of graphs
• On the connectivity of random graphs from addable classes
• Connectivity for random graphs from a weighted bridge-addable class
• Connectivity in bridge-addable graph classes: the McDiarmid-Steger-Welsh conjecture
• Connectivity of addable graph classes
• Connectivity for bridge-alterable graph classes
• Connectivity of random addable graphs
• Asymptotic Properties of Some Minor-Closed Classes of Graphs
• Connectivity in bridge-addable graph classes: the McDiarmid-Steger-Welsh conjecture
• The Evolution of Random Graphs on Surfaces
• Local convergence and stability of tight bridge-addable classes
• Logical properties of random graphs from small addable classes
• Bridge-addability, edge-expansion and connectivity
• Relatively Bridge-Addable Classes of Graphs
• Random graphs from a block-stable class

This page was built for publication: Connectivity for Bridge-addable monotone graph classes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3168442)