Hypotraceable Graph

A graph  is a hypotraceable graph if  has no Hamiltonian path (i.e., it is not a traceable graph), but  has a Hamiltonian path (i.e., is a traceable graph) for every  (Bondy and Murty 1976, p. 61).

There are no hypotraceable graphs on ten or fewer nodes (E. Weisstein, Dec. 11, 2013). In fact, the nonexistence of hypotraceable graphs on small numbers of vertices led T. Gallai to conjecture that no such graphs exist. This conjecture was refuted when a hypotraceable graph with 40 vertices was subsequently found by Horton (Grünbaum 1974, Thomassen 1974). Thomassen (1974) then showed that there exists a hypotraceable graph with  vertices for , 37, 39, 40, and all . The smallest of these is the 34-vertex Thomassen graph (left figure above; Thomassen 1974; Bondy and Murty 1976, pp. 239-240).

Walter (1969) gave an example of a connected graph in which the longest paths do not have a vertex in common, a property shared by hypotraceable graphs.

The planar hypotraceable graphs are a class of special interest.

REFERENCES

Araya, M. and Wiener, G. "On Cubic Planar Hypohamiltonian and Hypotraceable Graphs." Elec. J. Combin. 18, 2001.

 http://www.combinatorics.org/ojs/index.php/eljc/article/view/v18i1p85/.Bondy, J. A. and Murty, U. S. R. Graph Theory with Applications. New York: North Holland, pp. 61 and 239-240, 1976

.Grotschel, M. "On the Monotone Symmetric Travelling Salesman Problem: Hypohamiltonian/Hypotraceable Graphs and Facets." Math. Operations Res. 5, 285-292, 1980.

Grünbaum, B. "Vertices Missed by Longest Paths or Circuits." J. Combin. Th. A 17, 31-38, 1974.

Holton, D. A. and Sheehan, J. The Petersen Graph. Cambridge, England: Cambridge University Press, 1993.Jooyandeh, M.; McKay, B. D.; Östergård, P. R. J.; Pettersson, V. H.; and Zamfirescu, C. T. "Planar Hypohamiltonian Graphs on 40 Vertices." J. Graph Th. 84, 121-133, 2017.

Kapoor, S. F.; Kronk, H. V.; and Lick, D. R. "On Detours in Graphs." Canad. Math. Bull. 11, 195-201, 1968.

Thomassen, C. "Hypohamiltonian and Hypotraceable Graphs." Disc. Math. 9, 91-96, 1974.

Walter, H. "Über die Nichtexistenz eines Knotenpunktes, durch den alle längsten Wege eines Graphen gehen." J. Combin. Th. 6, 1-6, 1969

.Wiener, G. and Araya, M. "The Ultimate Question." 20 Apr 2009. http://arxiv.org/abs/0904.3012.Wiener, G. and Araya, M. "On Planar Hypotraceable Graphs." J. Graph Th. 67, 55-68, 2011.