Hamilton cycles in random geometric graphs

J\'ozsef Balogh , B\'ela Bollob\'as , Michael Krivelevich , Tobias M\"uller , Mark Walters

Authors on Pith no claims yet

classification 🧮 math.PR math.CO

keywords graphalmostbecomeseverygeometrichamiltonmodelrandom

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

This paper has not been read by Pith yet.

Hamilton cycles in random geometric graphs

discussion (0)