Hypohamiltonian Planar Graphs
by Derrick Stolee
Brendan McKay uploaded a short-but-sweet article to the arXiv titled Hypohamiltonian planar cubic graphs with girth five. Let’s quickly break down all of the words of this title:
- A graph is hypohamiltonian if it does not contain a hamilton cycle, but the deletion of any vertex does create a hamilton cycle.
- A planar graph is a graph that can be embedded in the plane with no edge crossings.
- A cubic graph is a 3-regular graph.
- The girth of a graph is the length of the shortest cycle.
McKay details the search for the smallest (and first known) graphs of this type, which have order 76. There are three non-isomorphic examples. The data for these graphs (and more) is available online [Note: at this time, it appears the data is not yet online].
We now abbreviate Hypohamiltonian Planar Cubic Graphs with Girth 5 as HPCG5s.
If we remove the all restrictions, then the Petersen graph is the smallest hypohamiltonian graph.
If we remove the degree restriction, then Jooyandeh, McKay, Ostergârd, Pettersson and Zamfirescu demonstrated that the smallest hypohamiltonian planar graph with girth 5 has order 45.
If we remove the degree and girth restrictions, then Jooyandeh, McKay, Ostergârd, Pettersson and Zamfirescu found 25 hypohamiltonian planar graphs of order 40 with girth 4.
I cannot find an exact reference to saying that having 3-cycles is a problem, but if we have a 3-cycle , then the hamilton cycle in cannot use the edge or else we could extend that cycle to a hamilton cycle of . This implies that , , and all have degree at least four, which makes the graph more dense and more likely to have a hamilton cycle.
I do not know of any examples of hypohamiltonian planar cubic graphs of girth 4, as all examples of hypohamiltonian planar graphs of girth 4 contain some vertices of larger degree.
There are some properties that are known about HPCG5s, including being 3-connected and cyclicly 4-connected. Being 3-connected (we must delete at least three vertices in order to separate the graph) implies that the graph has (essentially) a unique planar embedding. Being cyclicly 4-connected means that we must delete at least four edges in order to separate the graph into at least two components containing cycles. This avoids the issue of deleting the three edges incident to a single vertex, which trivially demonstrates that the edge connectivity is three.
Since a HPCG5 is cubic, has girth 5, and is 3-connected, its dual is a planar triangulation with minimum degree five. Thus, McKay uses
plantri to generate the duals before converting to the graphs we consider (
plantri is worth a post on its own). Before testing for hypohamiltonicity, McKay tests the connectivity requirements. However, the search does not have significant pruning mechanisms due to the strangeness of these objects (and the global nature of hypohamiltonicity). McKay summarizes this concept in the quote below:
“No theory is known which could efficiently restrict the search to a small subclass sure to contain the hypohamiltonian graphs, so we just tested all of them.”
In contrast, Jooyandeh, McKay, Ostergârd, Pettersson and Zamfirescu used Grinberg’s Theorem in order to generate planar graphs that were definitely not hamiltonian, but their search is not guaranteed to be complete, as there is no proof that a hypohamiltonian graph can be proven non-hamiltonian by Grinberg’s Theorem.
McKay reports the search took 8 years to complete, even after using a custom algorithm for testing hamiltonicity that works very quickly on planar cubic graphs.
Grinberg’s Theorem (Useful for proving a planar graph is not hamiltonian)
Planar Hypohamiltonian Data (by Reza Jooyandeh)
G. Brinkmann, O. Delgado Friedrichs, S. Lisken, A. Peeters and N. Van Cleemput,
CaGe—a virtual environment for studying some special classes of plane graphs—an update, MATCH Commun. Math. Comput. Chem. 63 (2010) 533–552.
G. Brinkmann and B. D. McKay, Construction of planar triangulations with minimum
degree 5, Discrete Math. 301 (2005) 147–163. (see
M. Jooyandeh, B. D. McKay, P. Ostergârd, V. Pettersson and C. T. Zamfirescu, Planar hypohamiltonian graphs on 40 vertices, arXiv:1302.2698.
B.D. McKay, Hypohamiltonian planar cubic graphs with girth five, arXiv:1507.07197 [math.CO].
B.D. McKay, Planar Graph Data.