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

- Connected regular graphs
- Connected regular graphs with girth at least 4
- Connected regular graphs with girth at least 5
- Connected regular graphs with girth at least 6
- Connected regular graphs with girth at least 7
- Connected regular graphs with girth at least 8
- Connected bipartite regular graphs
- Connected planar 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 .

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 .

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 .

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 .

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 .

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 .

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 .

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 .

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 .

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