On Finding Hamiltonian Cycles in Barnette Graphs

DOI10.3233/FI-222139MaRDI QIDQ5880941zbMATH OpenFDO

Authors Behrooz Bagheri Gh., Carlos Subi, Tomás Feder, Herbert Fleischner

Publication date 9 March 2023

Published in Fundamenta Informaticae (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2212.02668

zbMATH Keywords

Hamiltonian cycleBarnette's conjecture\(A\)-trailEulerian plane graphspanning tree of faces

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Eulerian and Hamiltonian graphs (05C45)

Recommendations

• On Barnette's conjecture
• A note on Barnette's conjecture
• Hamiltonian cycles in planar cubic graphs with facial 2‐factors, and a new partial solution of Barnette's Conjecture
• Hamiltonian cycles in some family of cubic 3-connected plane graphs
• Necessary condition for cubic planar 3-connected graph to be non-Hamiltonian with proof of Barnette's conjecture

Cites work

• scientific article; zbMATH DE number 3904590 (Why is no real title available?)
• scientific article; zbMATH DE number 3694608 (Why is no real title available?)
• scientific article; zbMATH DE number 3305794 (Why is no real title available?)
• Algorithms and outerplanar conditions for A-trails in plane Eulerian graphs
• Eulerian graphs and related topics. Part 1, Volume 1
• Graph theory
• Hamiltonian circuits in polytopes with even sided faces
• Hamiltonian cycles in cubic 3-connected bipartite planar graphs
• Hamiltonian cycles in planar cubic graphs with facial 2‐factors, and a new partial solution of Barnette's Conjecture
• Hamiltonicity in vertex envelopes of plane cubic graphs
• Matroid matching and some applications
• On Hamiltonian Circuits
• On the 2-factors of bicubic graphs
• On two-factors of bipartite regular graphs
• The NP-completeness of finding A-trails in Eulerian graphs and of finding spanning trees in hypergraphs
• The Planar Hamiltonian Circuit Problem is NP-Complete

Cited in

(5)

• Distance-two colourings of Barnette graphs
• Construction of Barnette graphs whose large subgraphs are non-Hamiltonian
• On finding hamiltonian cycles in Barnette graphs
• Hamiltonian cycles in planar cubic graphs with facial 2‐factors, and a new partial solution of Barnette's Conjecture
• Finding Hamiltonian paths in cocomparability graphs using the bump number algorithm

This page was built for publication: On Finding Hamiltonian Cycles in Barnette Graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5880941)