TOPICS
Search

Quintic Nonhamiltonian Graph

DOWNLOAD Mathematica NotebookDownload Wolfram Notebook
QuinticNonhamiltonianGraphs

A quintic nonhamiltonian graph is a quintic graph that is nonhamiltonian. A number of such graphs are illustrated above.

Owens (1980) showed that there exists a nonhamiltonian quintic polyhedral graph on 76 vertices, and van Cleemput and Zamfirescu (2018) demonstrated that there exists such a graph for every even n>=76. van Cleemput and Zamfirescu (2018) also demonstrated that the smallest possible such graph must have n>=38.

van Cleemput and Zamfirescu (2018) showed that there exists a nonhamiltonian quintic polyhedral graph on n vertices for every even n>=108, with no better lower bound presently known. Their proof relied on a construction involving the rhombic dodecahedral graph.

See also

Cubic Nonhamiltonian Graph, Nonhamiltonian Graph, Quartic Nonhamiltonian Graph, Quintic Graph

Explore with Wolfram|Alpha

References

Harant, J.; Owens, P. J.; Tkáč, M; and Walther, H. "5-Regular 3-Polytopal Graphs with Edges of Only Two Types and Shortness Exponents Less Than One." Disc. Math. 150, 143-153, 1996.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.van Cleemput, N. and Zamfirescu, C. T. "Regular Non-Hamiltonian Polyhedral Graphs." Appl. Math. Comput. 338 192-206, 2018.Walther, H. "A Non-Hamiltonian Five-Regular Multitriangular Polyhedral Graph." Disc. Math. 150, 387-392, 1996.

Cite this as:

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

Subject classifications