{
  "id": "1512.07655",
  "version": "v1",
  "published": "2015-12-23T22:45:50.000Z",
  "updated": "2015-12-23T22:45:50.000Z",
  "title": "The number of Hamiltonian decompositions of regular graphs",
  "authors": [
    "Roman Glebov",
    "Zur Luria",
    "Benny Sudakov"
  ],
  "categories": [
    "math.CO"
  ],
  "abstract": "A Hamilton cycle in a graph $\\Gamma$ is a cycle passing through every vertex of $\\Gamma$. A Hamiltonian decomposition of $\\Gamma$ is a partition of its edge set into disjoint Hamilton cycles. One of the oldest results in graph theory is Walecki's theorem from the 19th century, showing that a complete graph $K_n$ on an odd number of vertices $n$ has a Hamiltonian decomposition. This result was recently greatly extended by K\\\"{u}hn and Osthus. They proved that every $r$-regular $n$-vertex graph $\\Gamma$ with even degree $r=cn$ for some fixed $c>1/2$ has a Hamiltonian decomposition, provided $n=n(c)$ is sufficiently large. In this paper we address the natural question of estimating $H(\\Gamma)$, the number of such decompositions of $\\Gamma$. Our main result is that $H(\\Gamma)=r^{(1+o(1))nr/2}$. In particular, the number of Hamiltonian decompositions of $K_n$ is $n^{(1-o(1))n^2/2}$.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2015-12-23T22:45:50.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "hamiltonian decomposition",
      "regular graphs",
      "disjoint hamilton cycles",
      "vertex graph",
      "edge set"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2015arXiv151207655G"
    }
  }
}