TY - JOUR
T1 - The asymptotic connectivity of labelled regular graphs
AU - Wormald, Nicholas C.
PY - 1981
Y1 - 1981
N2 - It is shown that almost all labelled r-regular graphs are r-connected, for any fixed r≥3. This is an instance of a more general result which applies to labelled locally restricted graphs whose points have degrees lying between r and R, where r and R are fixed, 3≤r≤R. The proof employs a known asymptotic formula for the numbers of these locally restricted graphs. It is also demonstrated that for fixed k>0 and r≥3, almost all labelled r-regular graphs with girth at least [k/(r-2)] are cyclically k-connected. This provides an asymptotic formula for the number of labelled cyclically k-connected r-regular graphs with p points, for fixed k and r.
AB - It is shown that almost all labelled r-regular graphs are r-connected, for any fixed r≥3. This is an instance of a more general result which applies to labelled locally restricted graphs whose points have degrees lying between r and R, where r and R are fixed, 3≤r≤R. The proof employs a known asymptotic formula for the numbers of these locally restricted graphs. It is also demonstrated that for fixed k>0 and r≥3, almost all labelled r-regular graphs with girth at least [k/(r-2)] are cyclically k-connected. This provides an asymptotic formula for the number of labelled cyclically k-connected r-regular graphs with p points, for fixed k and r.
UR - http://www.scopus.com/inward/record.url?scp=58149404605&partnerID=8YFLogxK
U2 - 10.1016/S0095-8956(81)80021-4
DO - 10.1016/S0095-8956(81)80021-4
M3 - Article
AN - SCOPUS:58149404605
VL - 31
SP - 156
EP - 167
JO - Journal of Combinatorial Theory, Series B
JF - Journal of Combinatorial Theory, Series B
SN - 0095-8956
IS - 2
ER -