New Mexico Tech Socorro, NM 87801 Phone: (575)8355393 Fax: (575)8355366 math@nmt.edu 
The Traveling Salesman Problem on Halin GraphsA 4connected Halin graph is a graph of vertex connectivity 4 of the form H = S U T U C, where S and T are isomorphic plane trees with common leaves and C is the cycle containing the leaves of S in the order determined by the plane representation of S ot T. A 3connected Halin graph has a similar form H = T U C. 3connected Halin graphs have many interesting properties. They are Hamiltonianconnected and 1Hamiltonian (the vertex deleted subgraphs are Hamiltonian). Furthermore the travelling salesman problem can be solved in linear time on a weighted 3connected Halin graph. We have worked on the 4connected Halin graphs and proved the following for an arbitrary 4connected Halin graph H of order n : (a) H is pancyclic and so is any vertex deleted subgraph (b) H is 2Hamiltonian (c) The travelling salesman problem can be done in O(n^2) time on H (d) if x and y are vertices of H then Hxy is Hamiltonian.
