{
  "id": "1806.06713",
  "version": "v1",
  "published": "2018-06-15T11:17:50.000Z",
  "updated": "2018-06-15T11:17:50.000Z",
  "title": "On the algorithmic complexity of finding hamiltonian cycles in special classes of planar cubic graphs",
  "authors": [
    "Behrooz Bagheri Gh.",
    "Tomas Feder",
    "Herbert Fleischner",
    "Carlos Subi"
  ],
  "comment": "17 pages, 0 figures. arXiv admin note: text overlap with arXiv:1806.05483",
  "categories": [
    "math.CO"
  ],
  "abstract": "It is a well-known fact that hamiltonicity in planar cubic graphs is an NP-complete problem. This implies that the existence of an A-trail in plane eulerian graphs is also an NP-complete problem even if restricted to planar 3-connected eulerian graphs. In this paper we deal with hamiltonicity in planar cubic graphs G having a facial 2-factor Q via (quasi) spanning trees of faces in G/Q and study the algorithmic complexity of finding such (quasi) spanning trees of faces. We show, in particular, that if Barnette's Conjecture is false, then hamiltonicity in 3-connected planar cubic bipartite graphs is an NP-complete problem.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2018-06-15T11:17:50.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "planar cubic graphs",
      "finding hamiltonian cycles",
      "algorithmic complexity",
      "special classes",
      "np-complete problem"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 17,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}