Revisiting Constructions of Large Cayley Graphs of Given Degree and Diameter from Regular Orbits

Bachratý, Martin; Šigiová, Jana and Širáň, Jozef (2017). Revisiting Constructions of Large Cayley Graphs of Given Degree and Diameter from Regular Orbits. Journal of Interconnection Networks, 17(03n04) p. 1741011.

DOI: https://doi.org/10.1142/s0219265917410110

Abstract

The largest order C(d,k) of a Cayley graph of degree d≥3 and diameter k≥2 cannot exceed the Moore bound M(d,k) the asymptotic form of which is M(d,k)=dk−O(dk−1) for d→∞ and a fixed k. The second and the third author and the three authors proved by direct constructions that the Moore bound for diameter k=2 and k=3, respectively, can be approached asymptotically by Cayley graphs in the sense that C(d,k)/M(d,k)→1 for some sequences of degrees d→∞. In this note we present a unifying principle underlying the two results, based on the existence of certain regular orbits of automorphism groups of suitable graphs.