On Finding Hamiltonian Cycles in Barnette Graphs

DOI10.3233/FI-222139MaRDI QIDQ5880941FDOQ5880941

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

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

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)

Cites Work

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

Cited In (5)

• Distance-two colourings of Barnette graphs
• On finding hamiltonian cycles in Barnette graphs
• Construction of Barnette graphs whose large subgraphs are non-Hamiltonian
• 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)