Polyhedra of small order and their Hamiltonian properties (Q1907113)

This paper describes the result of an extensive computer enumeration of several classes of polyhedra (in Euclidean three-space, with combinatorially isomorphic polyhedra identified), for instance all polyhedra with up to 13 vertices, simplicial polyhedra with up to 16 vertices, 4-regular ones with up to 22 vertices, and non-Hamiltonian ones with up to 15 vertices. The principles of computation are explained, as well as certain methods to reduce computational complexity. In particular, the following substantial improvement of a theorem of Tutte is proved. Let \(P_{n,k}\) be the set of polyhedral graphs with \(n\) vertices and \(k\) faces. If \(k \geq n\), every graph in \(P_{n,k}\) (with the single exception of the wheel) can be generated by applying a face-splitting operation to some graph in \(P_{n,k - 1}\). Furthermore, some smallest graphs with certain properties are determined, for example the smallest non-Hamiltonian planar graphs satisfying certain toughness properties and the smallest non-Hamiltonian 3-connected Delaunay triangulation. Improved upper and lower bounds of the size of the smallest non-Hamiltonian inscribable polyhedra are also given, along with several examples and conjectures. Unfortunately, table VIII has got the same header as table VII. The header of table VIII should read ``The Number of Nonisomorphic 4-Connected Polyhedral Graphs Having \(n\) Vertices and \(k\) Faces''.