Cubic graphs and Snarks

Home CAAGT Authors Gunnar Brinkmann Jan Goedgebeur Brendan McKay

Cubic graphs and Snarks Snarkhunter is a generator for connected cubic graphs and snarks. Snarks are cyclically 4-edge connected cubic graphs with chromatic index 4 and girth at least 4 or 5. New: snarkhunter can now also be used to generate connected cubic graphs and snarks with girth at least k efficiently (for k ≤ 7). The algorithms used in the generator are described in: G. Brinkmann, J. Goedgebeur and B.D. McKay, Generation of Cubic graphs, Discrete Mathematics and Theoretical Computer Science, 13(2):69-80, 2011. G. Brinkmann, J. Goedgebeur, J. Hagglund and K. Markstrom, Generation and properties of Snarks, Journal of Combinatorial Theory, Series B, 103(4):468-488, 2013 (arXiv | DOI). G. Brinkmann and J. Goedgebeur, Generation of cubic graphs and snarks with large girth, Journal of Graph Theory, 86(2):255-272, 2017 (arXiv | DOI). The generator can be downloaded here and a short manual can be found here. Snarkhunter is released under the GNU General Public License (GPL) and has been tested on Linux and Mac OS X. Installation instructions: Download, extract and configure nauty (snarkhunter requires nauty 2.5 or a more recent version). Compile the nauty libraries using: "make nautyW1.a" and "make nautyL1.a" Copy the following files to the snarkhunter directory: nausparse.h nauty.h nautyW1.a nautyL1.a Compile using the command "make". The counts of cubic graphs (including downloadable lists) can be found here at the House of Graphs and the complete lists of snarks can be found here. Don't hesitate to contact us at jan.goedgebeur[at]ugent.be if you have any further questions or suggestions.