Generating Cubic Graphs

by Derrick Stolee

Today, we return to the canonical deletion method to generate cubic graphs. Cubic graphs are 3-regular graphs, and since the degree is constant, there are many fewer cubic graphs of order n than general graphs of order n. Also, since the structure of cubic graphs is very restricted, we can use custom augmentations to generate them more quickly than using an augmentation that works for general graphs.

This implementation of the method comes from Brinkmann, Goedgebeur, and McKay in their paper Generation of Cubic graphs from Discrete Mathematics and Theoretical Computer Science. By desigining custom augmentations, they are able to restrict their generation algorithm to create only connected cubic graphs. This augmenation is paired with a canonical deletion step which removes all isomorphic duplicates. Their implementation is given in the snarkhunter software, which is the current-fastest implementation to generate cubic graphs (and snarks; the generation snarks is investigated in a different paper).

Just to be sure everyone follows, a cubic graph is a graph where every vertex has degree three. Also, we will focus on generating connected cubic graphs, since we can combine these connected graphs as components of disconnected cubic graphs.

Edge Insertions

We can create a new cubic graph by performing an edge-insertion between two edges of a cubic graph.

Edge-Insertion: Given two edges uv, ab \in E(G), subdivide uv and ab to create two new vertices, x and y, respectively. Add the edge xy.

Figure 1. Edge-Insertion

Figure 1. Edge-Insertion

If G is a connected cubic graph, then the resulting graph after an edge insertion is also connected and cubic.

Moreover, we can reverse this procedure. Let e be an edge in a cubic graph G. If we delete the edge e from G, we have exactly two vertices of degree two. If we contract one edge incident to each of these vertices, we have a cubic graph with two fewer vertices than G. We call this procedure an edge reduction. Since we will generate only connected cubic simple graphs, we say an edge is reducible if its edge reduction results in a connected simple graph. (Observe edge reductions from cubic graphs always result in cubic graphs, but may create multiedges or may disconnect the graph.)

A cubic graph is prime if it contains no reducible edges. For example, the complete graph of order four, K_4, is the smallest simple cubic graph, so no edge reductions can create a simple cubic graph (in fact, all such operations create the multigraph on 2 vertices with three edges).

Prime Augmentations

We aim to generate all prime graphs using custom augmentations. Prime graphs are built from K_4 using three types of augmentation, listed below.

K_4-Addition: Given an edge uv \in E(G), subdivide the edge into a path uxv and add a new component isomorphic to K_4. Subdivide one of the edges of the K_4 to create a new vertex y and add the edge xy.

Figure 2. $latex K_r$-Addition.

Figure 2. K_r-Addition.

Kite-Division: Given an edge uv \in E(G), remove the edge uv and add a kite on vertices x, y, a, b such that a and b are adjacent to each other and to x and y. Add the edges ux and vy.

Figure 3. Kite-division.

Figure 3. Kite-division.

Kite-Insertion: Given two edges uv, ij \in E(G) (where possibly u = i) and perform an edge-insertion to create a new edge xy and then perform a kite-division on that edge.

Figure 4. Kite-Insersion.

Figure 4. Kite-Insersion.

Each of these operations are reversible. Looking at Figures 2, 3, and 4, when we detect a structure isomorphic to the red vertices, we can remove the red vertices and reconnect the black vertices as required. This allows us to define our canonical deletion to select such a reversal of these augmentation steps.

Most importantly, if G is irreducible, then the graph resulting from one of these actions is also irreducible. That is, we did not introduce any edges which can be removed by inverting the edge-insertion augmentation.

The fact that every prime graph can be built from K_4 using these augmentations requires a short proof, given in the paper.

Generation of Cubic Graphs

The generation strategy takes the following structure:

  1. Start with K_4.
  2. Using the three prime augmentations, we build all connected prime graphs.
  3. From each prime graph, we perform edge insertions to find all connected cubic graphs.

To remove all isomorphic duplicates, we define a canonical deletion, so we will only accept an augmentation if it matches the canonical deletion. Select a deletion using the following procedure:

  1. (Edge Reduction)If there is at least one reducible edge, then select a reducible edge using the canonical labeling.
  2. (K_4-Addition) If there exists a cut-edge, then use the canonical labeling to select a cut-edge e where one of the components of G-e is a subdivided K_4.
  3. (Kite-Division) If there exists a kite whose edge-replacement is not reducible, then use the canonical labeling to select such a kite.
  4. (Kite-Insertion) If there exists a kite whose edge-replacement is a reducible edge, then use the canonical labeling to select such a kite.

By this canonical deletion procedure, we know that if there exists a reducible edge, then we will not perform any of the prime augmentations.

After implementing and executing their algorithms into the snarkhunter software, the authors reported the number of prime graphs and cubic graphs of a given order, listed in Table 1.

|V(G)| # prime graphs # cubic graphs
4 1 1
6 0 2
8 1 5
10 1 19
12 1 85
14 3 509
16 2 4,060
18 5 41,301
20 4 510,489

Table 1. Number of prime and cubic graphs of a given order.

While the number of cubic graphs grows exponentially, it is much smaller than the number of general graphs. It would be hopeless to generate all graphs of order 20, but this algorithm generates them in less than 2 seconds. I tried using geng with standard flags for controlling the maximum and minimum degree, and it took about 8 minutes. As larger values of n are considered, the difference becomes much more important.

One reason the standard generation algorithm is slow is that it is checking a lot of graphs of order below n which cannot be extended to a 3-regular graph of order n. However, it is hard to check this property, especially in a general-purpose solver.

Another improvement in the algorithm is that at least two vertices are added at every step with these augmentations.

Applications

While cubic graphs are a very nice class of graphs to generate, it may be good to adapt the algorithm to some more rigid structures that happen to be 3-regular. In other papers, the authors use this algorithm to investigate snarks and fullerenes.

Related Posts

Introduction to Canonical Deletion

Small Graphs are Reconstructible

Canonical Labelings with nauty

Computing Orbits with nauty

References

G. Brinkmann, J. Goedgebeur, B. D. McKay. Generation of Cubic Graphs. Discrete Mathematics and Theoretical Computer Science, 13:2, 2011.

G. Brinkmann, J. Goedgebeur, J. Hägglund, K. Markström, The generation and properties of snarks, arXiv:1206.6690 [math.CO].

G. Brinkmann, J. Goedgebeur, B. D. McKay. The Generation of Fullerenes, arXiv:1207.7010 [math.CO].

Advertisements