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:

  1. A graph is hypohamiltonian if it does not contain a hamilton cycle, but the deletion of any vertex does create a hamilton cycle.
  2. A planar graph is a graph that can be embedded in the plane with no edge crossings.
  3. A cubic graph is a 3-regular graph.
  4. 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].

The three smallest examples of hypohamiltonian planar cubic graphs of girth 5. The numbers give the face lengths for faces other than 5-faces. Figures by B.D. McKay.

The three smallest examples of hypohamiltonian planar cubic graphs of girth 5. The numbers give the face lengths for faces other than 5-faces. Figures by B.D. McKay.


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 xyz, then the hamilton cycle in G-x cannot use the edge yz or else we could extend that cycle to a hamilton cycle of G. This implies that x, y, and z 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.

See Also

Generating cubic graphs

plantri

Grinberg’s Theorem (Useful for proving a planar graph is not hamiltonian)

Planar Hypohamiltonian Data (by Reza Jooyandeh)

References

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 plantri)

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.

Advertisements