Cubic Graphs

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.

Table of Contents

All cubic graphs

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.

Connected cubic graphs
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


3-connected cubic graphs (no girth restriction)
Vertices Graphs
10 14
12 57
14 341
16 2828
18 30468
20 396150

Properties

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

Diameters of the connected cubic graphs
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


Snarks

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

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 1
where 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.

Chromatic polynomials of connected cubic graphs
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