The Open UniversitySkip to content
 

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.

Full text available as:
[img]
Preview
PDF (Accepted Manuscript) - Requires a PDF viewer such as GSview, Xpdf or Adobe Acrobat Reader
Download (235kB) | Preview
DOI (Digital Object Identifier) Link: https://doi.org/10.1142/s0219265917410110
Google Scholar: Look up in Google Scholar

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.

Item Type: Journal Item
ISSN: 1793-6713
Keywords: Degree-diameter problem; Cayley graph; Moore bound
Academic Unit/School: Faculty of Science, Technology, Engineering and Mathematics (STEM) > Mathematics and Statistics
Faculty of Science, Technology, Engineering and Mathematics (STEM)
Item ID: 62562
SWORD Depositor: Jisc Publications-Router
Depositing User: Jisc Publications-Router
Date Deposited: 24 Jul 2019 11:55
Last Modified: 04 Jul 2020 14:24
URI: http://oro.open.ac.uk/id/eprint/62562
Share this page:

Metrics

Altmetrics from Altmetric

Citations from Dimensions

Download history for this item

These details should be considered as only a guide to the number of downloads performed manually. Algorithmic methods have been applied in an attempt to remove automated downloads from the displayed statistics but no guarantee can be made as to the accuracy of the figures.

Actions (login may be required)

Policies | Disclaimer

© The Open University   contact the OU