The term "Owens graphs" is used in this work for several named graphs associated with P. J. Owens.
The 76-node Owens graph (Owens 1980) provides the smallest known example of a polyhedral quintic
nonhamiltonian graph. It was constructed by inserting copies of the skeleton
of the gyroelongated pentagonal pyramid at 10 of the 11 vertices
of the Herschel graph.
Owens (1983) reported a 78-node bicubic nonhamiltonian graph obtained by operations on the generalized
Petersen graph .
The proof relies on property
of a 30-node fragment (Owens 1983, p. 328), which
asserts that a cycle visiting every vertex
of the fragment and at least one outside vertex uses
exactly two of its four linking edges. However, the
reconstructed fragment admits such a cycle using all
four linking edges, and the reconstructed 78-node graph
admits a Hamiltonian cycle.
Exhaustive enumeration shows that rearranging the linking edges among two copies of the reconstructed 30-node fragment , the 16-node fragment
, and two additional vertices
cannot produce a bicubic nonhamiltonian
graph with vertex connectivity 3. This
remains true if each copy of
is independently replaced by the fragment obtained by deleting
the endpoints of any edge of the 32-node Horton
graph. The intended construction therefore remains unclear.
The 76-node graph is implemented in the Wolfram Language as GraphData["OwensGraph76"].