TY - JOUR
T1 - Critical window for connectivity in the configuration model
AU - Federico, L.
AU - van der Hofstad, R.W.
PY - 2017/9/1
Y1 - 2017/9/1
N2 - We identify the asymptotic probability of a configuration model CMn(d) producing a connected graph within its critical window for connectivity that is identified by the number of vertices of degree 1 and 2, as well as the expected degree. In this window, the probability that the graph is connected converges to a non-trivial value, and the size of the complement of the giant component weakly converges to a finite random variable. Under a finite second moment condition we also derive the asymptotics of the connectivity probability conditioned on simplicity, from which follows the asymptotic number of simple connected graphs with a prescribed degree sequence.
AB - We identify the asymptotic probability of a configuration model CMn(d) producing a connected graph within its critical window for connectivity that is identified by the number of vertices of degree 1 and 2, as well as the expected degree. In this window, the probability that the graph is connected converges to a non-trivial value, and the size of the complement of the giant component weakly converges to a finite random variable. Under a finite second moment condition we also derive the asymptotics of the connectivity probability conditioned on simplicity, from which follows the asymptotic number of simple connected graphs with a prescribed degree sequence.
UR - http://www.scopus.com/inward/record.url?scp=85020113045&partnerID=8YFLogxK
U2 - 10.1017/S0963548317000177
DO - 10.1017/S0963548317000177
M3 - Article
AN - SCOPUS:85020113045
SN - 0963-5483
VL - 26
SP - 660
EP - 680
JO - Combinatorics, Probability and Computing
JF - Combinatorics, Probability and Computing
IS - 5
ER -