{
  "id": "0907.4459",
  "version": "v1",
  "published": "2009-07-26T05:08:26.000Z",
  "updated": "2009-07-26T05:08:26.000Z",
  "title": "Disjoint Hamilton cycles in the random geometric graph",
  "authors": [
    "Xavier Pérez-Giménez",
    "Nicholas C. Wormald"
  ],
  "categories": [
    "math.CO",
    "math.PR"
  ],
  "abstract": "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).",
  "revisions": [
    {
      "version": "v1",
      "updated": "2009-07-26T05:08:26.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "disjoint hamilton cycles",
      "first edge",
      "standard random geometric graph process",
      "random geometric graph hamiltonian",
      "pairwise edge-disjoint"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2009arXiv0907.4459P"
    }
  }
}