Random graph processes with maximum degree 2

A. Ruciński, N. C. Wormald

Research output: Contribution to journalArticleResearchpeer-review

7 Citations (Scopus)

Abstract

Suppose that a 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 2. In a previous article, the authors showed that as n → ∞, with probability tending to 1, the result of this process is a graph with n edges. The number of l-cycles in this graph is shown to be asymptotically Poisson (l ≥ 3), and other aspects of this random graph model are studied.

Original languageEnglish
Pages (from-to)183-199
Number of pages17
JournalAnnals of Applied Probability
Volume7
Issue number1
Publication statusPublished - Feb 1997
Externally publishedYes

Keywords

  • Generation algorithms
  • Limiting distributions
  • Number of cycles

Cite this