The Minimum Order Of A Class Of Hamiltonian Graphs And A New Proof That (k,g)-Cages Is 3-Connected

If a cycle in a graph contains all the vertices of the graph,then it is called a Hamilton cycle.A graph is said to be hamiltonian if it has a Hamilton cycle.Hamiltonian graphs are an important topic in graph theory.This thesis first studies a calss of hamiltonian graphs of minimum degree 3.In 1978 Entringer and Swart constructed a graph of order11 in which there is exactly one Hamilton cycle through a certain edge.In chapter 1 we prove that the smallest order of such graphs is 10.The length of a shortest cycle in a graph is called its girth.A(k,g)-graph is a k-regular graph of girth g.A(k,g)-graph is called a cage if it has the smallest order among all(k,g)-graphs.Tutte introduced this concept in 1947.Later Daven and Rodger and Jiang and mubayi proved independently that every(k,g)-cage is 3-connected.In chapter 2 we give a new proof of this result.