Hamiltonian Circuit

A closed loop through a Graph that visits each node exactly once and ends adjacent to theinitial 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 (theIcosian Game).

All Platonic Solids have a Hamiltonian circuit, as do planar 4-connected graphs. However, theproblem of finding a Hamiltonian circuit is NP-Complete, so the only known way to determinewhether a given general Graph has a Hamiltonian circuit is to undertake an exhaustive search. Thenumber of Hamiltonian circuits on an -A006069; Gardner 1986, pp. 23-24).

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. SequenceA006069/M1903in ``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.

• Thue Sequence
• Thue-Siegel-Roth Theorem
• Thue-Siegel-Schneider-Roth Theorem
• Thue's Theorem
• Thurston's Geometrization Conjecture
• Thwaites Conjecture
• Ticktacktoe
• Tic-Tac-Toe
• Tight Closure
• Tightly Embedded
• Tiling
• Tiling Theorem
• Times
• Titanic Prime
• Titchmarsh Theorem
• Tit-for-Tat
• Tits Group
• Toeplitz Matrix
• Togliatti Surface
• Tomography
• Tooth Surface
• Topological Basis
• Topological Completion
• Topological Dimension
• Topological Entropy