zbMATH — the first resource for mathematics

A Moore-like bound for graphs of diameter 2 and given degree, obtained as abelian lifts of dipoles. (English) Zbl 1046.05023
Several known constructions of large graphs with given degree and diameter turn out to be equivalent to lifting a suitable voltage graph. The author investigates upper bounds of Moore type for the number \(n(d,2)\) of vertices of a graph of diameter two and given degree \(d\) that arises as a lift of a dipole equipped with a voltage assignment in an abelian group. From the results it follows that, for instance, \(n(d,2)<0.933\,d^2\) for all sufficiently large \(d\). This is better than the general Moore bound \(1+d^2\) and compares well with the order of the McKay-Miller-Širáň graphs, which is approximately \(0.889\,d^2\) for infinitely many values of \(d\).

05C12 Distance in graphs
05C35 Extremal problems in graph theory
Full Text: EMIS EuDML