Sharp threshold for hamiltonicity of random geometric graphs

Abstract

We show for an arbitrary ${\ell }_p$ norm that the property that a random geometric graph $\mathcal{G}(n,r)$ contains a Hamiltonian cycle exhibits a sharp threshold at $r=r(n)=\sqrt{\frac{\log n}{{\alpha }_{p}n}}$, where ${\alpha }_p$ is the area of the unit disk in the ${\ell }_p$ norm. The proof is constructive and yields a linear time algorithm for finding a Hamiltonian cycle of $\RG$ a.a.s., provided $r=r(n)\ge \sqrt{\frac{\log n}{({\alpha }_p-\epsilon )n}}$ for some fixed $\epsilon >0$.

10 pages, 2 figures