Computational Combinatorics

Tag: generation

Hypohamiltonian Planar Graphs

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.

Read the rest of this entry »

Boron and Buckyballs

Recent news from the world of chemistry: the result is really the experimental observation of a special new molecule. People call it a “Boron Buckyball”, but this irritates me since we know that the buckyball is a specific fullerene on 60 vertices. In particular, it is the smallest fullerene that satisfies the independent pentagon rule. This new Boron molecule is called “Borospherene” and is quite interesting in its own right, as seen below:

The borospherene molecule. Credit: Zhai et al.

The borospherene molecule. Credit: Zhai et al.

The structure is very interesting when you consider it as a spherically-embedded (i.e. planar) graph: there are many triangular faces which create a cube-like structure, two of the faces of this cube are 6-faces, and the other four are 7-faces! These interesting heptagonal structures are particularly interesting. In the figure above, it appears to be a unit-distance embedding, and this creates a rotation in the opposing 6-faces.

Let’s dig more into the structure of this object, but also into the computational part of the experiment.
Read the rest of this entry »

Computational Combinatorics Roundup: November-December

We continue our monthly update of collecting research papers (or blog posts!) that were posted in the previous month+\varepsilon (or were missed by previous lists). So far, I’ve just been watching the arXiv updates and my Google Scholar updates. Please comment or send me an email if you have an addition. (You can even tell me about papers when you see them, and I’ll add them to the next one!)

I’ve added my own short synopsis in italics based on a cursory glance through the papers. These are not reviews which verify their correctness or quality.
Read the rest of this entry »