Regular Graphs

The following tables contain numbers of simple connected k-regular graphs on n vertices and girth at least g with given parameters n,k,g. If a number in the table is a link, then you can get further information about the graphs including adjacency lists or shortcode files. A description of the shortcode coding can be found in the GENREG-manual.

Most of the numbers were obtained by the computer program GENREG. It does not only compute the number of regular graphs for the chosen parameters but even constructs the desired graphs. The large cases with k=3 were solved by Gunnar Brinkmann, who implemented a very efficient algorithm for cubic graphs. His group at the University of Ghent also provides a searchable online database for general graphs, the House of Graphs.

If you want to compute regular graphs on your own or perhaps try one of the unsolved cases, you can get a free version of the generator. There are executables available for DEC-Alpha/ SGI Workstations and Linux/ Win NT PCs. The package genreg.tar contains a makefile for easy installation on any UNIX machine. There is a german and an english latex version of the manual included as well as a short C-programm that demonstrates how to read shortcode files.

When using GENREG for your publications, please cite

M. Meringer: Fast Generation of Regular Graphs and Construction of Cages. Journal of Graph Theory 30, 137-146, 1999.

Table of contents




Connected regular graphs

The following table contains numbers of connected regular graphs with given number of vertices and degree. For the empty fields the number is not yet known (to me). The latest numbers (for n=19,k=4; n=16,k=6; n=16,k=7) have been contributed by Jason Kimberley (University of Newcastle, Australia, June 2009), who ran GENREG on up to 250 cores.

Vertices Degree 3 Degree 4 Degree 5 Degree 6 Degree 7
4 1 0 0 0 0
5 0 1 0 0 0
6 2 1 1 0 0
7 0 2 0 1 0
8 5 6 3 1 1
9 0 16 0 4 0
10 19 59 60 21 5
11 0 265 0 266 0
12 85 1544 7848 7849 1547
13 0 10778 0 367860 0
14 509 88168 3459383 21609300 21609301
15 0 805491 0 1470293675 0
16 4060 8037418 2585136675 113314233808 733351105934
17 0 86221634 0   0
18 41301 985870522      
19 0 11946487647      
20 510489        
22 7319447        
24 117940535        
26 2094480864        

Back to table of contents .


Connected regular graphs with girth at least 4

The following table contains numbers of connected regular graphs with given number of vertices and degree and girth at least 4. For the empty fields the number is not yet known (to me).

Vertices Degree 3 Degree 4 Degree 5 Degree 6 Degree 7
6 1 0 0 0 0
7 0 0 0 0 0
8 2 1 0 0 0
9 0 0 0 0 0
10 6 2 1 0 0
11 0 2 0 0 0
12 22 12 1 1 0
13 0 31 0 0 0
14 110 220 7 1 1
15 0 1606 0 1 0
16 792 16828 388 9 1
17 0 193900 0 6 0
18 7805 2452818 406824 267 8
19 0 32670330 0   0
20 97546 456028474      
22 1435720        
24 23780814        
26 432757568        

Back to table of contents .


Connected regular graphs with girth at least 5

The following table contains numbers of connected regular graphs with given number of vertices and degree and girth at least 5. For the empty fields the number is not yet known (to me).

Vertices Degree 3 Degree 4 Degree 5
10 1 0 0
11 0 0 0
12 2 0 0
13 0 0 0
14 9 0 0
15 0 0 0
16 49 0 0
17 0 0 0
18 455 0 0
19 0 1 0
20 5783 2 0
21 0 8 0
22 90938 131 0
23 0 3917 0
24 1620479 123859 0
25 0 4131991 0
26 31478582 132160608 0
27 0   0
28 656783890   0
30     4
32     90

Back to table of contents .


Connected regular graphs with girth at least 6

The following table contains numbers of connected regular graphs with given number of vertices and degree and girth at least 6. For the empty fields the number is not yet known (to me).

Vertices Degree 3 Degree 4
14 1 0
15 0 0
16 1 0
17 0 0
18 5 0
19 0 0
20 32 0
21 0 0
22 385 0
23 0 0
24 7574 0
25 0 0
26 181227 1
27 0 0
28 4624501 1
29 0 0
30 122090544 4
31 0 0
32   19
33 0 0
34   1272

Back to table of contents .


Connected regular graphs with girth at least 7

The following table contains numbers of connected cubic graphs with given number of vertices and girth at least 7. Thomas Grüner found that there exist no 4-regular Graphs with girth 7 on less than 58 vertices. For less than 56 vertices this result could be veryfied with the independent program genreg.

Vertices Degree 3
22 0
24 1
26 3
28 21
30 546
32 30368

Back to table of contents .


Connected regular graphs with girth at least 8

The following table contains numbers of connected cubic graphs with given number of vertices and girth at least 8.

Vertices Degree 3
30 1
32 0
34 1
36 3
38 13
40 155

Back to table of contents .


Connected bipartite regular graphs

The following table contains numbers of connected bipartite regular graphs with given number of vertices and degree. For the empty fields the number is not yet known (to me).

Vertices Degree 3 Degree 4 Degree 5
6 1 0 0
8 1 1 0
10 2 1 1
12 5 4 1
14 13 14 4
16 38 129 41
18 149 1980 1981
20 703 62611 304495
22 4132 2806490  
24 29579    
26 245627    
28 2291589    
30 23466857    
32 259974248    

Back to table of contents .


Connected planar regular graphs

The following table contains numbers of connected planar regular graphs with given number of vertices and degree. For the empty fields the number is not yet known (to me). By Eulers formula there exist no such graphs with degree greater than 5. For the planarity test an algorithm was used which is included in the GTL. There is also a table with planar multigraphs available, which was computed with a graph generator by Thomas Grüner.

Vertices Degree 3 Degree 4 Degree 5
4 1 0 0
5 0 0 0
6 1 1 0
7 0 0 0
8 3 1 0
9 0 1 0
10 9 3 0
11 0 3 0
12 32 13 1
13 0 21 0
14 133 68 0
15 0 166 0
16 681 543 1
17 0 1605 0
18 3893 5413  
20 24809    
22 169206    
24 1214462    
26 9034509    

Back to table of contents .


Connected planar regular graphs with girth at least 4

The following table contains numbers of connected planar cubic graphs with given number of vertices and girth at least 4. By Eulers formula there exist no such regular graphs with degree greater than 3.

Vertices Degree 3
8 1
10 1
12 2
14 5
16 13
18 39
20 154
22 638
24 3047
26 15415

Back to table of contents .


Connected planar regular graphs with girth at least 5

The following table contains numbers of connected planar cubic graphs with given number of vertices and girth at least 5. By Eulers formula there exist no such regular graphs with degree greater than 3.

Vertices Degree 3
20 1
22 0
24 1
26 1
28 3

Back to table of contents .

Back to Markus Meringer's Homepage.
Markus Meringer, February 1997, updated June 2009