Introduction
The degree/diameter problem for general graphs can be stated as follows:
Given natural numbers d and k, find the largest possible number N(d,k) of vertices in a graph of maximum degree d and diameter k.
In attempting to settle the values of N(d,k), research activities in this problem have follow the following two directions:
 Increasing the lower bounds for N(d,k) by constructing ever larger graphs.
 Lowering and/or setting upper bounds for N(d,k) by proving the nonexistence of graphs
whose order is close to the Moore bounds M(d,k)=(d(d1)^{k}2)(d2)^{1}.
Increasing the lower bounds for N(d,k)
In the quest for the largest known graphs many innovative approaches have been suggested. In a wide spectrum, we can classify these approaches into general (those producing graphs for many combinations of the degree and the diameter) and ad hoc (those devised specifically for producing graphs for few combinations of the degree and the diameter). Among the former, we have the constructions of De Bruijn graphs and Kautz graphs, while among the latter, we have the star product, the voltage assigment technique and graph compunding. For information on the stateof theart of this research stream, the interested reader is referred to the survey by Miller and Širáň.
Below is the table of the largest known graphs (as of September 2009) in the undirected degree diameter problem for graphs of degree at most 3 ≤ d ≤ 20 and diameter 2 ≤ k ≤ 10. Only a few of the graphs in this table are known to be optimal (marked in bold), 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.
Table of the orders of the largest known graphs for the undirected degree diameter problem
[math]d[/math]\[math]k[/math] 
2 
3 
4 
5 
6 
7 
8 
9 
10

3 
10 
20 
38 
70 
132 
196 
360 
600 
1 250

4 
15 
41 
98 
364 
740 
1 320 
3 243 
7 575 
17 703

5 
24 
72 
212 
624 
2 772 
5 516 
17 030 
57 840 
187 056

6 
32 
111 
390 
1 404 
7 917 
19 383 
76 461 
331 387 
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 268 
75 893 
279 616 
1 697 688 
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 
856 
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 
187 
1 215 
11 712 
76 518 
1 417 248 
8 599 986 
90 001 236 
1 171 998 164 
10 012 349 898

16 
200 
1 600 
14 640 
132 496 
1 771 560 
14 882 658 
140 559 416 
2 025 125 476 
12 951 451 931

17 
274 
1 610 
19 040 
133 144 
3 217 872 
18 495 162 
220 990 700 
3 372 648 954 
15 317 070 720

18 
307 
1 620 
23 800 
171 828 
4 022 340 
26 515 120 
323 037 476 
5 768 971 167 
16 659 077 632

19 
338 
1 638 
23 970 
221 676 
4 024 707 
39 123 116 
501 001 000 
8 855 580 344 
18 155 097 232

20 
381 
1 958 
34 952 
281 820 
8 947 848 
55 625 185 
762 374 779 
12 951 451 931 
78 186 295 824

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

* 
The Petersen and Hoffman–Singleton graphs.

* 
Other non Moore but optimal graphs.

* 
Graph found by J. Allwright.

* 
Graph found by G. Wegner.

* 
Graphs found by G. Exoo.

* 
Graphs found by V. Pelekhaty. The adjacency list can be found here File:Pelekhaty856133.pdf.

* 
Family of graphs found by B. D. McKay, M. Miller and J. Širáň. More details are available in a paper by the authors.

* 
Graphs found by J. Gómez.

* 
Graph found by M. Mitjana and F. Comellas. This graph was also found independently by M. Sampels.

* 
Graphs found by C. Delorme.

* 
Graphs found by C. Delorme and G. Farhi.

* 
Graphs found by E. Canale. (2012)

* 
Graph found by J. C. Bermond, C. Delorme, and G. Farhi

* 
Graphs found by J. Gómez and M. A. Fiol.

* 
Graphs found by J. Gómez, M. A. Fiol, and O. Serra.

* 
Graph found by M.A. Fiol and J.L.A. Yebra.

* 
Graph found by F. Comellas and J. Gómez.

* 
Graph found by Jianxiang Chen.

* 
Graphs found by G. PinedaVillavicencio, J. Gómez, M. Miller and H. PérezRosés. More details are available in a paper by the authors.

* 
Graphs found by E. Loz. More details are available in a paper by E. Loz and J. Širáň.

* 
Graphs found by E. Loz and G. PinedaVillavicencio. More details are available in a paper by the authors.

* 
Graphs found by A. Rodriguez. (2012)

* 
Graphs found by M. Sampels.

* 
Graphs found by M. J. Dinneen and P. Hafner. More details are available in a paper by the authors.

* 
Graph found by M. Conder.

* 
Graphs found by Brown, W. G. (1966).

* 
Graph found by M. Abas. (2017). More details are available in a paper by the author.

Lowering and/or setting upper bounds for N(d,k)
As the Moore bound cannot be reached in general, some theoretical work has been done to determine the lowest possible upper bounds. In this direction reserachers have been interested in graphs of maximum degree d, diameter k and order M(d,k)δ for small δ. The parameter δ is called the defect. Such graphs are called (d,k,δ)graphs.
For δ=1 the only (d,k,1)graphs are the cycles on 2k vertices. Erdös, Fajtlowitcz and Hoffman, who proved the nonexistence of (d,2,1)graphs for d≠3. Then, Bannai and Ito, and also
independently, Kurosawa and Tsujii, proved the nonexistence of (d,k,1)graphs for d≥3 and k≥3.
For δ=2, the (2,k,2)graphs are the cycles on 2k1. Considering d≥3, only five graphs are known at present. Elspas found the unique (4,2,2)graph and the unique (5,2,2)graph, and credited Green with producing the unique (3,3,2)graph. The other graphs are two nonisomorphic (3,2,2)graphs.
When δ=2, d≥3 and k≥3, not much is known about the existence or otherwise of (d,k,2)graphs. In this context some known outcomes include the nonexistence of (3,k,2)graphs with k≥4 by Leif Jorgensen, the nonexistence of (4,k,2)graphs with k≥3 by Mirka Miller and Rino Simanjuntak, some structural properties of (5,k,2)graphs with k≥3 by Guillermo PinedaVillavicencio and Mirka Miller, the obtaining of several necessary conditions for the existence of (d,2,2)graphs with d≥3 by Mirka Miller, Minh Nguyen and Guillermo PinedaVillavicencio, and the nonexistence of (d,2,2)graphs for 5<d<50 by Jose Conde and Joan Gimbert.
For the case of δ≥3 only a few works are known at present: the nonexistence of (3,4,4)graphs by Leif Jorgensen; the complete catalogue of (3,k,4)graphs with k≥2 by Guillermo PinedaVillavicencio and Mirka Miller by proving the nonexistence of (3,k,4)graphs with k≥5, the settlement of N(3,4)=M(3,4)=38 by Buset; and the obtaining of N(6,2)=M(6,2)5=32 by Molodtsov. For more information, check the corresponding papers, and the survey by Miller and Širáň.
Table of the lowest upper bounds known at present, and the percentage of the order of the largest known graphs
[math]d[/math]\[math]k[/math] 
2 
3 
4 
5 
6 
7 
8 
9 
10

3










4










5










6










7










8










9










10










11










12










13










14










15










16










17










18










19










20










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

* 
The Moore bound.

* 
Upper bound introduced by A. Hoffman, R. Singleton, Bannai, E. and Ito, T.

* 
Upper bound introduced by Leif Jorgensen.

* 
Optimal graphs found by Buset and by Molodtsov.

* 
Graphs shown optimal.

References
 Abas M., "Large Networks of Diameter Two Based on Cayley Graphs" in "Cybernetics and Mathematics Applications in Intelligent Systems, Advances in Intelligent Systems and Computing 574", (2017), Pages 225233, PDF version
 Bannai, E.; Ito, T. (1981), "Regular graphs with excess one", Discrete Mathematics 37:147158, doi:10.1016/0012365X(81)902156.
 Buset, D. (2000), "Maximal cubic graphs with diameter 4", Discrete Applied Mathematics 101 (13): 5361, doi:10.1016/S0166218X(99)002048.
 J. Dinneen, Michael; Hafner, P. R. (1994), "New Results for the Degree/Diameter Problem", Networks 24 (7): 359–367, PDF version.
 Elspas, B. (1964), "Topological constraints on interconnectionlimited logic", Proceedings of IEEE Fifth Symposium on Switching Circuit Theory and Logical Design S164: 133147.
 Erdös P; Fajtlowicz, S.; Hoffman A. J. (1980), "Maximum degree in graphs of diameter 2", Networks 10: 8790.
 Hoffman, A. J.; Singleton, R. R. (1960), "Moore graphs with diameter 2 and 3", IBM Journal of Research and Development 5 (4): 497–504, MR0140437, PDF version.
 L. K. Jorgensen (1992), "Diameters of cubic graphs", Discrete Applied Mathematics 37/38: 347351, doi:10.1016/0166218X(92)90144Y.
 L. K. Jorgensen (1993), "Nonexistence of certain cubic graphs with small diameters", Discrete Mathematics 114:265273, doi:10.1016/0012365X(93)90371Y.
 Kurosawa, K.; Tsujii, S. (1981), "Considerations on diameter of communication networks", Electronics and Communications in Japan 64A (4): 3745.
 Loz, E.; Širáň, J. (2008), "New record graphs in the degreediameter problem", Australasian Journal of Combinatorics 41: 63–80.
 Loz, E.; PinedaVillavicencio, G. (2010), "New benchmarks for large scale networks with given maximum degree and diameter", The Computer Journal, The British Computer Society, Oxford University Press.
 McKay, B. D.; Miller, M.; Širáň, J. (1998), "A note on large graphs of diameter two and given maximum degree", Journal of Combinatorial Theory Series B 74 (4): 110–118.
 Miller, M; Nguyen, M.; PinedaVillavicencio, G. (accepted in September 2008), "On the nonexistence of graphs of diameter 2 and defect 2", Journal of Combinatorial Mathematics and Combinatorial Computing.
 Miller, M.; Simanjuntak, R. (2008), "Graphs of order two less than the Moore bound", Discrete Mathematics 308 (13): 28102821, doi:10.1016/j.disc.2006.06.045.
 Miller, M.; Širáň, J. (2005), "Moore graphs and beyond: A survey of the degree/diameter problem", Electronic Journal of Combinatorics Dynamic survey D, PDF version.
 Molodtsov, S. G. (2006), "Largest Graphs of Diameter 2 and Maximum Degree 6", Lecture Notes in Computer Science 4123: 853857.
 PinedaVillavicencio, G.; Miller, M. (2008), "On graphs of maximum degree 3 and defect 4", Journal of Combinatorial Mathematics and Combinatorial Computing 65: 2531.
 PinedaVillavicencio, G.; Miller, M., "Complete characterization of graphs of maximum degree 3 and defect at most 4", submitted.
 PinedaVillavicencio, G.; Gómez, J.; Miller, M.; PérezRosés, H., "New Largest Known Graphs of Diameter 6", Networks, to appear, doi:10.1002/net.20269. See also Electronic Notes in Discrete Mathematics 24: 153–160, 2006.
 PinedaVillavicencio, G.; Miller, M. (Oct 2006), "On Graphs of Maximum Degree 5, Diameter D and Defect 2", Proceedings of MEMICS 2006, Second Doctoral Workshop on Mathematical and Engineering Methods in Computer Science: 182189, Mikulov, Czech Republic.
 Brown, W. G. (1966) On graphs that do not contain a Thomsen graph. Canadian Mathematical Bulletin, 9, 281  285.
External links