NMT logo
Mathematics Department Home
Course Information
Help SessionsThe Undergraduate Program
The Graduate Program
Faculty
Schedules
News and Events
Faculty Research
Opportunities for Students
Careers in Mathematics
Industrial Mathematics Program
Operations Research and Statistics Program
Seminar
Reports
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.