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.
- Hamilton cycles
- Random geometric graphs
ASJC Scopus subject areas
- Statistics and Probability
- Statistics, Probability and Uncertainty