# 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. The source code and excutables are available at SourceForge. The original source package genreg.tar can be downloaded from ResearchGate and 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.

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

## 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

## 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

## 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 31478584 132160608 0
27 0   0
28 656783890   0
30     4
32     90

## 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

## 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

## 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

## 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

## 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

## 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

## 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