The Degree/Diameter Problem
From eyal
Contents
Introduction
A full description of the degree diameter problem is available from Combinatorics Wiki. Below is a short summary, and tables presenting the graphs I found as part of the PhD work I have done during 20062008. Adjacency lists to some of the graphs that I found, of order less than 20,000 are also available.
Undirected graphs
The degree diameter problem is the problem of finding the largest possible number N(d,k) of vertices in a graph of maximum degree d and diameter k.
We call a graph of maximum degree d and diameter k a (d,k)graph.
An upper bound on the order of a (d,k)graph is given by the expression (d(d1)^{k}2)(d2)^{1}, known as the Moore bound, and denoted by M(d,k).
Graphs whose order attains the Moore bound are called Moore graphs. Moore graphs are very rare. They are the complete graphs on d+1 vertices, the cycles on 2k+1 vertices, and for diameter 2, the Petersen graph, the HoffmanSingleton graph and probably a graph of degree d = 57. For 2 < k and 2 < d, there are no Moore graphs.
Consequently, research activities in the degree/diameter problem cover (i) Constructions of ever larger graphs, which provide better lower bounds on N(d,k) and (ii) Proofs of the nonexistence or otherwise of graphs whose order misses the Moore bound by a small number of vertices. A comprehensive information source, covering the current state of knowledge in the degree/diameter problem for general graphs can be found here.
Directed graphs
In the context of digraphs the degree/diameter problem can be considered as the problem of finding the largest possible number DN(d,k) of vertices in a digraph of maximum outdegree d and diameter k.
We call a digraph of maximum outdegree d and diameter k a (d,k)digraph.
An upper bound on the order of a (d,k)digraph is given by the expression (d^{k+1}1)(d2)^{1}, known as the directed Moore bound, and denoted by DM(d,k).
Digraphs attaining the directed Moore bound are called Moore digraphs, and they are even rarer than the Moore graphs. Moore digraphs are the directed cycles on k+1 vertices and the complete digraphs on d+1 vertices. For 1 < k and 1 < d, there are no Moore digraphs. A comprehensive information source, covering the current state of knowledge in the degree/diameter problem for general digraphs can be found here.
The degree/diameter problem for several classes of graphs:
The following set of tables list all the graphs I found as part of my ongoing interest in the degree diameter problem. I am also currently working with Hebert PérezRosés, Guillermo Pineda Villavicencio and Jozef Širáň, on different aspects of the degree diameter problem.
If, in addition to the limits on the degree and the diameter, we add further constraints to the graphs in question, we can state the degree/diameter problem for several classes of graphs, such as bipartite graphs, vertextransitive graphs, Cayley graphs, arctransitive graphs, and the corresponding versions for digraphs. In these cases we denote the largest possible number of nodes by N^{b}(d,k) (for bipartite graphs), N^{vt}(d,k) (for vertextransitive graphs), N^{c}(d,k) (for Cayley graphs), and N^{at}(d,k) (for arctransitive graphs), respectively.
For only a few classes of graphs, better general upper bounds are known.
The undirected case:
General graphs:
For complete information on the general undirected case please refer to the degree/diameter problem for general graphs. Below is the table of the largest known graphs (as of January 2009) that I found (with orange background). Graphs that were found by other authors are displayed without colour. Graphs in bold are known to be optimal.
d\k  2  3  4  5  6  7  8  9  10 
3  10  20  38  70  132  196  336  600  1 250 
4  15  41  96  364  740  1 320  3 243  7 575  17 703 
5  24  72  210  624  2 772  5 516  17 030  57 840  187 056 
6  32  110  390  1 404  7 917  19 383  76 461  307 845  1 253 615 
7  50  168  672  2 756  11 988  52 768  249 660  1 223 050  6 007 230 
8  57  253  1 100  5 060  39 672  131 137  734 820  4 243 100  24 897 161 
9  74  585  1 550  8 200  75 893  279 616  1 686 600  12 123 288  65 866 350 
10  91  650  2 286  13 140  134 690  583 083  4 293 452  27 997 191  201 038 922 
11  104  715  3 200  19 500  156 864  1 001 268  7 442 328  72 933 102  600 380 000 
12  133  786  4 680  29 470  359 772  1 999 500  15 924 326  158 158 875  1 506 252 500 
13  162  851  6 560  40 260  531 440  3 322 080  29 927 790  249 155 760  3 077 200 700 
14  183  916  8 200  57 837  816 294  6 200 460  55 913 932  600 123 780  7 041 746 081 
15  186  1 215  11 712  76 518  1 417 248  8 599 986  90 001 236  1 171 998 164  10 012 349 898 
16  198  1 600  14 640  132 496  1 771 560  14 882 658  140 559 416  2 025 125 476  12 951 451 931 
Cayley graphs
For complete information on degree diameter Cayley graphs please refer to the degree/diameter problem for Cayley graphs. Below is the table of the largest known graphs (as of January 2009) that I found (with orange background). Graphs that were found by other authors are displayed without colour. Graphs in bold are known to be optimal. Note that the graphs with lighter orange background also appear in the table above.
d\k  2  3  4  5  6  7  8  9  10 
3  8  14  24  60  72  168  300  506  820 
4  13  30  84  205  513  1 155  3 080  7 550  17 604 
5  18  60  210  546  1 640  5 500  16 965  57 840  187 056 
6  32  108  375  1 395  5 115  19 383  76 461  307 845  1 253 615 
7  36  168  672  2 756  11 988  52 768  249 660  1 223 050  6 007 230 
8  48  253  1 100  5 060  23 991  131 137  734 820  4 243 100  24 897 161 
9  60  294  1 550  8 200  45 612  279 616  1 686 600  12 123 288  65 866 350 
10  72  406  2 286  13 140  81 235  583 083  4 293 452  27 997 191  201 038 922 
11  84  486  2 860  19 500  139 446  1 001 268  7 442 328  72 933 102  500 605 110 
12  96  605  3 775  29 470  229 087  1 999 500  15 924 326  158 158 875  1 225 374 192 
13  108  680  4 788  40 260  347 126  3 322 080  29 927 790  233 660 788  2 129 329 324 
14  128  873  6 510  57 837  530 448  5 600 532  50 128 239  579 328 377  7 041 746 081 
15  144  972  7 956  76 518  787 116  8 599 986  88 256 520  1 005 263 436  10 012 349 898 
16  150  1 155  9 576  100 650  1 125 264  12 500 082  135 340 551  1 995 790 371  12 951 451 931 
17  162  1 260  12 090  133 144  1 609 830  18 495 162  220 990 700  3 372 648 954  
18  171  1 510  15 026  171 828  2 193 321  26 515 120  323 037 476  5 768 971 167  
19  200  1 638  17 658  221 676  3 030 544  39 123 116  501 001 000  8 855 580 344  
20  203  1 958  21 333  281 820  4 040 218  55 625 185  762 374 779  12 951 451 931 
Cayley Graphs of Diameter Two
For the special case of diameter 2, Cayley graphs of degree up to 12 are known to be optimal. It is interesting to note that optimal Cayley graphs are smaller than the Moore bound (as shown in the table below).
Jana Šiagiová and Jozef Širáň have found a general construction for Cayley graphs. SS graphs are constructed using semidirect products of a product of finite fields and Z_{2}, where each such group yields a range of graphs of different degrees. SS graphs are the largest known Cayley graphs for degree larger than 30 and diameter 2, with order up to about 50% of the Moore bound.
A range of Cayley graphs of diameter 2 and degree larger than 12 was found by Eyal Loz using semidirect products of cyclic groups.


Color  Details 
*  Optimal Cayley Graphs found by Marston Conder. 
*  Cayley Graphs found by Eyal Loz. 
*  Cayley Graphs found by Jana Šiagiová and Jozef Širáň. 
Bipartite graphs
For complete information on the bipartite case please refer to the degree/diameter problem for bipartite graphs. Below is the table of the largest known graphs (as of January 2009) that I found (with orange background). Graphs that were found by other authors are displayed without colour. Graphs in bold are known to be optimal. Note that some of the graphs in this table also appear in the table above.
d\k  3  4  5  6  7  8  9  10 
3  14  30  56  126  168  256  506  800 
4  26  80  160  728  840  2 184  4 970  11 748 
5  42  170  336  2 730  3 110  9 234  27 936  90 068 
6  62  312  684  7 812  8 310  29 790  117 360  452 032 
7  80  346  1 134  8 992  23 436  80 940  400 160  1 987 380 
8  114  800  1 710  39 216  40 586  201 480  1 091 232  6 927 210 
9  146  1 170  2 496  74 898  117 648  449 480  2 961 536  20 017 260 
10  182  1 640  4 000  132 860  224 694  1 176 480  7 057 400  50 331 156 
11  186  1 734  5 850  142 464  398 580  2 246 940  15 200 448  130 592 354 
12  266  2 928  8 200  354 312  664 300  4 650 100  30 001 152  300 383 050 
13  270  3 064  11 480  374 452  1 062 936  5 314 680  50 990 610  617 330 936 
14  366  4 760  14 760  804 468  1 771 560  14 172 480  95 087 738  1 213 477 190 
15  370  4 946  20 496  842 048  2 480 184  XXX  168 016 334  2 300 326 510 
16  394  5 134  27 300  884 062  4 022 340  36 201 060  288 939 118  4 119 507 330 
The directed case:
For complete information on the general directed case please refer to the degree/diameter problem for general digraphs.
Vertex symmetric digraphs
For complete information on the general directed case please refer to the degree/diameter problem for vertex symmetric digraphs. Below is the table of the largest known vertex symmetric digraphs (as of January 2009) that I found (with orange background). Digraphs that were found by other authors are displayed without colour. Graphs in bold are known to be optimal. For some values of d and k the complete list of distinct Cayley digraphs is linked from the table.
d\k  2  3  4  5  6  7  8  9  10  11 
2  6  10  20  27  72  144  171  336  504  737 
3  12  27  60  165  333  1 152  2 041  5 115  11 568  41 472 
4  20  60  168  465  1 378  7 200  14 400  42 309  137 370  648 000 
5  30  120  360  1 152  3 775  28 800  86 400  259 200  1 010 658  5 184 000 
6  42  210  840  2 520  9 020  88 200  352 800  1 411 200  5 184 000  27 783 000 
7  56  336  1 680  6 720  20 160  225 792  1 128 960  5 644 800  27 783 000  113 799 168 
8  72  504  3 024  15 120  60 480  508 032  3 048 192  18 289 152  113 799 168  457 228 800 
9  90  720  5 040  30 240  151 200  1 036 800  7 257 600  50 803 200  384 072 192  1 828 915 200 
10  110  990  7 920  55 400  332 640  1 960 200  15 681 600  125 452 800  1 119 744 000  6 138 320 000 
11  132  1 320  11 880  95 040  665 280  3 991 680  31 152 000  282 268 800  2 910 897 000  18 065 203 200 
12  156  1 716  17 160  154 440  1 235 520  8 648 640  58 893 120  588 931 200  6 899 904 000  47 703 427 200 
13  182  2 184  24 024  240 240  2 162 160  17 297 280  121 080 960  1 154 305 152  15 159 089 098  115 430 515 200 
References
 Bannai, E.; Ito, T. (1973), "On finite Moore graphs", J. Fac. Sci. Univ. Tokyo Ser. A 20: 191–208, MR0323615
 Bridges, W. G.; Toueg, S. (1980), "On the impossibility of directed Moore graphs", Journal of Combinatorial Theory, Series B 29 (3), 339341, doi:10.1016/00958956(80)90091X.
 J. Dinneen, Michael; Hafner, P. R. (1994), "New Results for the Degree/Diameter Problem", Networks 24 (7): 359–367, PDF version.
 Loz, E.; Širáň, J. (2008), "New record graphs in the degreediameter problem", Australasian Journal of Combinatorics 41: 63–80.
 Hoffman, Alan J.; Singleton, Robert R. (1960), "Moore graphs with diameter 2 and 3", IBM Journal of Research and Development 5 (4): 497–504, MR0140437, PDF version
 Singleton, Robert R. (1968), "There is no irregular Moore graph", American Mathematical Monthly 75 (1): 42–43, MR0225679
 Miller, Mirka; Širáň, Jozef (2005), "Moore graphs and beyond: A survey of the degree/diameter problem", Electronic Journal of Combinatorics Dynamic survey DS14 PDF version.
External links
 Degree diameter problem on CombinatoricsWiki
 Geoffrey Exoo's DegreeDiameter record graphs page.
 Degree Diameter online table.
 Vertexsymmetric digraphs online table.
 Degree diameter problem on Wikipedia.