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 |
A permutation graph (or sometimes also called cycle permutation graph) is a cubic graph which has a 2-factor that consists of two induced cycles. The graphs listed in the following table were generated by Goedgebeur and Renders using the specialised generation algorithm for permutation graphs which is described in [5]. The source code of this algorithm can be found here .
Note that the girth of permutation graphs of order larger than 6 must be at least 4. We omitted the single permutation graph of girth 3 on order 6 from the table below.
Lists of non-hamiltonian permutation graphs and permutation snarks can be found on the snarks page.
Vertices | Girth ≥ 4 | Girth ≥ 5 | Girth ≥ 6 | Girth ≥ 7 | Girth ≥ 8 | Girth ≥ 9 |
---|---|---|---|---|---|---|
8 | 2 | 0 | 0 | 0 | 0 | 0 |
10 | 4 | 1 | 0 | 0 | 0 | 0 |
12 | 10 | 1 | 0 | 0 | 0 | 0 |
14 | 28 | 3 | 0 | 0 | 0 | 0 |
16 | 123 | 11 | 1 | 0 | 0 | 0 |
18 | 667 | 59 | 0 | 0 | 0 | 0 |
20 | 4815 | 402 | 4 | 0 | 0 | 0 |
22 | 41369 | 3602 | 9 | 0 | 0 | 0 |
24 | 411231 | 37178 | 84 | 0 | 0 | 0 |
26 | 4535796 | 424252 | 846 | 1 | 0 | 0 |
28 | 54828142 | 5289603 | 12597 | 0 | 0 | 0 |
30 | 717967102 | 71206645 | 197921 | 1 | 0 | 0 |
32 | 10118035593 | 1027074710 | 3334149 | 6 | 0 | 0 |
34 | 152626831184 | 15800380281 | 58638599 | 190 | 0 | 0 |
36 | ? | ? | 1077159843 | 4437 | 1 | 0 |
38 | ? | ? | 20642970164 | 147820 | 0 | 0 |
40 | ? | ? | ? | 5166381 | 0 | 0 |
42 | ? | ? | ? | 167517630 | 2 | 0 |
44 | ? | ? | ? | ? | 33 | 0 |
46 | ? | ? | ? | ? | 847 | 0 |
48 | ? | ? | ? | ? | 21294 | 0 |
50 | ? | ? | ? | ? | 1053289 | 0 |
52 | ? | ? | ? | ? | ? | 0 |
54 | ? | ? | ? | ? | ? | 0 |
56 | ? | ? | ? | ? | ? | 0 |
58 | ? | ? | ? | ? | ? | 0 |
60 | ? | ? | ? | ? | ? | 2 |
62 | ? | ? | ? | ? | ? | 61 |
64 | ? | ? | ? | ? | ? | 1654 |
[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.
[5] J. Goedgebeur and J. Renders, Generation of Cycle Permutation Graphs and Permutation Snarks, manuscript, 2024.