Connected cubic graphs

Some of the data available here is a copy (as of 2010-07-13) of the data available at Gordon Royle's web page (c) 1996 Gordon Royle.

The graph lists are currently only available in 'graph6' format. The larger files are compressed with gzip.

The following lists are available:

Cubic graphs

All numbers for minimum girths 3, 4 and 5 were independently confirmed by genreg, minibaum and snarkhunter up to 30 vertices. The numbers for minimum girths 3, 4 and 5 for 32 vertices were independently confirmed by minibaum and snarkhunter. All numbers for minimum girth 3 were also theoretically determined by Robinson and Wormald [1].

The numbers for minimum girths 6 and 7 were obtained by snarkhunter. They were independently confirmed by genreg and minibaum up to 34 vertices for minimum girth 6 and up to 38 vertices for minimum girth 7. The numbers for minimum girth 8 were independently confirmed by genreg and minibaum. The graphs with minimum girth 9 were obtained by and McKay et al. [2]. They were independently confirmed by Brinkmann et al. [3] for order 58.

Vertices girth ≥ 3 girth ≥ 4 girth ≥ 5 girth ≥ 6 girth ≥ 7 girth ≥ 8 girth ≥ 9
4 1 0 0 0 0 0 0
6 2 1 0 0 0 0 0
8 5 2 0 0 0 0 0
10 19 6 1 0 0 0 0
12 85 22 2 0 0 0 0
14 509 110 9 1 0 0 0
16 4060 792 49 1 0 0 0
18 41301 7805 455 5 0 0 0
20 510489 97546 5783 32 0 0 0
22 7319447 1435720 90938 385 0 0 0
24 117940535 23780814 1620479 7574 1 0 0
26 2094480864 432757568 31478584 181227 3 0 0
28 40497138011 8542471494 656783890 4624501 21 0 0
30 845480228069 181492137812 14621871204 122090544 546 1 0
32 18941522184590 4127077143862 345975648562 3328929954 30368 0 0
34 453090162062723 ? ? 93990692595 1782840 1 0
36 11523392072541432 ? ? 2754222605376 95079083 3 0
38 310467244165539782 ? ? ? 4686063120 13 0
40 8832736318937756165 ? ? ? 220323447962 155 0
42 ? ? ? ? 10090653722861 4337 0
44 ? ? ? ? ? 266362 0
46 ? ? ? ? ? 20807688 0
48 ? ? ? ? ? ? 0
50 ? ? ? ? ? ? 0
52 ? ? ? ? ? ? 0
54 ? ? ? ? ? ? 0
56 ? ? ? ? ? ? 0
58 ? ? ? ? ? ? 18
60 ? ? ? ? ? ? 474
62 ? ? ? ? ? ? 27169
64 ? ? ? ? ? ? 1408813

Cubic bipartite graphs

A graph G is bipartite if it is possible to partition the set of vertices of G into two subsets A and B such that every edge of G joins a vertex of A to a vertex of B. The graphs listed in the following table were generated using minibaum. Most of these counts were determined in [4].

Vertices girth ≥ 4 girth ≥ 6 girth ≥ 8
6100
8100
10200
12500
141310
163810
1814930
20703100
224132280
24295791620
2624562712010
282291589114150
30234668571255711
3225997424815144890
343087698618195034761
36390750205822654488473
38524492748500379950976010
40?57039155060101
42?8962939171292510
44??79605
46??2607595
48??81716416
50??2472710752

References

[1] R. W. Robinson and N. C. Wormald, Numbers of cubic graphs. J. Graph Theory, 7:463-467, 1983.
[2] B. D. McKay, W. Myrvold and J. Nadon, Fast backtracking principles applied to find new cages, 9th Annual ACM-SIAM Symposium on Discrete Algorithms, 188-191, 1998.
[3] G. Brinkmann, B. D. McKay and C. Saager, The smallest cubic graphs of girth 9, Combinatorics, Probability and Computing, 5:1-13, 1995.
[4] J. Goedgebeur, A counterexample to the pseudo 2-factor isomorphic graph conjecture, Discrete Applied Mathematics, 193:57-60, 2015.

Go to top