logo

Connected cubic graphs

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

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.

VerticesGirth ≥ 3Girth ≥ 4Girth ≥ 5Girth ≥ 6Girth ≥ 7Girth ≥ 8Girth ≥ 9
41000000
62100000
85200000
1019610000
12852220000
1450911091000
164060792491000
184130178054555000
2051048997546578332000
227319447143572090938385000
241179405352378081416204797574100
26209448086443275756831478584181227300
2840497138011854247149465678389046245012100
308454802280691814921378121462187120412209054454610
3218941522184590412707714386234597564856233289299543036800
34453090162062723??93990692595178284010
3611523392072541432??27542226053769507908330
38310467244165539782???4686063120130
408832736318937756165???2203234479621550
42????1009065372286143370
44?????2663620
46?????208076880
48??????0
50??????0
52??????0
54??????0
56??????0
58??????18
60??????474
62??????27169
64??????1408813
Go to top

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].

VerticesGirth ≥ 4Girth ≥ 6Girth ≥ 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
Go to top

Permutation graphs

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.

VerticesGirth ≥ 4Girth ≥ 5Girth ≥ 6Girth ≥ 7Girth ≥ 8Girth ≥ 9
8200000
10410000
121010000
142830000
16123111000
18667590000
2048154024000
224136936029000
244112313717884000
264535796424252846100
2854828142528960312597000
3071796710271206645197921100
321011803559310270747103334149600
34152626831184158003802815863859919000
36??1077159843443710
38??2064297016414782000
40???516638100
42???16751763020
44????330
46????8470
48????212940
50????10532890
52?????0
54?????0
56?????0
58?????0
60?????2
62?????61
64?????1654
Go to top

[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.


Copyright © 2010-2024 Ghent University & KU Leuven

Our website uses functional cookies to enhance your user experience. By using this site, you agree to our use of cookies. Learn more

Close