HALIN GRAPHS AND THE TRAVELLING SALESMAN PROBLEM

Abstract

A Halin graph H=TcupC is obtained by imbedding a tree T having no degree two nodes in the plane, and then adding a cycle C to join the leaves of T in such a way that the resulting graph is planar. These graphs are edge minimal 3-connected, hamiltonian, and in general have large numbers of hamilton cycles. We show that for arbitrary real edge costs the travelling salesman problem can be polynomially solved for such a graph, and we give an explicit linear description of the travelling salesman polytope (the convex hull of the incidence vectors of the hamilton cycles) for such a graph.