Behrooz Bagheri Gh. ; Tomas Feder ; Herbert Fleischner ; Carlos Subi - On finding hamiltonian cycles in Barnette graphs

fi:10437 - Fundamenta Informaticae, December 15, 2022, Volume 188, Issue 1
On finding hamiltonian cycles in Barnette graphs

Authors: Behrooz Bagheri Gh. ; Tomas Feder ; Herbert Fleischner ; Carlos Subi

    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.


    Volume: Volume 188, Issue 1
    Published on: December 15, 2022
    Accepted on: December 7, 2022
    Submitted on: December 7, 2022
    Keywords: Mathematics - Combinatorics

    Share

    Consultation statistics

    This page has been seen 25 times.
    This article's PDF has been downloaded 28 times.