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

SN - 0095-8956

VL - 31

SP - 156

EP - 167

JO - Journal of Combinatorial Theory, Series B

JF - Journal of Combinatorial Theory, Series B

IS - 2

ER -