The Open UniversitySkip to content
 

Asymptotically approaching the Moore bound for diameter three by Cayley graphs

Bachratý, Martin; Šiagiová, Jana and Širáň, Jozef (2019). Asymptotically approaching the Moore bound for diameter three by Cayley graphs. Journal of Combinatorial Theory, Series B, 134 pp. 203–217.

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

Abstract

The largest order n(d,k) of a graph of maximum degree d and diameter k cannot exceed the Moore bound, of the form M(d,k) = dk - O(dk-1) for d → ∞ and any fixed k. Known results in finite geometries on generalised (k+1)-gons imply, for k=2,3,5, existence of an infinite sequence of values of d such that n(d,k) = dk - o(dk). Thus, for k = 2,3,5 the Moore bound can be asymptotically approached in the sense that lim supd→ ∞ n(d,k)/M(d,k) =1; moreover, no such result is known for any other value of k ≥ 2. The corresponding graphs are, however, far from vertex-transitive, and there appears to be no obvious way to extend them to vertex-transitive graphs giving the same type of asymptotic result.
The second and the third author (2012) proved by a direct construction that the Moore bound for diameter k = 2 can, in a similar sense, be asymptotically approached by Cayley graphs. Subsequently, the first and the third author (2015) showed that the same construction can be derived from generalised triangles with polarity.
By a detailed analysis of regular orbits of suitable groups of automorphisms of graphs arising from polarity quotients of incidence graphs of generalised quadrangles with polarity, we prove that for an infinite set of values of d there exist Cayley graphs of degree d, diameter 3, and order d3 - O(d2.5). The Moore bound for diameter 3 can thus as well be asymptotically approached by Cayley graphs. We also show that this method does not extend to constructing Cayley graphs of diameter 5 from generalised hexagons with polarity.

Item Type: Journal Item
Copyright Holders: 2018 Elsevier Inc.
ISSN: 0095-8956
Project Funding Details:
Funded Project NameProject IDFunding Body
Not SetAPVV 0136-12Not Set
Not SetAPVV-15-0220Not Set
Not SetVEGA 1/0026/16Not Set
Not SetVEGA 1/0142/17Not Set
Keywords: Degree; Diameter; Cayley graph; Generalized quadrangle; Suzuki-Tits oval
Academic Unit/School: Faculty of Science, Technology, Engineering and Mathematics (STEM) > Mathematics and Statistics
Faculty of Science, Technology, Engineering and Mathematics (STEM)
Item ID: 55789
Depositing User: Jozef Širáň
Date Deposited: 13 Jul 2018 15:03
Last Modified: 21 Jun 2019 06:46
URI: http://oro.open.ac.uk/id/eprint/55789
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