Hamilton cycles in random geometric graphs

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

Published 2009-05-28, updated 2012-11-08Version 2

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 \kappa\ such that almost every \kappa-connected graph has a Hamilton cycle.