Abstract
A Halin graphH=T∪C is obtained by embedding a treeT having no nodes of degree 2 in the plane, and then adding a cycleC to join the leaves ofT 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.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
G. Cornuéjols, D. Naddef and W.R. Pulleyblank, “The travelling salesman problem in graphs with 3-edge cutsets”, Discussion paper no. 8212, Centre for Operations Research and Econometrics (Louvain-la-Neuve 1982).
J. Edmonds and E.L. Johnson “Matching: a well-solved class of integer programs”, in R.K. Guy et al., eds.,Combinatorial structures and their applications (Gordon and Breach, New York, 1970) pp. 89–92.
M. Grötschel,Polyedrische Charakterisierungen kombinatorischer Optimierungsprobleme (Verlag Anton Hain, Meisenheim am Glan, 1977).
R. Halin, “Studies on minimallyn-connected graphs”, in D.J.A. Welsh, ed.,Combinatorial mathematics, and its applications (Academic Press, New York 1971) pp. 129–136.
L. Lovász and M. Plummer, “On a family of planar bicritical graphs”,Proceedings of the London Mathematical Society 30 (1975) 160–176.
D. Naddef and W.R. Pulleyblank, “Ear decompositions of elementary graphs and GF2-rank of perfect matchings”,Annals of Discrete Mathematics 16 (1982) 241–260.
W.R. Pulleyblank, “The matching rank of Halin graphs”, RR210, 1MAG, Université Scientifique et Médicale de Grenoble, France (1980).
M. Syslo and A. Proskurowski, “On Halin graphs”, to appear inProceedings of the Tagow Conference dedicated to the memory of R. Kuratowski (1981).
Author information
Authors and Affiliations
Additional information
Research supported in part by NSF grant ENG 79-02526 to Carnegie-Mellon University.
Research supported by the National Science and Engineering Research Council of Canada and by the University of Bonn (Sonderforschungsbereich 21 (DFG), Institut für Operations Research).
Rights and permissions
About this article
Cite this article
Cornuéjols, G., Naddef, D. & Pulleyblank, W.R. Halin graphs and the travelling salesman problem. Mathematical Programming 26, 287–294 (1983). https://doi.org/10.1007/BF02591867
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF02591867