Hamiltonicity of random graphs produced by 2-processes

András Telcs, Nicholas Wormald, Sanming Zhou

Research output: Contribution to journalArticleResearchpeer-review

5 Citations (Scopus)

Abstract

Suppose that a random graph begins with n isolated vertices and evolves by edges being added at random, conditional upon all vertex degrees being at most 2. The final graph is usually 2-regular, but is not uniformly distributed. Some properties of this final graph are already known, but the asymptotic probability of being a Hamilton cycle was not known. We answer this question along with some related questions about cycles arising in the process.

Original languageEnglish
Pages (from-to)450-481
Number of pages32
JournalRandom Structures & Algorithms
Volume31
Issue number4
DOIs
Publication statusPublished - Dec 2007
Externally publishedYes

Keywords

  • 2-process
  • Differential equation
  • Graph
  • Hamilton cycle
  • Hamiltonicity
  • Large deviation inequality
  • Martingale
  • Probability
  • Random graph process

Cite this