Paper Info
Title
On the connectivity of random graphs from addable classes
Abstract
A class A of graphs is called weakly addable (or bridge-addable) if for any G@?A and any two distinct components C"1 and C"2 in G, any graph that can be obtained by adding an edge between C"1 and C"2 is also in A. McDiarmid, Steger and Welsh (2006) conjectured in [6] that a graph chosen uniformly at random among all graphs with n vertices in a weakly addable A is connected with probability at least e^-^1^/^2^+^o^(^1^), as n-~. In this paper we show that the conjecture is true under a stronger assumption. A class G of graphs is called bridge-alterable, if for any G@?G and any bridge e in G, G@?G if and only if G-e@?G. We prove that a graph chosen uniformly at random among all graphs with n vertices in a bridge-alterable G is connected with probability at least e^-^1^/^2^+^o^(^1^), as n-~. The main tool in our analysis is a tight enumeration result that addresses the number of ways in which a given forest can be complemented to a forest with fewer components.
Year
DOI
Venue
2013
10.1016/j.jctb.2012.12.001
J. Comb. Theory, Ser. B
Keywords
Field
DocType
random graph,bridge-alterable g,n vertex,distinct component,stronger assumption,weakly addable,fewer component,class a,addable class,main tool,class g,bridge e,random graphs,connectivity
Graph,Discrete mathematics,Random regular graph,Combinatorics,Random graph,Vertex (geometry),Enumeration,If and only if,Conjecture,Mathematics
Journal
Volume
Issue
ISSN
103
2
0095-8956
Citations 
PageRank 
References 
7
0.68
2
Authors
2
Name
Order
Citations
PageRank
Mihyun Kang116329.18
Konstantinos Panagiotou229027.80