Planar graphs, regular graphs, bipartite graphs and Hamiltonicity.
Derek Holton, Robert E. L. Aldred · 1999
This paper seeks to review some ideas and results relating to Hamiltonian graphs. We list the well known results which are to be found in most undergraduate graph theory courses and then consider some old theorems which are fundamental to planar graphs. By restricting our attention to 3-connected cubic planar graphs (a class of graphs of interest to Four Colour Theorists), we are able to report on recent results regarding the smallest non Hamiltonian graphs. We then consider regular graphs generally and what might be said about when the number of Hamiltonian cycles is greater than one. Another interesting class of graphs are the bipartite graphs. In general these are not Hamiltonian but there is a famous conjecture due to Barnette that suggests that 3-connected cubic bipartite planar graphs are Hamiltonian. In our final two sections we consider this along with another open conjecture due to Barnette.