On the algorithmic complexity of finding hamiltonian cycles in special classes of planar cubic graphs
| Autor: | Gh., Behrooz Bagheri, Feder, Tomas, Fleischner, Herbert, Subi, Carlos |
|---|---|
| Rok vydání: | 2018 |
| Předmět: | |
| Druh dokumentu: | Working Paper |
| Popis: | 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. Comment: 17 pages, 0 figures. arXiv admin note: text overlap with arXiv:1806.05483 |
| Databáze: | arXiv |
| Externí odkaz: |
|