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

摘要

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) = d~k - O(d~(k-1)) for d → ∞ and a fixed k. The second and the third author~(20) and the three authors~1 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.