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: http://dx.doi.org/10.1016/j.jctb.2011.07.005
Google Scholar: Look up in Google Scholar

Abstract

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
Item ID: 32158
Depositing User: Jozef Širáň
Date Deposited: 03 Feb 2012 11:28
Last Modified: 28 Aug 2013 08:34
URI: http://oro.open.ac.uk/id/eprint/32158
Share this page:

Actions (login may be required)

View Item
Report issue / request change

Policies | Disclaimer

© The Open University   + 44 (0)870 333 4340   general-enquiries@open.ac.uk