Sharp threshold for hamiltonicity of random geometric graphs
<|reference_start|>Sharp threshold for hamiltonicity of random geometric graphs: 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$.<|reference_end|>
@article{diaz2006sharp,
    title={Sharp threshold for hamiltonicity of random geometric graphs},
    author={J. Diaz, D. Mitsche, X. Perez},
    journal={arXiv preprint arXiv:cs/0607023},
    year={2006},
    archivePrefix={arXiv},
    eprint={cs/0607023},
    primaryClass={cs.DM}
}