Behrooz Bagheri Gh., Tomas Feder, Herbert Fleischner, Carlos Subi
Published 2022-12-05Version 1
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. Moreover, we show that if Barnette's Conjecture is false, then hamiltonicity in 3-connected planar cubic bipartite graphs is an NP-complete problem.
Comments: arXiv admin note: substantial text overlap with arXiv:1806.06713. substantial text overlap with arXiv:1806.06713
On the algorithmic complexity of finding hamiltonian cycles in special classes of planar cubic graphs
Counting graphs with different numbers of spanning trees through the counting of prime partitions
Hamiltonian cycles in planar cubic graphs with facial 2-factors, and a new partial solution of Barnette's Conjecture
![QR code for arXiv:2212.02668 [math.CO]](http://oss.arxitics.com/images/favicon.svg)