Cayley graphs of given degree and diameters 3, 4 and 5

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.