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:
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 |
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 |
---|---|---|---|
6 | 1 | 0 | 0 |
8 | 1 | 0 | 0 |
10 | 2 | 0 | 0 |
12 | 5 | 0 | 0 |
14 | 13 | 1 | 0 |
16 | 38 | 1 | 0 |
18 | 149 | 3 | 0 |
20 | 703 | 10 | 0 |
22 | 4132 | 28 | 0 |
24 | 29579 | 162 | 0 |
26 | 245627 | 1201 | 0 |
28 | 2291589 | 11415 | 0 |
30 | 23466857 | 125571 | 1 |
32 | 259974248 | 1514489 | 0 |
34 | 3087698618 | 19503476 | 1 |
36 | 39075020582 | 265448847 | 3 |
38 | 524492748500 | 3799509760 | 10 |
40 | ? | 57039155060 | 101 |
42 | ? | 896293917129 | 2510 |
44 | ? | ? | 79605 |
46 | ? | ? | 2607595 |
48 | ? | ? | 81716416 |
50 | ? | ? | 2472710752 |
[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.