BIB-VERSION:: CS-TR-v2.0
          ID:: STAN//CS-TR-72-256
       ENTRY:: October 16, 1995
ORGANIZATION:: Stanford University, Department of Computer Science
       TITLE:: Edmonds polyhedra and weakly hamiltonian graphs.
        TYPE:: Technical Report
      AUTHOR:: Chvatal, Vaclav
        DATE:: January 1972
       PAGES:: 24
    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.
       NOTES:: [Adminitrivia V1/Prg/19951016]
         END:: STAN//CS-TR-72-256