Bachratý, Martin; Šigiová, Jana and Širáň, Jozef
(2017).
|
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.
CORE (COnnecting REpositories)
CORE (COnnecting REpositories)