A graph
is hypohamiltonian if is nonhamiltonian,
but
is Hamiltonian for every (Bondy and Murty 1976, p. 61). The Petersen
graph, which has ten nodes, is the smallest hypohamiltonian graph (Herz et
al. 1967; Bondy and Murty 1976, p. 61) and the only such graph on ten nodes.
Herz et al. (1967) showed that there are no hypohamiltonian graphs with 11
or 12 vertices.
By parity, no bipartite graph is hypohamiltonian.
Many (but not all) snarks are hypohamiltonian.
Sousselier (in Herz et al. 1967) and Lindgren (1967) independently constructed the same sequence of hypohamiltonian graphs with vertices, illustrated above (which includes the Petersen
graph on 10 vertices).
Bondy (1972) found an infinite sequence of hypohamiltonian graphs on vertices.
Sousselier found a cubic hypohamiltonian graph on 18 vertices (Chvátal 1973). Chvátal (1973) showed there exists a hypohamiltonian graph on vertices for every . More generally, there exists a hypohamiltonian graph
for every
with the exception of (Collier and Schmeichel 1978) and (Aldred et al. 1997). Aldred et al. (1997)
give a complete enumeration of all (seven) hypohamiltonian graphs on 17 or fewer
vertices. McKay gives a listing of all known hypohamiltonian graphs up to 26 vertices
(where the enumerations on 18 vertices and higher may be incomplete), as well as
a girth-restricted subset of cubic hypohamiltonian up to 26 vertices. The numbers
of hypohamiltonian graphs on , 2, ... nodes are 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1,
0, 1, 4, 0, 14, 34, ... (OEIS A141150; Goedgebeur
and Zamfirescu 2017).
Thomassen (1973) found hypohamiltonian graphs on and 25 vertices, and Collier and Schmeichel (1978) found
"new" hypohamiltonian graphs for and 22, though their "new" graph is actually isomorphic to the first Blanuša
snark and their "new" graphs are isomorphic to the Loupekine
snarks.
A number of non-snark hypohamiltonian graphs, including
a number previously discussed, are shown above, ordered by vertex count.
Aldred, R. E. L.; Bau, S.; Holton, D. A.; and McKay, B. D. "Nonhamiltonian 3-Connected Cubic Planar Graphs."
SIAM J. Disc. Math.13, 25-32, 2000.Aldred, R. E. L.;
McKay, B. D.; and Wormald, N. C. "Small Hypohamiltonian Graphs."
J. Combin. Math. Combin. Comput.23, 143-152, 1997.Araya,
M. and Wiener, G. "On Cubic Planar Hypohamiltonian and Hypotraceable Graphs."
Elec. J. Combin.18, 2011. http://www.combinatorics.org/ojs/index.php/eljc/article/view/v18i1p85/.Bondy,
J. A. "Variations of the Hamiltonian Theme." Canad. Math. Bull.15,
57-62, 1972.Bondy, J. A. and Murty, U. S. R. Graph
Theory with Applications. New York: North Holland, p. 61, 1976.Chvátal,
V. "Flip-Flops in Hypohamiltonian Graphs." Canad. Math. Bull.16,
33-41, 1973.Collier, J. B. and Schmeichel, E. F. "Systematic
Searches for Hypohamiltonian Graphs." Networks8, 193-200, 1978.Doyen,
J. and van Diest, V. "New Families of Hypohamiltonian Graphs." Disc.
Math.13, 225-236, 1975.Gaudin, T.; Herz, J.-C.; and Rossi,
P. "Solution de problème no. 29." Française Informat.
Recherche Opérationnelle8, 214-218, 1964.Godsil,
C. and Royle, G. Algebraic
Graph Theory. New York: Springer-Verlag, p. 66, 2001.Goedgebeur,
J. and Zamfirescu, C. T. "Improved Bounds for Hypohamiltonian Graphs."
Ars Math. Contemp.13, 235-257, 2017.Grotschel, M. "On
the Monotone Symmetric Travelling Salesman Problem: Hypohamiltonian/Hypotraceable
Graphs and Facets." Math. Operations Res.5, 285-292, 1980.Harary,
F. Graph
Theory. Reading, MA: Addison-Wesley, 1994.Hatzel, H. "Ein
planarer hypohamiltonscher Graph mit 57 Knoten." Math Ann.243,
213-216, 1979.Herz, J. C.; Duby, J. J.; and Vigué,
F. "Recherche systématique des graphes hypohamiltoniens." In Theory
of Graphs: Internat. Sympos., Rome 1966 (Ed. P. Rosenstiehl). Paris: Gordon
and Breach, pp. 153-159, 1967.Holton, D. A. and Sheehan, J.
The
Petersen Graph. Cambridge, England: Cambridge University Press, 1993.House
of Graphs. "Hypohamiltonian Graphs." https://houseofgraphs.org/meta-directory/hypohamiltonian.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.Katerinis, P. "Some
Properties of Hypohamiltonian Graphs." Aeq. Math.72, 139-151,
2006.Lindgren, W. F. "An Infinite Class of Hypohamiltonian
Graphs." Amer. Math. Monthly74, 1087-1089, 1967.McKay,
B. "Hypohamiltonian Graphs." http://cs.anu.edu.au/~bdm/data/graphs.html.Skupień,
Z. "Exponentially Many Hypohamiltonian Snarks." Electronic Notes in
Disc. Meth.28, 417-424, 2007.Sloane, N. J. A.
Sequence A141150 in "The On-Line Encyclopedia
of Integer Sequences."Sousselier, R. "Problème no.
29: Le cercle des irascibles." Rev. Franc. Rech. Operat.7, 405-406,
1963.Thomassen, C. "Hypohamiltonian and Hypotraceable Graphs."
Disc. Math.9, 91-96, 1974.Thomassen, C. "On Hypohamiltonian
Graphs." Disc. Math.10, 383-390, 1974.Thomassen,
C. "Planar and Infinite Hypohamiltonian and Hypotraceable Graphs." Disc.
Math14, 377-389, 1976.Thomassen, C. "Hypohamiltonian
Graphs and Digraphs." In Theory
and Applications of Graphs Proceedings, Michigan May 11-15, 1976 (Ed. Y. Alavi
and D. R. Lick). New York: Springer-Verlag, pp. 557-571, 1978.Thomassen,
C. "Planar Cubic Hypohamiltonian and Hypotraceable Graphs." J. Comb.
Th. B30, 36-44, 1981.Tsai, C.-C. "Small Planar Hypohamiltonian
Graphs." 8 Apr 2024. https://arxiv.org/abs/2403.18384.Wiener,
G. and Araya, M. "The Ultimate Question." 20 Apr 2009. http://arxiv.org/abs/0904.3012.Wiener,
G. and Araya, M. "On Planar Hypohamiltonian Graphs." J. Graph Th.67,
55-68, 2011.Zamfirescu, C. T. and Zamfirescu, T. I. "A
Planar Hypohamiltonian Graph with 48 Vertices." J. Graph Th.48,
338-342, 2007.
is hypohamiltonian if 
is nonhamiltonian,
but 
is Hamiltonian for every 
(Bondy and Murty 1976, p. 61). The Petersen
graph, which has ten nodes, is the smallest hypohamiltonian graph (Herz et
al. 1967; Bondy and Murty 1976, p. 61) and the only such graph on ten nodes.
Herz et al. (1967) showed that there are no hypohamiltonian graphs with 11
or 12 vertices.
vertices, illustrated above (which includes the Petersen
graph on 10 vertices).
vertices.
vertices for every 
. More generally, there exists a hypohamiltonian graph
for every 
with the exception of 
(Collier and Schmeichel 1978) and 
(Aldred et al. 1997). Aldred et al. (1997)
give a complete enumeration of all (seven) hypohamiltonian graphs on 17 or fewer
vertices. McKay gives a listing of all known hypohamiltonian graphs up to 26 vertices
(where the enumerations on 18 vertices and higher may be incomplete), as well as
a girth-restricted subset of cubic hypohamiltonian up to 26 vertices. The numbers
of hypohamiltonian graphs on 
, 2, ... nodes are 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1,
0, 1, 4, 0, 14, 34, ... (OEIS A141150; Goedgebeur
and Zamfirescu 2017).
and 25 vertices, and Collier and Schmeichel (1978) found
"new" hypohamiltonian graphs for 
and 22, though their "new" 
graph is actually isomorphic to the first Blanuša
snark and their "new" 
graphs are isomorphic to the Loupekine
snarks.
