Applications
Hypohamiltonian graphs arise in integer programming solutions to the traveling salesman problem: certain kinds of hypohamiltonian graphs define facets of the traveling salesman polytope, a shape defined as the convex hull of the set of possible solutions to the traveling salesman problem, and these facets may be used in cutting-plane methods for solving the problem. Grötschel (1980) observes that the computational complexity of determining whether a graph is hypohamiltonian, although unknown, is likely to be high, making it difficult to find facets of these types except for those defined by small hypohamiltonian graphs; fortunately, the smallest graphs lead to the strongest inequalities for this application.
Concepts closely related to hypohamiltonicity have also been used by Park, Lim & Kim (2007) to measure the fault tolerance of network topologies for parallel computing.
Read more about this topic: Hypohamiltonian Graph