|
|
|
A closed loop through a Graph that visits each node exactly once and ends adjacent to the
initial point. The Hamiltonian circuit is named after Sir William Rowan Hamilton, 
who devised a puzzle in which such a path along the Edges of an Icosahedron was sought (the
Icosian Game).
All Platonic Solids have a Hamiltonian circuit, as do planar 4-connected graphs. However, the
problem of finding a Hamiltonian circuit is NP-Complete, so the only known way to determine
whether a given general Graph has a Hamiltonian circuit is to undertake an exhaustive search. The
number of Hamiltonian circuits on an 
-Hypercube is 2, 8, 96, 43008, ... (Sloane's A006069; Gardner 1986, pp. 23-24).
See also Chvátal's Theorem, Dirac's Theorem, Euler Graph, Grinberg Formula, Hamiltonian Graph, Hamiltonian Path, Icosian Game, Kozyrev-Grinberg Theory, Ore's Theorem, Pósa's Theorem, Smith's Network Theorem
References
Chartrand, G. Introductory Graph Theory. New York: Dover, p. 68, 1985.
Gardner, M. ``The Binary Gray Code.'' In Knotted Doughnuts and Other Mathematical Entertainments.
New York: W. H. Freeman, pp. 23-24, 1986.
Sloane, N. J. A. Sequence
A006069/M1903
in ``An On-Line Version of the Encyclopedia of Integer Sequences.''
http://www.research.att.com/~njas/sequences/eisonline.html and Sloane, N. J. A. and Plouffe, S.
The Encyclopedia of Integer Sequences. San Diego: Academic Press, 1995.