Connectivity of addable graph classes

DOI10.1016/J.JCTB.2007.09.003MaRDI QIDQ2483480zbMATH OpenOpenAlexFDO

Authors Béla Bollobás, Stefanie Gerke, Paul Balister

Publication date 28 April 2008

Published in Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.jctb.2007.09.003

zbMATH Keywords

connectivityplanar and other addable graph classes

Mathematics Subject Classification ID

Trees (05C05) Connectivity (05C40) Random graphs (graph-theoretic aspects) (05C80)

Review text

A non-empty class \(A\) of labeled graphs is weakly addable if the class is closed under the joining of an edge between any two distinct components in a graph of the class. Consider a non-empty subclass of \(A\) containing the graphs of \(n\) specified vertices. For sufficiently large \(n\), a new lower bound is given for the probability that a graph drawn uniformly at random from the subclass is connected. By extending the notion of addability to closeness under the addition of at most two edges between any two distinct components of a graph, it is proved that the random graph is connected with probability 1 as \(n\) tends to infinity.

Recommendations

• On the connectivity of random graphs from addable classes
• Connectivity for Bridge-addable monotone graph classes
• Connectivity of addition Cayley graphs
• Connectivity of random addable graphs
• The Connectivity of addition Cayley graphs
• Relatively Bridge-Addable Classes of Graphs
• Connectivity for bridge-alterable graph classes
• Connectivity in bridge-addable graph classes: the McDiarmid-Steger-Welsh conjecture
• Connectivity in bridge-addable graph classes: the McDiarmid-Steger-Welsh conjecture
• scientific article; zbMATH DE number 4023324

Cites work

• scientific article; zbMATH DE number 3152798 (Why is no real title available?)
• scientific article; zbMATH DE number 5130821 (Why is no real title available?)
• Random planar graphs
• The generalized Randić index of trees

Cited in

(11)

• Connectivity in bridge-addable graph classes: the McDiarmid-Steger-Welsh conjecture
• Connectivity for bridge-alterable graph classes
• Connectivity of random addable graphs
• Connectivity for Bridge-addable monotone graph classes
• Random graphs from a minor-closed class
• 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
• Longest and shortest cycles in random planar graphs

This page was built for publication: Connectivity of addable graph classes

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