TOPICS
Search

Herschel Graph

DOWNLOAD Mathematica NotebookDownload Wolfram Notebook
HerschelGraph

The smallest possible number of vertices a polyhedral nonhamiltonian graph can have is 11, and there exist 74 such graphs, including the Herschel graph and the Goldner-Harary graph. The Herschel graph is the unique 11-vertex nonhamiltonian polyhedral graph having the minimum possible number of edges (18). It was used by Owens (1980) in the construction of the 76-node Owens graph, which is the smallest known polyhedral quartic nonhamiltonian graph.

The Herschel graph is implemented in the Wolfram Language as GraphData["HerschelGraph"].

It has graph spectrum

(-sqrt(11))^1(-sqrt(3))^1(-sqrt(2))^20^3(sqrt(2))^2(sqrt(3))^1(sqrt(11))^1.

The canonical polyhedron corresponding to the Herschel graph may be termed the Herschel enneahedron.

See also

Goldner-Harary Graph, Hamiltonian Cycle, Hamiltonian Graph, Herschel Enneahedron, Icosian Game, Polyhedral Graph, Polyhedral Nonhamiltonian Graph

Explore with Wolfram|Alpha

References

Coxeter, H. S. M. Regular Polytopes, 3rd ed. New York: Dover, p. 8, 1973.Dillencourt, M. B. "Polyhedra of Small Orders and Their Hamiltonian Properties." Tech. Rep. 92-91, Info. and Comput. Sci. Dept. Irvine, CA: Univ. Calif. Irvine, 1992.Herschel, A. S. "Sir Wm. Hamilton's Icosian Game." Quart. J. Pure Applied Math. 5, 305, 1862.Owens, P. J. "On Regular Graphs and Hamiltonian Circuits, Including Answers to Some Questions of Joseph Zaks." J. Combin. Theory, Ser. B 28, 262-277, 1980.Tutte, W. T. "On Hamiltonian Circuits." J. London Math. Soc. 21, 98-101, 1946.

Cite this as:

Weisstein, Eric W. "Herschel Graph." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/HerschelGraph.html

Subject classifications