Disjoint Hamilton cycles in the random geometric graph

Xavier Pérez-Giménez, Nicholas C. Wormald

Published 2009-07-26Version 1

We prove a conjecture of Penrose about the standard random geometric graph process, in which n vertices are placed at random on the unit square and edges are sequentially added in increasing order of lengths taken in the l_p norm. We show that the first edge that makes the random geometric graph Hamiltonian is a.a.s. exactly the same one that gives 2-connectivity. We also extend this result to arbitrary connectivity, by proving that the first edge in the process that creates a k-connected graph coincides a.a.s. with the first edge that causes the graph to contain k/2 pairwise edge-disjoint Hamilton cycles (for even k), or (k-1)/2 Hamilton cycles plus one perfect matching, all of them pairwise edge-disjoint (for odd k).