The asymptotic connectivity of labelled regular graphs

Research output: Contribution to journalArticleResearchpeer-review

75 Citations (Scopus)

Abstract

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.

Original languageEnglish
Pages (from-to)156-167
Number of pages12
JournalJournal of Combinatorial Theory, Series B
Volume31
Issue number2
DOIs
Publication statusPublished - 1981
Externally publishedYes

Cite this