Hamilton cycles in random geometric graphs

József Balogh, Béla Bollobás, Michael Krivelevich, Tobias Müller, Mark Walters

Research output: Contribution to journalArticlepeer-review

Abstract

We prove that, in the Gilbert model for a random geometric graph, almost every graph becomes Hamiltonian exactly when it first becomes 2-connected. This answers a question of Penrose. We also show that in the κ-nearest neighbor model, there is a constant κ such that almost every κ-connected graph has a Hamilton cycle.

Original languageEnglish (US)
Pages (from-to)1053-1072
Number of pages20
JournalAnnals of Applied Probability
Volume21
Issue number3
DOIs
StatePublished - Jun 2011

Keywords

  • Hamilton cycles
  • Random geometric graphs

ASJC Scopus subject areas

  • Statistics and Probability
  • Statistics, Probability and Uncertainty

Fingerprint Dive into the research topics of 'Hamilton cycles in random geometric graphs'. Together they form a unique fingerprint.

Cite this