A note on large graphs of diameter two and given maximum degree (Q1272472)

The well-known degree/diameter problem asks for determining the largest number of vertices in a graph of maximum degree \(d\) and diameter \(k\). In this paper the case of vertex-transitive graphs and \(k=2\) is considered. The upper (Moore) bound is \(d^2+1\), but the previously known lower bound was asymptotically only \(d^2/4\). Using voltage graphs, the authors construct vertex-transitive non-Cayley graphs with asymptotically \(8d^2/9\) vertices for a selected sequence of \(d\)'s.