TOPICS
Search

Owens Graphs


OwensGraphs

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 J_(11) 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 GP(8,3). The proof relies on property P(L) 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 L, the 16-node fragment H, and two additional vertices cannot produce a bicubic nonhamiltonian graph with vertex connectivity 3. This remains true if each copy of L 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"].


See also

Bicubic Nonhamiltonian Graph, Horton Graphs, Quintic Nonhamiltonian Graph

Explore with Wolfram|Alpha

References

House of Graphs. "Owens Graph 76." https://houseofgraphs.org/graphs/51432.Owens, P. J. "On Regular Graphs and Hamiltonian Circuits, Including Answers to Some Questions of Joseph Zaks." J. Combin. Theory, Ser. B 28, 262-277, 1980.Owens, P. J. "Bipartite Cubic Graphs and a Shortness Exponent." Disc. Math. 44, 327-330, 1983.

Referenced on Wolfram|Alpha

Owens Graphs

Cite this as:

Weisstein, Eric W. "Owens Graphs." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/OwensGraphs.html

Subject classifications