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