On the Hamiltonicity of Cubic, Polyhedral, Bipartite Graphs

Overview

Barnette's conjecture states that every cubic, planar, 3-connected, bipartite (Barnette) graph is Hamiltonian. The conjecture is a famous unsolved problem in the field of graph theory. Due to the difficulty of the problem, little progress has been made since the conjecture was posed forty years ago. In this project, a specific class of Barnette graphs are considered, which we call difficult graphs. Difficult graphs are Barnette graphs whereby every pair of adjacent quadrilateral faces in the graph satisfies a particular property. Pairs of faces satisfying this property will be called dangerous pairs. The main result of this project states that if all difficult graphs are Hamiltonian, then Barnette's conjecture is true. This result has the obvious implication that if one were to prove all difficult graphs are Hamiltonian, Barnette's conjecture would also be proven. This will be the subject of future research.

Awards (1)

• American Mathematical Society: Third Award of $500 $500

Competition history

• ISEF 2014 Robotics and Intelligent Machines · Entry MA036

Resources

• ISEF abstract page ↗

Related projects

Closest projects by meaning, across every fair and year in the corpus.