Computational Combinatorics

Category: Paper Reviews

Generating Cubic Graphs

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).
Read the rest of this entry »

Uniquely Kr-Saturated Graphs: Experiment #2

In the previous post, we defined uniquely K_r-saturated graphs and described a search to find all such graphs of a given order. One of these graphs was a 7-primitive graph of order 17. The graph is vertex-transitive, and all vertex-transitive graphs of prime order are Cayley graphs. Recall that an r-primitive graph is a uniquely K_r-saturated graph with no dominating vertex. Since Cayley graphs are regular, we search for r-primitive Cayley graphs.
Read the rest of this entry »

Uniquely Kr-Saturated Graphs: Experiment #1

My paper with Stephen Hartke, Uniquely K_r-Saturated Graphs appeared recently on the Electronic Journal of Combinatorics. This publication prompted our recent shift to the technique of orbital branching. In this post, we will see how we extended orbital branching to generate uniquely K_r-saturated graphs, which led to many new examples. In a future post, we will discuss a second computational experiment within this paper.

Read the rest of this entry »

Small Graphs are Reconstructible

One of the most famous examples of using canonical deletion was McKay’s method to verify (for small graphs) one of the oldest open problems in graph theory: the Reconstruction Conjecture. This is a natural example to discuss the benefits of canonical deletion for two reasons:

  1. It uses vertex augmentations/deletions as in our standard examples.
  2. By slightly customizing the canonical deletion, we can significantly improve the running time over simply generating graphs and testing the conjecture on all pairs.

Read the rest of this entry »