Introduction
The degree/diameter problem for Cayley graphs can be stated as follows:
Given natural numbers d and k, find the largest possible number N^{c}(d,k) of vertices in a Cayley graph of maximum degree d and diameter k.
There are no better upper bounds for N^{c}(d,k) than the very general Moore bounds M(d,k)=(d(d1)^{k}2)(d2)^{1}. As an interesting fact, no Moore graph (graph whose order attains the Moore bound) is a Cayley graph. Indeed, neither the Petersen graph nor the HoffmanSingleton graph are Cayley, and the possible Moore graph of degree 57 and diameter 2 is not even vertextransitive.
Therefore, in attempting to settle the values of N^{c}(d,k), research activities in this problem follow the next two directions:
 Increasing the lower bounds for N^{c}(d,k) by constructing ever larger graphs.
 Lowering and/or setting upper bounds for N^{c}(d,k) by proving the nonexistence of graphs whose order is close to the Moore bounds M(d,k).
Finding an upper bound for the general nonabelian case is still an open problem, while such an upper bound for the abelian case is already known.
Increasing the lower bounds for N^{c}(d,k)
The current largest lower bounds (of order close to d^{2}/2) for Cayley graphs of diameter k=2 and an infinite set of values for the degree d>20, is given by Šiagiová and Širáň. Some lower bounds for trivalent graphs of diameter d>10 are given by Curtin.
Table of the orders of the largest known Cayley graphs for the undirected degree diameter problem
Below is the table of the largest known Cayley graphs (as of September 2009) in the undirected degree diameter problem for Cayley graphs of degree at most 3 ≤ d ≤ 20 and diameter 2 ≤ k ≤ 10. This table represents the best lower bounds known at present on the order of Cayley (d,k)graphs. All optimal graphs are marked in bold. All Cayley graphs of order up to 33 are isomorphic to graphs in the lists available here, and some of the trivalent Cayley graphs of order up to 1000 are available here, but no information was given in these lists regarding diameter.
[math]d[/math]\[math]k[/math] 
2 
3 
4 
5 
6 
7 
8 
9 
10

3 
8 
14 
24 
60 
72 
168 
300 
506 
882

4 
13 
30 
84 
216 
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 
112 
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 
200 
1 155 
9 576 
100 650 
1 125 264 
12 500 082 
135 340 551 
1 995 790 371 
12 951 451 931

17 
200 
1 260 
12 090 
133 144 
1 609 830 
18 495 162 
220 990 700 
3 372 648 954 

18 
200 
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 
210 
1 958 
21 333 
281 820 
4 040 218 
55 625 185 
762 374 779 
12 951 451 931 

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

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

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

* 
Graph found by Wohlmuth, and shown to be optimal by Marston Conder.

* 
Graphs found by Michael Sampels.

* 
Graphs found (and verified as optimal in most cases) by Marston Conder. See Graphs found by Marston Conder for more details.

* 
Optimal graph found by Marston Conder. This graph was also found independently by Eyal Loz.

* 
Graph found by Eugene Curtin, and shown to be optimal by Marston Conder. This graph was also found independently by Eyal Loz.

* 
Graphs found by Eyal Loz as part of the joint project The degree/diameter problem for several classes of graphs by E. Loz, H. PérezRosés and G. PinedaVillavicencio.

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

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

* 
Graph found by P. Potočnik, P. Spiga and G. Verret, Cubic vertextransitive graphs on up to 1280 vertices.

* 
Graphs found by Marcel Abas.

Lowering and/or setting upper bounds for N^{c}(d,k)
In attempting to set the values for N^{c}(d,k), most research efforts have been directed at the abelian case.
The abelian case
When the group considered is abelian, a Moorelike bound was given by Stanton and Cowan, and is asymptotically equivalent to (2k)^{d/2}(d/2)!^{1}, where (d/2) is the number of generators from the group. Dougherty and Faber gave a list of optimal graphs for both the directed and undirected abelian Cayley case.
The nonabelian case
As said above, to set a Moorelike bound for the nonabelian case remains an open problem.
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

* 
Graphs shown to be optimal by Marston Conder.

* 
Graphs shown to be optimal by P. Potočnik, P. Spiga and G. Verret.

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

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.
Marcel Abas has found a general construction for Cayley graphs of any degree with order half of the Moore bound using direct product of dihedral groups D_{m} with cyclic groups Z_{n}. It has been shown that, in asymptotic sense, the most of record Cayley graphs of diameter two is obtained by Abas construction. Using semidirect product of Z_{n}×Z_{n} with Z_{2} he has found (for degrees 13 ≤ d ≤ 57) largest known Cayley graphs in 34 cases of total 45 degrees and he constructed Cayley graphs of diameter two and of order of 0.684 of the Moore bound for every degree d ≥ 360 756.
A range of Cayley graphs of diameter 2 and degree larger than 12 was found by Eyal Loz using semidirect products of cyclic groups.
[math]d[/math] 
Order 
% Moore Bound

4 
13 
76.47%

5 
18 
69.23%

6 
32 
86.48%

7 
36 
72%

8 
48 
73.84%

9 
60 
73.17%

10 
72 
71.28%

11 
84 
68.85%

12 
96 
66.20%

13 
112 
65.88%

14 
128 
64.97%

15 
144 
63.71%

16 
200 
77.82%

17 
200 
68.96%

18 
200 
61.53%

19 
200 
55.24%

20 
210 
52.36%

21 
288 
65.15%

22 
288 
59.38%

23 
392 
73.96%

24 
392 
67.93%

25 
392 
62.61%

26 
392 
57.90%

27 
392 
53.69%

28 
512 
65.22%

29 
512 
60.80%

30 
512 
56.82%


[math]d[/math] 
Order 
% Moore Bound

31 
648 
67.35%

32 
648 
63.21%

33 
648 
59.44%

34 
648 
56.00%

35 
648 
52.85%

36 
648 
49.96%

37 
800 
58.39%

38 
800 
55.36%

39 
800 
52.56%

40 
968 
60.46%

41 
968 
57.55%

42 
968 
54.84%

43 
968 
52.32%

44 
968 
49.97%

45 
1058 
52.22%

46 
1152 
54.41%

47 
1152 
52.12%

48 
1152 
49.97%

49 
1352 
56.28%

50 
1352 
54.05%

51 
1352 
51.96%

52 
1352 
49.98%

53 
1458 
51.88%

54 
1568 
53.75%

55 
1568 
51.81%

56 
1568 
49.98%

57 
1682 
51.75%


Color 
Details

* 
Optimal Cayley Graphs found by Marston Conder.

* 
Cayley Graphs found by Eyal Loz.

* 
Cayley Graphs found by Jana Šiagiová and Jozef Širáň.

* 
Cayley Graphs found by Marcel Abas.

* 
Cayley Graphs found by Marcel Abas.

References
 Marcel Abas, "Cayley graphs of diameter two and any degree with order half of the Moore bound", Discrete Applied Mathematics, Volume 173, 20 August 2014, Pages 17
 Marcel Abas, "Cayley graphs of diameter two with order greater than 0.684 of the Moore bound for any degree", European Journal of Combinatorics, Volume 57, (2016), Pages 109120, PDF version
 Marcel Abas, "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
 J. Dinneen, Michael; Hafner, Paul R. (1994), "New Results for the Degree/Diameter Problem", Networks 24 (7): 359–367, PDF version
 Miller, Mirka; Širáň, Jozef (2005), "Moore graphs and beyond: A survey of the degree/diameter problem", Electronic Journal of Combinatorics Dynamic survey D, PDF version
 Loz, Eyal; Širáň, Jozef (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.
 Eugene Curtin, Cubic Cayley graphs with small diameter Discrete Mathematics and Theoretical Computer Science 4, 2001, 123132, PDF version
 Jana Šiagiová and Jozef Širáň, "A note on large Cayley graphs of diameter two and given degree", Discrete Mathematics, Volume 305, Issues 13, 6 December 2005, Pages 379382
 Randall Dougherty and Vance Faber, "The DegreeDiameter Problem for Several Varieties of Cayley Graphs I: The Abelian Case", SIAM Journal on Discrete Mathematics, Volume 17 , Issue 3, 2004, 478519, ISSN:08954801
 R. Stanton and D. Cowan, "Note on a “square” functional equation", SIAM Rev., 12 (1970), pp. 277–279.
External links