{
  "id": "0903.4567",
  "version": "v1",
  "published": "2009-03-26T13:16:51.000Z",
  "updated": "2009-03-26T13:16:51.000Z",
  "title": "Pancyclicity of Hamiltonian and highly connected graphs",
  "authors": [
    "Peter Keevash",
    "Benny Sudakov"
  ],
  "comment": "15 pages, 1 figure",
  "categories": [
    "math.CO"
  ],
  "abstract": "A graph G on n vertices is Hamiltonian if it contains a cycle of length n and pancyclic if it contains cycles of length $\\ell$ for all $3 \\le \\ell \\le n$. Write $\\alpha(G)$ for the independence number of $G$, i.e. the size of the largest subset of the vertex set that does not contain an edge, and $\\kappa(G)$ for the (vertex) connectivity, i.e. the size of the smallest subset of the vertex set that can be deleted to obtain a disconnected graph. A celebrated theorem of Chv\\'atal and Erd\\H{o}s says that $G$ is Hamiltonian if $\\kappa(G) \\ge \\alpha(G)$. Moreover, Bondy suggested that almost any non-trivial conditions for Hamiltonicity of a graph should also imply pancyclicity. Motivated by this, we prove that if $\\kappa(G) \\ge 600\\alpha(G)$ then G is pancyclic. This establishes a conjecture of Jackson and Ordaz up to a constant factor. Moreover, we obtain the more general result that if G is Hamiltonian with minimum degree $\\delta(G) \\ge 600\\alpha(G)$ then G is pancyclic. Improving an old result of Erd\\H{o}s, we also show that G is pancyclic if it is Hamiltonian and $n \\ge 150\\alpha(G)^3$. Our arguments use the following theorem of independent interest on cycle lengths in graphs: if $\\delta(G) \\ge 300\\alpha(G)$ then G contains a cycle of length $\\ell$ for all $3 \\le \\ell \\le \\delta(G)/81$.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2009-03-26T13:16:51.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C38",
      "05C45"
    ],
    "keywords": [
      "highly connected graphs",
      "hamiltonian",
      "pancyclicity",
      "vertex set",
      "old result"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 15,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2009arXiv0903.4567K"
    }
  }
}