The Open UniversitySkip to content

Approaching the Moore bound for diameter two by Cayleygraphs

Šiagiová, Jana and Siran, Jozef (2012). Approaching the Moore bound for diameter two by Cayleygraphs. Journal of Combinatorial Theory, Series B, 102(2) pp. 470–473.

Full text available as:
Full text not publicly available
Due to copyright restrictions, this file is not available for public download
Click here to request a copy from the OU Author.
DOI (Digital Object Identifier) Link:
Google Scholar: Look up in Google Scholar


The order of a graph of maximum degree d and diameter 2 cannot exceed d 2+1, the Moore bound for diameter two. A combination of known results guarantees the existence of regular graphs of degree d, diameter 2, and order at least d2−2d1.525 for all sufficiently large d, asymptotically approaching the Moore bound. The corresponding graphs, however, tend to have a fairly small or trivial automorphism group and the nature of their construction does not appear to allow for modifications that would result in a higher level of symmetry. The best currently available construction of vertex-transitive graphs of diameter 2 and preassigned degree gives order 8/9 (d + ½)2 for all degrees of the form d=(3q−1)/2 for prime powers q=1 mod 4. In this note we show that for an infinite set of degrees d there exist Cayley, and hence vertex-transitive, graphs of degree d, diameter 2, and order d 2−O(d3/2).

Item Type: Journal Article
Copyright Holders: 2011 Elsevier
ISSN: 0095-8956
Project Funding Details:
Funded Project NameProject IDFunding Body
Not SetNot SetVEGA Research Grants [1/0280/10 and 1/0781/11]
Not SetNot SetAPVV Research Grants [0040-06, 0104-07 and 0223-10]
Not SetNot SetAPVV LPP Research Grants [0145-06 and 0203-06]
Keywords: degree; diameter; Moore bound; Cayley graph
Academic Unit/Department: Mathematics, Computing and Technology > Mathematics and Statistics
Mathematics, Computing and Technology
Item ID: 32158
Depositing User: Jozef Širáň
Date Deposited: 03 Feb 2012 11:28
Last Modified: 26 Feb 2016 13:27
Share this page:


Scopus Citations

▼ Automated document suggestions from open access sources

Actions (login may be required)

Policies | Disclaimer

© The Open University   + 44 (0)870 333 4340