# The Degree Diameter Problem for Cayley Graphs

From Combinatorics Wiki

## Introduction

The degree/diameter problem for Cayley graphs can be stated as follows:

Given natural numbers d and k, find the largest possible number Nc(d,k) of vertices in a Cayley graph of maximum degree d and diameter k.

There are no better upper bounds for Nc(d,k) than the very general Moore bounds M(d,k)=(d(d-1)k-2)(d-2)-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 Hoffman-Singleton graph are Cayley, and the possible Moore graph of degree 57 and diameter 2 is not even vertex-transitive.

Therefore, in attempting to settle the values of Nc(d,k), research activities in this problem follow the next two directions:

• Increasing the lower bounds for Nc(d,k) by constructing ever larger graphs.
• Lowering and/or setting upper bounds for Nc(d,k) by proving the non-existence of graphs whose order is close to the Moore bounds M(d,k).

Finding an upper bound for the general non-abelian case is still an open problem, while such an upper bound for the abelian case is already known.

## Increasing the lower bounds for Nc(d,k)

The current largest lower bounds (of order close to d2/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.

 $d$\$k$ 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érez-Rosés and G. Pineda-Villavicencio. * 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 Pineda-Villavicencio. More details are available in a paper by the authors. * Graph found by P. Potočnik, P. Spiga and G. Verret, Cubic vertex-transitive graphs on up to 1280 vertices. * Graphs found by Marcel Abas.

## Lowering and/or setting upper bounds for Nc(d,k)

In attempting to set the values for Nc(d,k), most research efforts have been directed at the abelian case.

The abelian case

When the group considered is abelian, a Moore-like 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 non-abelian case

As said above, to set a Moore-like bound for the non-abelian 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

$d$\$k$ 2 3 4 5 6 7 8 9 10
3
 8 100%
 14 100%
 24 100%
 60 100%
 72 100%
 168 100%
 300 100%
 1532 33.02%
 3068 28.75%
4
 13 100%
 30 100%
 84 100%
 484 42.35%
 1456 35.23%
 4372 26.41%
 13120 23.47%
 39364 19.17%
 118096 14.90%
5
 18 100%
 60 100%
 424 49.52%
 1704 32.04%
 6824 24.03%
 27304 20.14%
 109224 15.53%
 436904 13.23%
 1747624 10.70%
6
 32 100%
 108 100%
 936 40.06%
 4686 29.76%
 23436 21.82%
 117186 16.54%
 585936 13.04%
 2929686 10.50%
 14648436 8.55%
7
 36 100%
 168 100%
 1813 37.06%
 10885 25.31%
 65317 18.35%
 391909 13.46%
 2351461 10.61%
 14108773 8.66%
 84652645 7.09%
8
 48 100%
 456 55.48%
 3200 34.37%
 22408 22.58%
 156864 15.29%
 1098056 11.94%
 7686400 9.56%
 53804808 7.88%
 376633664 6.61%
9
 60 100%
 657 44.74%
 5265 29.43%
 42129 19.46%
 337041 13.53%
 2696337 10.37%
 21570705 7.81%
 172565649 7.02%
 1380525201 4.77%
10
 72 100%
 910 44.61%
 8200 27.87%
 73810 17.80%
 664300 12.22%
 5978710 9.75%
 53808400 7.97%
 484275610 5.78%
 4358480500 4.61%
11
 84 100%
 1221 39.80%
 12221 23.40%
 122221 15.95%
 1222221 11.40%
 12222221 8.19%
 122222221 6.08%
 1222222221 5.96%
 12222222221 4.09%
12
 96 100%
 1596 37.90%
 17568 21.48%
 193260 15.24%
 2125872 10.77%
 23384604 8.55%
 257230656 6.19%
 2829537228 5.58%
 31124909520 3.93%
13
 168 65.88%
 2041 33.31%
 24505 19.53%
 294073 13.69%
 3528889 9.83%
 42346681 7.84%
 508160185 5.88%
 6097922233 3.83%
 73175066809 2.90%
14
 195 65.64%
 2562 34.07%
 33320 19.53%
 433174 13.35%
 5631276 9.41%
 73206602 7.65%
 951685840 5.26%
 12371915934 4.68%
 160834907156 4.37%
15
 224 64.28%
 3165 30.71%
 44325 17.94%
 620565 12.33%
 8687925 9.05%
 121630965 7.07%
 1702833525 5.18%
 23839669365 4.21%
 333755371125 2.99%
16
 255 60.31%
 3856 29.95%
 57856 16.55%
 867856 11.59%
 13017856 8.64%
 195267856 6.40%
 2929017856 4.62%
 43935267856 4.54%
 659029017856 1.96%
17
 288 58.62%
 4641 27.14%
 74273 16.27%
 1188385 11.20%
 19014177 8.46%
 304226849 6.07%
 4867629601 4.54%
 77882073633 4.33%
 1246113178145 0%
18
 323 59.07%
 5526 27.32%
 93960 15.99%
 1597338 10.75%
 27154764 8.07%
 461631006 5.74%
 7847727120 4.11%
 133411361058 4.32%
 2267993138004 0%
19
 360 55.55%
 6517 25.13%
 117325 15.05%
 2111869 10.49%
 38013661 7.97%
 684245917 5.71%
 12316426525 4.06%
 221695677469 3.99%
 3990522194461 0%
20
 399 52.36%
 7620 25.69%
 144800 14.73%
 2751220 10.24%
 52273200 7.72%
 993190820 5.6%
 18870625600 4.04%
 358541886420 3.61%
 6812295842000 0%

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 semi-direct products of a product of finite fields and Z2, 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 Dm with cyclic groups Zn. 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 Zn×Zn with Z2 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 semi-direct products of cyclic groups.

$d$ 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%
$d$ 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 1-7
• 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 109-120, 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 225-233, 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 degree-diameter problem", Australasian Journal of Combinatorics 41: 63–80
• Loz, E.; Pineda-Villavicencio, 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, 123-132, PDF version
• Jana Šiagiová and Jozef Širáň, "A note on large Cayley graphs of diameter two and given degree", Discrete Mathematics, Volume 305, Issues 1-3, 6 December 2005, Pages 379-382
• Randall Dougherty and Vance Faber, "The Degree-Diameter Problem for Several Varieties of Cayley Graphs I: The Abelian Case", SIAM Journal on Discrete Mathematics, Volume 17 , Issue 3, 2004, 478-519, ISSN:0895-4801
• R. Stanton and D. Cowan, "Note on a “square” functional equation", SIAM Rev., 12 (1970), pp. 277–279.