### Generating Fullerenes

#### by Derrick Stolee

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 than fullerenes of order . 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:

where is the number of vertices, is the number of edges, and is the number of faces. Since and where is the number of faces of length , 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.

### 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 is given, the list of augmentations is finite.

#### -type augmentations

The -augmentation is an infinite family, where is a number corresponding to a path of length between two 5-faces in a fullerene. Suppose and are two 5-faces, and is a path of length between a vertex on and a vertex on . In addition, suppose that every face incident to an edge in is a 6-face and every face shares at most two edges with . If we imagine walking along , we alternate between taking a left or right edge at every vertex. Let be the 6-faces along one side of and be the 6-faces on the other side of , such that is adjacent to and (note is only adjacent to ).

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

#### -type augmentations

-type augmentations are very similar to -type augmentations since there is a path between two 5-faces bounded between faces and on either side of the path. However, for a -type augmentation there is exactly one 6-face that is incident to this path on three edges and exactly one 6-face 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.)

#### -augmentations

The -augmentation is a single augmentation, but important, as this step by itself is required to generate the carbon nanotube structures. Let be a 5-face adjacent to five 6-faces and the five faces at distance two from are , where is adjacent to . To perform an -augmentation on $p$, we add a ring of five 6-faces between the faces and faces such that 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 *-type contractions*, *-type contractions*, and *-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 -contraction exists, that suffices. We shall assume that no -contraction exists.

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

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 -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.

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.

### 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:

- If some 5-face has a -contraction, then select a 5-face using the canonical labels of the dual graph and contract on that face.
- If both -type and -type contractions exist, then restrict to the -type contractions.
- If multiple contractions remain, then restrict to those of shortest length.
- If multiple contractions remain, then restrict to contractions between two 5-faces of lowest lexicographic label in the canonical labeling of the dual graph.
- 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 -augmentations if an -contraction already exists, or only -augmentations and -type augmentations if a -type contraction already exists. Finally, we can also restrict to augmentations that will form shortest contractions. This reduces the number of augmentations slightly.

### A Note About Implementation

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.

### Online Resources

Shigeo Maruyama’s Fullerene and Carbon Nanotube Site

### 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).