This page provides access to the ever popular listings of cubic graphs together with a variety of data relating to these graphs. Please note that these pages are being developed incrementally on an "as-needed" basis, so if you want anything, then just ask me on gordon@cs.uwa.edu.au and unless its a bad time, then I will probably oblige.

Most of this work originates from my PhD thesis
*Constructive Enumeration of Graphs*, though the techniques
used there are now largely obsolete. At present the best cubic graph
generation program is written by, and available from
Gunnar Brinkmann.
The data from the snarks section was generated by Gunnar, so thanks to
him for letting me incorporate it into this database.

Exact numbers of cubic graphs are known by results of Robinson and Wormald for values up to 40 vertices. The cubic graphs on up to 20 vertices, together with some smaller families of high girth cubic graphs on higher numbers of vertices are available. The larger numbers in the table, other than the Robinson/Wormald results are due to Gunnar Brinkmann.

Each number in the table below is a link to a file of graphs in graph6 format. The largest file is the cubics on 22 vertices at 300Mb.

Vertices | girth >= 3 | girth >= 4 | girth >= 5 | girth >= 6 | girth >= 7 | girth >= 8 |
---|---|---|---|---|---|---|

4 | 1 | 0 | 0 | 0 | 0 | 0 |

6 | 2 | 1 | 0 | 0 | 0 | 0 |

8 | 5 | 2 | 0 | 0 | 0 | 0 |

10 | 19 | 6 | 1 | 0 | 0 | 0 |

12 | 85 | 22 | 2 | 0 | 0 | 0 |

14 | 509 | 110 | 9 | 1 | 0 | 0 |

16 | 4060 | 792 | 49 | 1 | 0 | 0 |

18 | 41301 | 7805 | 455 | 5 | 0 | 0 |

20 | 510489 | 97546 | 5783 | 32 | 0 | 0 |

22 | 7319447 | 1435720 | 90938 | 385 | 0 | 0 |

24 | 117940535 | 23780814 | 1620479 | 7574 | 1 | 0 |

26 | 2094480864 | 432757568 | 31478584 | 181227 | 3 | 0 |

28 | 40497138011 | ? | 656783890 | 4624501 | 21 | 0 |

30 | 845480228069 | ? | ? | 122090544 | 546 | 1 |

32 | 18941522184590 | ? | ? | ? | 30368 | 0 |

34 | 453090162062723 | ? | ? | ? | ? | 1 |

36 | 11523392072541432 | ? | ? | ? | ? | 3 |

38 | 310467244165539782 | ? | ? | ? | ? | 13 |

40 | 8832736318937756165 | ? | ? | ? | ? | 155 |

Vertices | Graphs |
---|---|

10 | 14 |

12 | 57 |

14 | 341 |

16 | 2828 |

18 | 30468 |

20 | 396150 |

The following table gives the diameters of the cubic graphs on up to 20 vertices.

Vertices | d=2 | d=3 | d=4 | d=5 | d=6 | d=7 | d=8 | d=9 | d=10 | d=11 | d=12 | d=13 | d=14 |
---|---|---|---|---|---|---|---|---|---|---|---|---|---|

6 | 2 | ||||||||||||

8 | 2 | 3 | |||||||||||

10 | 1 | 15 | 2 | 1 | |||||||||

12 | 34 | 43 | 6 | 2 | |||||||||

14 | 34 | 351 | 93 | 24 | 6 | 1 | |||||||

16 | 14 | 2167 | 1499 | 261 | 101 | 14 | 4 | ||||||

18 | 1 | 12301 | 22992 | 4400 | 1229 | 310 | 55 | 12 | 1 | ||||

20 | 1 | 57628 | 338356 | 90870 | 17281 | 5145 | 948 | 220 | 36 | 4 | |||

22 | 185836 | 4692045 | 2013271 | 321788 | 84159 | 17894 | 3516 | 799 | 118 | 20 | 1 |

A *snark* is defined to be a cyclically 4-edge connected cubic graph
with chromatic index 4 and girth at least 5. The really important part of
this definition is that the graph has chromatic index 4; the statement
that all cubic graphs of chromatic index 4 are non-planar is equivalent
to the four-colour theorem, and hence a planar snark (a boojum) would be a
counterexample to the four-colour theorem. The other adjectives are all
there to eliminate "trivial" cases where the graph can be seen to be
an easy modification of a related graph of chromatic index 4. For example,
we do not need to consider graphs with triangles, because we can simply
contract a triangle to a point without altering the essential chromatic
index property.

Gunnar Brinkmann's cubic graph generation program was used to construct snarks of all orders up to 28.

Each number in the following table represents a file of snarks, all of which are stored in the graph6 format. The files contain all snarks of cyclic edge-connectivity greater than or equal to the stated value, hence the graphs with cyclic edge-connectivity greater than 4 appear in several files.

#vertices | Cyc-con >= 4 | Cyc-con >= 5 | Cyc-con >= 6 |
---|---|---|---|

10 | 1 | 1 | |

12 | 0 | 0 | |

14 | 0 | 0 | |

16 | 0 | 0 | |

18 | 2 | 0 | |

20 | 6 | 1 | |

22 | 20 | 2 | |

24 | 38 | 2 | |

26 | 280 | 10 | |

28 | 2900 | 75 | 1 |

A compressed tarfile (only 33K) containing all the above files is also available. The files, though not in the graph6 format are also available via anonymous ftp from Gunnar's home university: ftp.uni-bielefeld.de in pub/math/graphs/SNARKS.

Chromatic polynomials have been computed for many of the above graphs. Each chromatic polynomial is given with respect to the tree basis. For example, the chromatic polynomial of the Petersen graph is given as

10 0 0 36 -120 180 -170 114 -56 21 -6 1where the initial 10 refers to the degree of the polynomial, and the subsequent 11 coefficients give the coefficients of the chromatic polynomial with respect to the basis {Ti} where Ti is the chromatic polynomial of a tree on i vertices. Therefore T0 = 1, T1 = x, T2 = x(x-1) and in general Ti = x(x-1)^(i-1).

The files of chromatic polynomials are also compressed with gzip. The listings are in the same order as the listings of the cubic graphs if it is necessary to find which graph belongs to which polynomial. The only file above 120K is the chromatic polynomials of the 18-vertex cubics which occupies 1.2Mb.

Given a family of polynomials, it is natural to immediately think about computing their complex roots and to see whether any patterns arise that may lead to interesting theorems. When one does this with chromatic polynomials of graphs there are some quite striking patterns which are currently unexplained. A paper by Ron Read and myself investigates some of these patterns and gives a few answers. One of the long-standing questions was whether it was possible for the chromatic polynomial of a graph to have roots whose real parts were negative. The only reason that this question is longstanding is that it seems necessary to go to quite large graphs before chromatic polynomials exhibiting this behaviour arise. In particular, I discovered that the cubic graphs of large girth had some roots with quite significant negative real parts.

Vertices | girth >= 3 | girth >= 4 | girth >= 5 | girth >= 6 | girth >= 7 | girth >= 8 |
---|---|---|---|---|---|---|

4 | 1 | 0 | 0 | 0 | 0 | 0 |

6 | 2 | 1 | 0 | 0 | 0 | 0 |

8 | 5 | 2 | 0 | 0 | 0 | 0 |

10 | 19 | 6 | 1 | 0 | 0 | 0 |

12 | 85 | 22 | 2 | 0 | 0 | 0 |

14 | 509 | 110 | 9 | 1 | 0 | 0 |

16 | 4060 | 792 | 49 | 1 | 0 | 0 |

18 | 41301 | 7805 | 455 | 5 | 0 | 0 |

20 | 510489 | 97546 | 5783 | 32 | 0 | 0 |

22 | 7319447 | 1435720 | 90938 | 385 | 0 | 0 |

24 | 117940535 | 23780814 | 1620479 | 7574 | 1 | 0 |

26 | 2094480864 | 432757568 | 31478584 | 181227 | 3 | 0 |

28 | 40497138011 | ? | 656783890 | 4624501 | 21 | 0 |

30 | 845480228069 | ? | ? | 122090544 | 546 | 1 |

Gordon Royle, October 1996, gordon@cs.uwa.edu.au