Booth Id:
MA036
Category:
Robotics and Intelligent Machines
Year:
2014
Finalist Names:
Clarke, Paul
Abstract:
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 Won:
American Mathematical Society: Third Award of $500