{
  "id": "1606.01693",
  "version": "v1",
  "published": "2016-06-06T11:30:45.000Z",
  "updated": "2016-06-06T11:30:45.000Z",
  "title": "A Strengthening of a Theorem of Tutte on Hamiltonicity of Polyhedra",
  "authors": [
    "Gunnar Brinkmann",
    "Carol T. Zamfirescu"
  ],
  "comment": "20 pages",
  "categories": [
    "math.CO"
  ],
  "abstract": "In 1956, Tutte showed that every planar 4-connected graph is hamiltonian. In this article, we will prove that even if we relax the prerequisites on the polyhedra from 4-connected to containing at most three 3-cuts, hamiltonicity is still guaranteed. This also strengthens a theorem of Jackson and Yu, who have shown the result for the subclass of triangulations. We also prove that polyhedra with at most four 3-cuts have a hamiltonian path. It is well known that for each $k \\ge 6$ non-hamiltonian polyhedra with $k$ 3-cuts exist. We give computational results on lower bounds on the order of a possible non-hamiltonian polyhedron for the remaining open cases of polyhedra with four or five 3-cuts.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2016-06-06T11:30:45.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "hamiltonicity",
      "non-hamiltonian polyhedron",
      "hamiltonian path",
      "strengthening",
      "lower bounds"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 20,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}