On the Monotone Symmetric Travelling Salesman Problem: Hypohamiltonian/Hypotraceable Graphs and Facets

Abstract
A graph G is called hypohamiltonian (hypotraceable) if it does not contain a hamiltonian cycle (chain) but if every vertex-deleted subgraph G − v contains a hamiltonian cycle (chain). It is shown that certain classes of these graphs induce facets of the monotone symmetric travelling salesman polytope, i.e. the convex hull of the incidence vectors of all tours and subsets of tours. These results indicate that it is quite unlikely that an explicit complete characterization of this polytope can be obtained.