Hamilton cycles in random geometric graphs

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

Research output: Contribution to journalArticle

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

    Balogh, J., Bollobás, B., Krivelevich, M., Müller, T., & Walters, M. (2011). Hamilton cycles in random geometric graphs. Annals of Applied Probability, 21(3), 1053-1072. https://doi.org/10.1214/10-AAP718