Table of the largest known graphs of a given diameter and maximal degree

In graph theory, the degree diameter problem is the problem of finding the largest possible graph for a given maximum degree and diameter. The Moore bound sets limits on this, but for many years mathematicians in the field have been interested in a more precise answer. The table below gives current progress on this problem (excluding the case of degree 2, where the largest graphs are cycles with an odd number of vertices).

Table of the orders of the largest known graphs for the undirected degree diameter problem

Below is the table of the vertex numbers for the best-known graphs (as of October 2008) in the undirected degree diameter problem for graphs of degree at most 3 ≤ d ≤ 16 and diameter 2 ≤ k ≤ 10. Only a few of the graphs in this table (marked in bold) are known to be optimal (that is, largest possible). The remainder are merely the largest so far discovered, and thus finding a larger graph that is closer in order (in terms of the size of the vertex set) to the Moore bound is considered an open problem. Some general constructions are known for values of d and k outside the range shown in the table.

k
d
 2 3 4 5 6 7 8 9 10
3 10 20 38 70 132 196 336 600 1250
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 1404 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

The following table is the key to the colors in the table presented above:

Color Details
* The Petersen and Hoffman–Singleton graphs.
* Optimal graphs which are not Moore graphs.
* Graph found by James Allwright.
* Graph found by G. Wegner.
* Graphs found by Geoffrey Exoo.
* Family of graphs found by Brendan D. McKay, Mirka Miller and Jozef Širáň. More details are available in a paper by the authors.
* Graphs found by J. Gómez.
* Graph found by Mitjana M. and Francesc Comellas. This graph was also found independently by Michael Sampels.
* Graph found by Fiol, M.A. and Yebra, J.L.A.
* Graph found by Francesc Comellas and J. Gómez.
* Graphs found by G. Pineda-Villavicencio, J. Gómez, Mirka Miller and H. Pérez-Rosés. More details are available in a paper by the authors.
* Graphs found by Eyal Loz. More details are available in a paper by Eyal Loz and Jozef Širáň.
* Graphs found by Michael Sampels.
* Graphs found by Michael J. Dinneen and Paul Hafner. More details are available in a paper by the authors.
* Graph found by Marston Conder.

References

This article is issued from Wikipedia - version of the 5/28/2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.