Report Number: CS-TR-72-256
Institution: Stanford University, Department of Computer Science
Title: Edmonds polyhedra and weakly hamiltonian graphs.
Author: Chvatal, Vaclav
Date: January 1972
Abstract: Jack Edmonds developed a new way of looking at extremal combinatorial problems and applied his technique with a great success to the problems of the maximal-weight degree-constrained subgraphs. Professor C. St. J. A. Nash-Williams suggested to use Edmonds' approach in the context of hamiltonian graphs. In the present paper, we determine a new set of inequalities (the "comb inequalities") which are satisfied by the characteristic functions of hamiltonian circuits but are not explicit in the straightforward integer programming formulation. A direct application of the linear programming duality theorem then leads to a new necessary condition for the existence of hamiltonian circuits; this condition appears to be stronger than the previously known ones. Relating linear programming to hamiltonian circuits, the present paper can also be seen as a continuation of the work of Dantzig, Fulkerson and Johnson on the travelling salesman problem.
http://i.stanford.edu/pub/cstr/reports/cs/tr/72/256/CS-TR-72-256.pdf