Connectedness of graphs generated by a random d-process

A. Ruciński, N. C. Wormald

Research output: Contribution to journalArticleResearchpeer-review

11 Citations (Scopus)

Abstract

Suppose that a graph process begins with n isolated vertices, to which edges are added randomly one by one so that the maximum degree of the induced graph is always at most d. In a previous article, the authors showed that as n → ∞, with probability tending to 1, the result of this process is a d-regular graph. This graph is shown to be connected with probability asymptotic to 1.

Original languageEnglish
Pages (from-to)67-85
Number of pages19
JournalJournal of the Australian Mathematical Society
Volume72
Issue number1
DOIs
Publication statusPublished - 2002
Externally publishedYes

Cite this