Abstract
A Halin graph $H = T cup C$ 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.
Notes
We are currently acquiring citations for the work deposited into this collection. We recognize the distribution rights of this item may have been assigned to another entity, other than the author(s) of the work.If you can provide the citation for this work or you think you own the distribution rights to this work please contact the Institutional Repository Administrator at digitize@ucalgary.ca