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 graphsArticle

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.

    Comment: arXiv admin note: substantial text overlap with arXiv:1806.06713

    Source: arXiv.org:2212.02668
    Volume: Volume 188, Issue 1
    Published on: December 15, 2022
    Accepted on: December 7, 2022
    Submitted on: December 7, 2022
    Keywords: Mathematics - Combinatorics
    Licence: CC0 1.0 Universal (CC0 1.0) Public Domain Dedication

    Share and export

    Consultation statistics

    This page has been seen 299 times.
    This article's PDF has been downloaded 273 times.