New Mexico Tech Socorro, NM 87801 Phone: (575)835-5393 Fax: (575)835-5366 math@nmt.edu

The Traveling Salesman Problem on Halin Graphs A 4-connected 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 3-connected Halin graph has a similar form H = T U C. 3-connected Halin graphs have many interesting properties. They are Hamiltonian-connected and 1-Hamiltonian (the vertex deleted subgraphs are Hamiltonian). Furthermore the travelling salesman problem can be solved in linear time on a weighted 3-connected Halin graph. We have worked on the 4-connected Halin graphs and proved the following for an arbitrary 4-connected Halin graph H of order n : (a) H is pancyclic and so is any vertex deleted subgraph (b) H is 2-Hamiltonian (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 H-x-y is Hamiltonian.