van Cleemput-Zamfirescu Graphs


A number of interesting graphs are associated with the work of van Cleemput and Zamfirescu (2018).

Two 13- and 15-node graphs, denoted alpha and beta respectively, were used in the construction of an untraceable quintic polyhedral graph on 108 nodes which is the smallest known such graph.

The 39-node van Cleemput-Zamfirescu graph is the smallest known (and conjectured to be smallest possible) polyhedral quartic nonhamiltonian graph. (It is however traceable.) The 78-node and 108-node van Cleemput-Zamfirescu graphs are the smallest known quartic and quintic graphs, respectively, that are untraceable and polyhedral.

These graphs are will be implemented in the Wolfram Language as GraphData["VanCleemputZamfirescuGraphNNN"].

See also

Nonhamiltonian Graph, Quartic Graph, Quartic Nonhamiltonian Graph, Untraceable Graph

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. "van Cleemput-Zamfirescu Graphs." From MathWorld--A Wolfram Web Resource.

Subject classifications