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.