Abstract:
Let Cd,k be the largest number of vertices in a Cayley graph of degree d and diameter k. We
show that Cd,3 ≥ 3
16 (d − 3)3 and Cd,5 ≥ 25( d−7
4 )5 for any d ≥ 8, and Cd,4 ≥ 32( d−8
5 )4
for any d ≥ 10. For sufficiently large d our graphs are the largest known Cayley graphs of
degree d and diameters 3, 4 and 5.