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

Metrics

Item Actions

Export

You can export this page using these formats Digital Object Identifier - DOI

About

• Item ORO ID
• 62562
• Item Type
• Journal Item
• ISSN
• 1793-6713
• Keywords
• Degree-diameter problem; Cayley graph; Moore bound
• Academic Unit or School
• Faculty of Science, Technology, Engineering and Mathematics (STEM)
• SWORD Depositor
• Jisc Publications-Router
• Depositing User
• Jisc Publications-Router