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.

Viewing alternatives

Download history

Metrics

Public Attention

Altmetrics from Altmetric

Number of Citations

Citations from Dimensions

Item Actions

Export

About

Recommendations