TOPICS
Search

Goldner-Harary Graph


GoldnerHararyGraph

The smallest possible number of vertices a polyhedral nonhamiltonian graph can have is 11, and there exist 74 such graphs. The Goldner-Harary graph (Goldner and Harary 1975a, de Wet et al. 2018), illustrated above, is one of these, as is the Herschel graph.

The Goldner-Harary graph has 11 vertices and 27 edges. It is exceptional for being the unique smallest nonhamiltonian simplicial graph, meaning it is the only 11-vertex nonhamiltonian polyhedral that contains of only triangular faces. It is also the unique 11-vertex nonhamiltonian polyhedral graph having the maximum possible 27 edges. It is also a 3-tree.

GoldnerHararyGraphEmbeddings

The Goldner-Harary graph is shown above in a number of straight-line embeddings.

The Goldner-Harary graph is the skeleton of the augmented triangular dipyramid, a construction described by Grünbaum (2003, p. 357), though without identification of the particular resulting graph. It is also the dual graph of the skeleton of the truncated triangular prism. The canonical polyhedron of this solid is termed the Goldner-Harary polyhedron in this work.


See also

Goldner-Harary Polyhedron, Herschel Graph Nonhamiltonian Graph, Polyhedral Graph, Polyhedral Nonhamiltonian Graph, Truncated Triangular Prism

Explore with Wolfram|Alpha

References

de Wet, J. P.; Frick, M.; and van Aardt, S. A. "Hamiltonicity of Locally Hamiltonian and Locally Traceable Graphs." Disc. Appl. Math. 236, 137-152, 2018.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.Dillencourt, M. B. "Polyhedra of Small Orders and Their Hamiltonian Properties." J. Combin. Th. 66, 87-122, 1996.Goldner, A. and Harary, F. "Note on a Smallest Nonhamiltonian Maximal Planar Graph." Bull. Malaysian Math. Soc. 6, No. 1, 41-42, 1975a.Goldner, A. and Harary, F. "Note on a Smallest Nonhamiltonian Maximal Planar Graph." Bull. Malaysian Math. Soc. 6, No. 2, 33, 1975b.Goldner, A. and Harary, F. "Note on a Smallest Nonhamiltonian Maximal Planar Graph." Bull. Malaysian Math. Soc. 8, 104-106, 1977.Grünbaum, B. Convex Polytopes, 2nd ed. New York: Springer-Verlag, p. 357, 2003.Read, R. C. and Wilson, R. J. An Atlas of Graphs. Oxford, England: Oxford University Press, p. 285, 1998.

Cite this as:

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

Subject classifications