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 »

Advertisements