Quartic Nonhamiltonian Graph


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

Van Cleemput and Zamfirescu (2018) gave a 39-vertex example of a nonhamiltonian quartic polyhedral graph (the 39-van Cleemput-Zamfirescu graph), showed that there exists a on n vertices for each n>=39, and conjectured that n=39 gives the smallest such graph possible. Van Cleemput and Zamfirescu (2018) also gave a 78-node quartic nonhamiltonian polyhedral graph that is untraceable.

See also

Cubic Nonhamiltonian Graph, Meredith Graph, Nonhamiltonian Graph, Quartic Graph, van Cleemput-Zamfirescu Graphs

Explore with Wolfram|Alpha


van Cleemput, N. and Zamfirescu, C. T. "Regular Non-Hamiltonian Polyhedral Graphs." Appl. Math. Comput. 338 192-206, 2018.

Cite this as:

Weisstein, Eric W. "Quartic Nonhamiltonian Graph." From MathWorld--A Wolfram Web Resource.

Subject classifications