Online citations, reference lists, and bibliographies.
← Back to Search

Polyhedra With Few 3-Cuts Are Hamiltonian

G. Brinkmann, C. T. Zamfirescu

Save to my Library
Download PDF
Analyze on Scholarcy Visualize in Litmaps
Reduce the time it takes to create your bibliography by a factor of 10 by using the world’s favourite reference manager
Time to take this seriously.
Get Citationsy
In 1956, Tutte showed that every planar 4-connected graph is hamiltonian. In this article, we will generalize this result and prove that polyhedra with at most three $3$-cuts are hamiltonian. In 2002 Jackson and Yu have shown this result for the subclass of triangulations. We also prove that polyhedra with at most four $3$-cuts have a hamiltonian path. It is well known that for each $k\ge 6$ non-hamiltonian polyhedra with $k$ $3$-cuts exist. We give computational results on lower bounds on the order of a possible non-hamiltonian polyhedron for the remaining open cases of polyhedra with four or five $3$-cuts.