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:

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://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 ²+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 d²−2d^1.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 + ½)² 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 ²−O(d3/2).

Item Type:

Journal Article

2011 Elsevier

ISSN:

0095-8956

Project Funding Details:

Funded Project Name	Project ID	Funding Body
Not Set	Not Set	VEGA Research Grants [1/0280/10 and 1/0781/11]
Not Set	Not Set	APVV Research Grants [0040-06, 0104-07 and 0223-10]
Not Set	Not Set	APVV LPP Research Grants [0145-06 and 0203-06]

Keywords:

degree; diameter; Moore bound; Cayley graph

Academic Unit/Department:

Faculty of Science, Technology, Engineering and Mathematics (STEM) > Mathematics and Statistics
Faculty of Science, Technology, Engineering and Mathematics (STEM)

Item ID:

32158

Depositing User:

Jozef Širáň

Date Deposited:

03 Feb 2012 11:28

Last Modified:

09 Aug 2016 16:12