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.House of Graphs. "Herschel Graph." https://houseofgraphs.org/graphs/1158.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.

Referenced on Wolfram|Alpha

Herschel Graph

Cite this as:

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

Subject classifications