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 than general graphs of order . 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.
We can create a new cubic graph by performing an edge-insertion between two edges of a cubic graph.
Edge-Insertion: Given two edges , subdivide and to create two new vertices, and , respectively. Add the edge .
If 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 be an edge in a cubic graph . If we delete the edge from , 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 . 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, , 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).
We aim to generate all prime graphs using custom augmentations. Prime graphs are built from using three types of augmentation, listed below.
-Addition: Given an edge , subdivide the edge into a path and add a new component isomorphic to . Subdivide one of the edges of the to create a new vertex and add the edge .
Kite-Division: Given an edge , remove the edge and add a kite on vertices such that and are adjacent to each other and to and . Add the edges and .
Kite-Insertion: Given two edges (where possibly ) and perform an edge-insertion to create a new edge and then perform a kite-division on that edge.
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 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 using these augmentations requires a short proof, given in the paper.
Generation of Cubic Graphs
The generation strategy takes the following structure:
- Start with .
- Using the three prime augmentations, we build all connected prime graphs.
- 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:
- (Edge Reduction)If there is at least one reducible edge, then select a reducible edge using the canonical labeling.
- (-Addition) If there exists a cut-edge, then use the canonical labeling to select a cut-edge where one of the components of is a subdivided .
- (Kite-Division) If there exists a kite whose edge-replacement is not reducible, then use the canonical labeling to select such a kite.
- (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.
|# prime graphs||# cubic graphs|
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 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 which cannot be extended to a 3-regular graph of order . 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.
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.
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].