EXTREMAL CAYLEY DIGRAPHS OF FINITE CYCLIC GROUPS

Let Cay(m, A) denote the Cayley digraph of Z(m) generated by A, where Z(m) is the cyclic group of residues module m. Let r(m, A) denote the average distance of Cay (m, A). For any r greater than or equal to 1 a nd k greater than or equal to 1 define m(r, A) as the largest positiv e integer m such that the average distance of the Cayley digraph Cay(m , A) is at most r for some set A with k elements. In this paper, an as ymptotic formula for m(r, 2) is proved and a lower bound for m*(r, k) is also obtained for k greater than or equal to 3. Applications to th e construction of optimal distributed loop networks are discussed in t his paper. A lower bound of the average order of subsets for asymptoti c bases in number theory is proved using the main theorem of this pape r.