The Open UniversitySkip to content

Large Cayley graphs of small diameter

Erskine, Grahame and Tuite, James (2018). Large Cayley graphs of small diameter. Discrete Applied Mathematics, 250 pp. 202–214.

Full text available as:
PDF (Accepted Manuscript) - Requires a PDF viewer such as GSview, Xpdf or Adobe Acrobat Reader
Download (338kB) | Preview
DOI (Digital Object Identifier) Link:
Google Scholar: Look up in Google Scholar


The degree-diameter problem seeks to find the largest possible number of vertices in a graph having given diameter and given maximum degree. Very often the problem is studied for restricted families of graph such as vertex-transitive or Cayley graphs, with the goal being to find a family of graphs with good asymptotic properties. In this paper we restrict attention to Cayley graphs, and study the asymptotics by fixing a small diameter and constructing families of graphs of large order for all values of the maximum degree. Much of the literature in this direction is focused on the diameter two case. In this paper we consider larger diameters, and use a variety of techniques to derive new best asymptotic constructions for diameters 3, 4 and 5 as well as an improvement to the general bound for all odd diameters. Our diameter 3 construction is, as far as we know, the first to employ matrix groups over finite fields in the degree-diameter problem.

Item Type: Journal Item
Copyright Holders: 2018 Elsevier
ISSN: 0166-218X
Keywords: Degree-diameter problem; Cayley graphs
Academic Unit/School: Faculty of Science, Technology, Engineering and Mathematics (STEM) > Mathematics and Statistics
Faculty of Science, Technology, Engineering and Mathematics (STEM)
Related URLs:
Item ID: 55855
Depositing User: Grahame Erskine
Date Deposited: 23 Jul 2018 13:27
Last Modified: 19 May 2019 04:11
Share this page:


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