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.

DOI: https://doi.org/10.1016/j.jctb.2011.07.005

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).

Viewing alternatives

Metrics

Item Actions

Export

You can export this page using these formats Digital Object Identifier - DOI

About

• Item ORO ID
• 32158
• Item Type
• Journal Item
• 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 or School
• Faculty of Science, Technology, Engineering and Mathematics (STEM) > Mathematics and Statistics
  Faculty of Science, Technology, Engineering and Mathematics (STEM)
• Copyright Holders
• © 2011 Elsevier
• Depositing User
• Jozef Širáň