{
  "id": "0904.0431",
  "version": "v2",
  "published": "2009-04-02T17:22:55.000Z",
  "updated": "2020-08-26T18:49:52.000Z",
  "title": "Hamilton cycles in 3-out",
  "authors": [
    "Tom Bohman",
    "Alan Frieze"
  ],
  "comment": "We removed an annoying typo in equation (17)",
  "categories": [
    "math.CO",
    "math.PR"
  ],
  "abstract": "Let G_{\\rm 3-out} denote the random graph on vertex set [n] in which each vertex chooses 3 neighbors uniformly at random. Note that G_{\\rm 3-out} has minimum degree 3 and average degree 6. We prove that the probability that G_{\\rm 3-out} is Hamiltonian goes to 1 as n tends to infinity.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2009-04-02T17:22:55.000Z",
      "comment": null,
      "journal": null,
      "doi": null
    },
    {
      "version": "v2",
      "updated": "2020-08-26T18:49:52.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "hamilton cycles",
      "random graph",
      "average degree",
      "vertex chooses",
      "minimum degree"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2009arXiv0904.0431B"
    }
  }
}