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.
When using GENREG for your publications, please cite
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 |
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 | ||||
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 |
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 |
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 |
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 |
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 |
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 |
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 |
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 |