A NOTE ON LARGE GRAPHS OF DIAMETER 2 AND GIVEN MAXIMUM DEGREE

Let vt(d, 2) be the largest order of a vertex-transitive graph of degr ee d and diameter 2. It is known that vt(d, 2)= d(2) + 1 for d= 1, 2, 3, and 7; for the remaining values of d we have ct(d, 2)less than or e qual to d(2)-1. The only known general lower bound on vt(d, 2), valid for all d, seems to be vt(d 2) greater than or equal to [(d+ 2)/2][(df 2)/2]. Using voltage graphs, we construct a family of vertex-transiti ve non-Cayley graphs which shows that ui(d, 2) greater than or equal t o(8/9)(d+1/2)(2) for all d of the form d=(3q-1)/2, where q is a prime power congruent with 1 (mod 4). The construction generalizes to all pr ime powers and yields large highly symmetric graphs for other degrees as well. In particular, for d=7 we obtain as a special case the Hoffma n-Singleton graph, and for d=11 and d=13 we have new largest graphs of diameter 2, and degree d on 98 and 162 vertices, respectively. (C) 19 98 Academic Press.