constructed a family of the currently largest known vertex-transitive graphs of degree d, diameter 2, and order 8 9 (d+ 1 2 ) 2 , for infinitely many values of d. We present a simplified construction of their graphs.
2001 Academic Press
The vertex-transitive version of the degree-diameter problem is to determine the largest order vt d, k of a vertex-transitive graph of degree d and diameter k. No general results on vt d, k are known for k 3. In the case of 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 vt d, 2 d 2 &1, see [4]. The only general lower bound on vt d, 2 , valid for all d, is vt d, 2 w d+2 2 x W d+2 2 X ; it is based on a Cayley graph for the group Z w(d+2)Â2x _Z W(d+2)Â2X . For further references see [1 3, 5, 7].
Recently, McKay, Miller, and S8 ira n [7] constructed a family of vertextransitive graphs H q (indexed by prime powers q#1 (mod 4)) of diameter two, valence d=(3q&1)Â2, and order 8 9 (d+ 1 2 ) 2 . This shows that vt d, 2 8 9 (d+ 1 2 ) 2 for infinitely many values of d. The graphs H q are the currently largest known vertex-transitive graphs of diameter two and given valence d=(3q&1)Â2. For example, H 5 is the Hoffman Singleton graph, and the graph H 9 of order 162 misses the Moore bound d 2 +1=170 just by 8.
To describe the graphs H q , let F=GF(q) denote a finite field of prime power order q=4k+1, let ! be a primitive element of F, and let X=[1, ! 2 , ! 4 , ..., ! 4k&2 ]. The vertex set of the graph H q is the set V=[0, 1]_F_F, and each vertex (r, i, m) is adjacent in H q to the |X | vertices (r, i, m+! r x), x # X, as well as to the q vertices (1&r, j, m+(&1) r ij), j # F. As |X | = (q&1)Â2, this gives the vertex valence d=(3q&1)Â2. Further, for s, t # F the graph H q has automorphisms f s , g t : V Ä V given by f s (r, i, m)= (r, i, m+s) and g t (r, i, m)=(r, i+t, m&(&1) r it+rt 2 ) that fix setwise the vertex sets V r =[r]_F_F where r=0, 1. The automorphism h defined by h(r, i, m)=(1&r, (&!) r i, !m) interchanges the sets V 0 and V 1 . The group