A Hamiltonian graph, also called a Hamilton graph, is a graph possessing a Hamiltonian cycle. A graph that
is not Hamiltonian is said to be nonhamiltonian.
While it would be easy to make a general definition of "Hamiltonian" that considers the singleton graph is to be either Hamiltonian or nonhamiltonian, defining
"Hamiltonian" to mean "has a Hamiltonian cycle" and taking "Hamiltonian
cycles" to be a subset of "cycles" in general would lead to the convention
that the singleton graph is nonhamiltonian (B. McKay,
pers. comm., Oct. 11, 2006). However, by convention, the singleton graph is
generally considered to be Hamiltonian (B. McKay, pers. comm., Mar. 22,
2007). The convention in this work and in GraphData
is that
is Hamiltonian, while
is nonhamiltonian.
The numbers of simple Hamiltonian graphs on nodes for , 2, ... are then given by 1, 0, 1, 3, 8, 48, 383, 6196,
177083, ... (OEIS A003216).
Testing whether a graph is Hamiltonian is an NP-complete problem (Skiena 1990, p. 196). Rubin (1974) describes an efficient search
procedure that can find some or all Hamilton paths and circuits in a graph using
deductions that greatly reduce backtracking and guesswork.
All Hamiltonian graphs are biconnected, although the converse is not true (Skiena 1990, p. 197). Any bipartite
graph with unbalanced vertex parity is not Hamiltonian.
If the sums of the degrees of nonadjacent vertices in a graph is greater than the number of nodes for all subsets of nonadjacent vertices, then is Hamiltonian (Ore 1960; Skiena 1990, p. 197).
All Platonic solids are Hamiltonian (Gardner 1957),
as illustrated above.
Although not explicitly stated by Gardner (1957), all Archimedean solids have Hamiltonian circuits as well, several of which are illustrated above.
However, the skeletons of the Archimedean duals
(i.e., the Archimedean dual graphs are not
necessarily Hamiltonian, as shown by Coxeter (1946) and Rosenthal (1946) for the
rhombic dodecahedron (Gardner 1984, p. 98).
Bermond, J.-C. "Hamiltonian Graphs." Ch. 6 in Selected
Topics in Graph Theory (Ed. L. W. Beineke and R. J. Wilson).
London: Academic Press, pp. 127-167, 1979.Bollobás, B. Graph
Theory: An Introductory Course. New York: Springer-Verlag, p. 12, 1979.Chartrand,
G. Introductory
Graph Theory. New York: Dover, p. 68, 1985.Chartrand, G.;
Kapoor, S. F.; and Kronk, H. V. "The Many Facets of Hamiltonian Graphs."
Math. Student41, 327-336, 1973.Coxeter, H. S. M.
"Problem E 711." Amer. Math. Monthly53, 156, 1946.Dolch,
J. P. "Names of Hamiltonian Graphs." In 4th S-E Conf. Combin.,
Graph Theory, Computing.Congress. Numer.8, 259-271, 1973.Gardner,
M. "Mathematical Games: About the Remarkable Similarity between the Icosian
Game and the Towers of Hanoi." Sci. Amer.196, 150-156, May 1957.Gardner,
M. The
Sixth Book of Mathematical Games from Scientific American. Chicago, IL: University
of Chicago Press, pp. 96-97, 1984.Godsil, C. and Royle, G. "Hamilton
Paths and Cycles." C§3.6 in Algebraic
Graph Theory. New York: Springer-Verlag, pp. 45-47, 2001.Gould,
R. J. "Updating the Hamiltonian Problem--A Survey." J. Graph Th.15,
121-157, 1991.Hamilton, W. R. Quart. J. Math., 5,
305, 1862.Hamilton, W. R. Philos. Mag.17, 42, 1884.Harary,
F. Graph
Theory. Reading, MA: Addison-Wesley, p. 4, 1994.Harary,
F. and Palmer, E. M. Graphical
Enumeration. New York: Academic Press, p. 219, 1973.Herschel,
A. S. "Sir Wm. Hamilton's Icosian Game." Quart. J. Pure Applied
Math.5, 305, 1862.Lucas, E. Récréations
mathématiques, Vol. 2. Paris: Gauthier-Villars, pp. 201
and 208-255, 1891.Mütze, T. "On Hamilton Cycles in Graphs
Defined by Intersecting Set Systems." Not. Amer. Soc.74, 583-592,
2024.Ore, O. "A Note on Hamiltonian Circuits." Amer. Math.
Monthly67, 55, 1960.Rosenthal, A. "Solution to Problem
E 711: Sir William Hamilton's Icosian Game." Amer. Math. Monthly53,
593, 1946.Rubin, F. "A Search Procedure for Hamilton Paths and
Circuits." J. ACM21, 576-580, 1974.Skiena, S. "Hamiltonian
Cycles." §5.3.4 in Implementing
Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Reading,
MA: Addison-Wesley, pp. 196-198, 1990.Sloane, N. J. A.
Sequence A003216/M2764 in "The On-Line
Encyclopedia of Integer Sequences."