{
  "id": "1203.0659",
  "version": "v2",
  "published": "2012-03-03T15:49:36.000Z",
  "updated": "2013-10-31T15:26:35.000Z",
  "title": "Hamilton decompositions of regular expanders: applications",
  "authors": [
    "Daniela Kühn",
    "Deryk Osthus"
  ],
  "comment": "final version, to appear in J. Combinatorial Theory B",
  "doi": "10.1016/j.jctb.2013.10.006",
  "categories": [
    "math.CO"
  ],
  "abstract": "In a recent paper, we showed that every sufficiently large regular digraph G on n vertices whose degree is linear in n and which is a robust outexpander has a decomposition into edge-disjoint Hamilton cycles. The main consequence of this theorem is that every regular tournament on n vertices can be decomposed into (n-1)/2 edge-disjoint Hamilton cycles, whenever n is sufficiently large. This verified a conjecture of Kelly from 1968. In this paper, we derive a number of further consequences of our result on robust outexpanders, the main ones are the following: (i) an undirected analogue of our result on robust outexpanders; (ii) best possible bounds on the size of an optimal packing of edge-disjoint Hamilton cycles in a graph of minimum degree d for a large range of values for d. (iii) a similar result for digraphs of given minimum semidegree; (iv) an approximate version of a conjecture of Nash-Williams on Hamilton decompositions of dense regular graphs; (v) the observation that dense quasi-random graphs are robust outexpanders; (vi) a verification of the `very dense' case of a conjecture of Frieze and Krivelevich on packing edge-disjoint Hamilton cycles in random graphs; (vii) a proof of a conjecture of Erdos on the size of an optimal packing of edge-disjoint Hamilton cycles in a random tournament.",
  "revisions": [
    {
      "version": "v2",
      "updated": "2013-10-31T15:26:35.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C45",
      "05C35",
      "05C70",
      "05C80",
      "05C20"
    ],
    "keywords": [
      "hamilton decompositions",
      "regular expanders",
      "robust outexpander",
      "conjecture",
      "applications"
    ],
    "tags": [
      "journal article"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2012arXiv1203.0659K"
    }
  }
}