Loading...
Loading...

Go to the content (press return)

Connectivity in bridge-addable graph classes: the McDiarmid-Steger-Welsh conjecture

Author
Chapuy, G.; Perarnau-Llobet, G.
Type of activity
Journal article
Journal
Journal of combinatorial theory. Series B
Date of publication
2018-09-17
Volume
136
First page
44
Last page
71
DOI
10.1016/j.jctb.2018.09.004
Repository
http://hdl.handle.net/2117/134647 Open in new window
URL
https://www.sciencedirect.com/science/article/pii/S0095895618300856 Open in new window
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 is any bridge-addable class of graphs on n vertices, and is taken uniformly at random from , then is connected with probability at least , when n tends to infinity. This lower bound is asymptotically best possible since it is reached for forests. Our proof uses...
Citation
Chapuy, G.; Perarnau-Llobet, G. Connectivity in bridge-addable graph classes: the McDiarmid-Steger-Welsh conjecture. "Journal of combinatorial theory. Series B", 17 Setembre 2018, vol. 136, p. 44-71.
Group of research
GAPCOMB - Geometric, Algebraic and Probabilistic Combinatorics

Participants