Hamilton cycles in random geometric graphs

Citation
Balogh, József et al., Hamilton cycles in random geometric graphs, Annals of applied probability , 21(3), 2011, pp. 1053-1072
ISSN journal
10505164
Volume
21
Issue
3
Year of publication
2011
Pages
1053 - 1072
Database
ACNP
SICI code
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 k-nearest neighbor model, there is a constant . such that almost every .-connected graph has a Hamilton cycle.