Hamilton cycles in random geometric graphs

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.

Published in at http://dx.doi.org/10.1214/10-AAP718 the Annals of Applied Probability (http://www.imstat.org/aap/) by the Institute of Mathematical Statistics (http://www.imstat.org)

Cited by in corpus (6)

• Connectivity of soft random geometric graphs
• Hitting time theorems for random matrices
• Node-Differentially Private Estimation of the Number of Connected Components
• Hamiltonicity of graphs perturbed by a random geometric graph
• A geometric Achlioptas process
• On the contractibility of random Vietoris-Rips complexes