|
Title:Hamiltonian cycles in plane cubic graphs
Abstract: Barnette's conjecture that every cubic, plane, 3-connected, bipartite graph is Hamiltonian has proved to be a very tough nut to crack. It is therefore interesting to examine special infinite classes of such graphs to determine if they are Hamiltonian. We introduce two operations on a graph G, denoted G_{vh} and G_{eh}, which generate cubic, plane, 3-connected, bipartite graphs from plane, 2-connected, bipartite graphs. For each of the classes of graphs so generated we have obtained a characterizing theorem for them to be Hamiltonian. We apply these theorems to several special classes of graphs, verifying that each is Hamiltonian. |