Hypohamiltonian Graph - Generalizations

Generalizations

Graph theorists have also studied hypotraceable graphs, graphs that do not contain a Hamiltonian path but such that every subset of n − 1 vertices may be connected by a path. Analogous definitions of hypohamiltonicity and hypotraceability for directed graphs have been considered by several authors.

An equivalent definition of hypohamiltonian graphs is that their longest cycle has length n − 1 and that the intersection of all longest cycles is empty. Menke, Zamfirescu & Zamfirescu (1998) investigate graphs with the same property that the intersection of longest cycles is empty but in which the longest cycle length is shorter than n − 1. Herz (1968) defines the cyclability of a graph as the largest number k such that every k vertices belong to a cycle; the hypohamiltonian graphs are exactly the graphs that have cyclability n − 1. Similarly, Park, Lim & Kim (2007) define a graph to be ƒ-fault hamiltonian if the removal of at most ƒ vertices leaves a Hamiltonian subgraph. Schauerte & Zamfirescu (2006) study the graphs with cyclability n − 2.