### Generating Fullerenes

Today, we discuss “Generation of Fullerenes” by Brinkmann, Goedgebuer, and McKay, recently published in the Journal of Chemical Information and Modeling. A fullerene for our purposes is a cubic planar graph where every face has length 5 or 6. However, the definition of fullerene as a molecule is valuable as well (and why this paper was published in a chemistry journal). Since we previously discussed generating cubic graphs, we could use that algorithm and restrict our output to graphs that satisfy our requirements, but this method is wasteful as there are many more cubic graphs of order $n$ than fullerenes of order $n$. Since their method uses canonical deletion, we only need to describe our base objects and our augmentation step.

### Structural Properties of Fullerenes

Since fullerenes are planar, they satisfy Euler’s formula:
$n - e + f = 2$
where $n$ is the number of vertices, $e$ is the number of edges, and $f$ is the number of faces. Since $e = \frac{3}{2}n$ and $e = \frac{5}{2}f_5 + \frac{6}{2}f_6$ where $f_i$ is the number of faces of length $i$, we find that a fullerene contains exactly 12 5-faces and the rest are 6-faces.

A fullerene satisfies the independent pentagon rule (IPR) if no 5-faces are adjacent in the dual (i.e. no 5-faces share an edge). The smallest IPR fullerene is the buckyball (or buckminsterfullerene), named after Buckminster Fuller who started this whole mess. The buckyball has 60 vertices and is commonly known by the shape of some soccer balls. Something fun about the symmetry of the buckyball: the 5-faces are antipodal in the dual, but the faces are switched. See Figure 1, which shows the buckyball centered at a 5-face.

Figure 1. The buckyball centered on a 5-face. Source: Wikipedia.

### Generating Fullerenes

As when generating cubic graphs, we will perform canonical deletion subject to custom augmentation steps. These steps are designed such that at every point our current graph is a fullerene. We will replace certain connected induced subgraphs with larger connected subgraphs in expansion steps, and the reverse is a reduction step. It was shown by Brinkmann, Graver, and Justus that no finite set of replacements suffices to generate all fullerenes, so an infinite family must be used. However, the infinite family used can be generated algorithmically, and when a maximum order $n$ is given, the list of augmentations is finite.

#### $L$-type augmentations

The $L_i$-augmentation is an infinite family, where $i$ is a number corresponding to a path of length $i +2$ between two 5-faces in a fullerene. Suppose $p_1$ and $p_2$ are two 5-faces, and $P$ is a path of length $i+2$ between a vertex on $p_1$ and a vertex on $p_2$. In addition, suppose that every face incident to an edge in $P$ is a 6-face and every face shares at most two edges with $P$. If we imagine walking along $P$, we alternate between taking a left or right edge at every vertex. Let $f_1,\dots,f_{i+2}$ be the 6-faces along one side of $P$ and $g_1,\dots,g_{i+2}$ be the 6-faces on the other side of $P$, such that $g_{i}$ is adjacent to $f_{i-1}$ and $f_i$ (note $g_1$ is only adjacent to $f_1$).

With this path, the $L_i$ augmentation inserts $i$ 6-faces between the $f_i$‘s and $g_i$‘s, moves the 5-faces $p_1$ and $p_2$ closer together, and adds two 6-faces adjacent to the previous neighbors of $p_1$ and $p_2$. (The paper has a very nice figure that I won’t even try to replicate here.)

#### $B$-type augmentations

$B$-type augmentations are very similar to $L$-type augmentations since there is a path between two 5-faces bounded between faces $f_1, \dots, f_i$ and $g_1,\dots, g_i$ on either side of the path. However, for a $B$-type augmentation there is exactly one 6-face $f_j$ that is incident to this path on three edges and exactly one 6-face $g_j$ that is incident to the path on one edge. Essentially, this forms a “turn” in the path between the 5-faces. Similarly, we pull the 5-faces closer together and insert 6-faces on the outsides. (Again, the paper has a very nice figure. Seriously go look at it.)

#### $F$-augmentations

The $F$-augmentation is a single augmentation, but important, as this step by itself is required to generate the carbon nanotube structures. Let $p$ be a 5-face adjacent to five 6-faces $f_1,\dots,f_5$ and the five faces at distance two from $p$ are $g_1,\dots,g_5$, where $f_i$ is adjacent to $f, f_{i-1}, f_{i+1}, g_{i}, g_{i+1}$. To perform an $F$-augmentation on $p$, we add a ring of five 6-faces $h_1,\dots,h_5$ between the faces $f_i$ and faces $g_i$ such that $h_i$ is adjacent to $h_{i-1}, h_{i+1}, f_{i}, f_{i+1}, g_{i}, g_{i+1}$.

Observe that these augmentations have natural inversions, which I will call $L$-type contractions, $B$-type contractions, and $F$-contractions. It may not be obvious as to why every fullerene is generated by this family of augmentations, so I will sketch a short proof here. We shall consider a fullerene and test that some contraction exists within the graph. If an $F$-contraction exists, that suffices. We shall assume that no $F$-contraction exists.

Consider the fullerene embedded on a sphere as in the figure below.

Figure 2. A fullerene on the sphere, some 5-faces shown.

Now, start walking from one of the 5-faces, alternating left and right turns whenever reaching a new vertex until reaching a 5-face. If we reach a 5-face other than the one we started at, then we have an $L$-type contraction. Otherwise, we have made a closed curve about the sphere that starts and ends at a common 5-face, as in the figure below.

Figure 3. Walking from a 5-face back to itself.

However, every other 5-face lies to one side of this curve. Thus, there is some point where we can adjust our walk by making two right turns (or two left turns) in a row to then reach a distinct 5-face, as in the figure below.

Figure 4. Making one turn to form a $B$-type contraction.

### The Canonical Deletion

It takes some careful work to implement the given augmentations, and their inversions. However, once that has been dealt with, we can make a simple canonical deletion. Among all types of contractions in the graph, follow the filtering process below:

1. If some 5-face has a $F$-contraction, then select a 5-face using the canonical labels of the dual graph and contract on that face.
2. If both $B$-type and $L$-type contractions exist, then restrict to the $B$-type contractions.
3. If multiple contractions remain, then restrict to those of shortest length.
4. If multiple contractions remain, then restrict to contractions between two 5-faces of lowest lexicographic label in the canonical labeling of the dual graph.
5. If multiple contractions remain, then they are between the same pair of 5-faces, have the same length, and have the same type. Use the list of 6-faces surrounding the contraction to find the lexicographically-least tuple in the canonical labels of the dual graph.

This process of canonical deletion allows us to restrict our augmentations to be only $F$-augmentations if an $F$-contraction already exists, or only $F$-augmentations and $B$-type augmentations if a $B$-type contraction already exists. Finally, we can also restrict to augmentations that will form shortest contractions. This reduces the number of augmentations slightly.

The authors seem to use the dual graph as their generation tool, and I agree that this is the better option. Since the augmentations involve shifting faces and adding faces, and the canonical deletion uses the dual graph, it is only fitting that we use the dual graph. Thus, we are shifting vertices and adding vertices, a much more natural operation.

### Software

plantri and fullgen are Brinkmann and McKay’s software for generating certain classes of planar graphs, such as triangulations and fullerenes.

buckygen

### Online Resources

Fullerene on Wikipedia

Fullerene on MathWorld

Fullerense on House of Graphs

Shigeo Maruyama’s Fullerene and Carbon Nanotube Site

The Fullgen Page

### References

G. Brinkmann, J. Goedgebeur and B.D. McKay, Generation of Fullerenes, Journal of Chemical Information and Modeling, 52(11), pages 2910-2918 (2012). (arXiv version)

G. Brinkmann, A.W.M. Dress, A Constructive Enumeration of Fullerenes, Journal of Algorithms 23(2) 345-358, (1997).

J. R. Dias, Algorithm for generating fullerenes by circumscribing, Journal of Chemical Information and Computer Sciences 34 (2), pp 248-251 (1994).

B. Plestenjak, T. Pisanski, A. Graovac, Generating Fullerenes at Random, Journal of Chemical Information and Computer Sciences 36(4), pp 825-828 (1996).