Extremal Problems in the Construction of Distributed Loop Networks

Abstract

Let $G( N,A )$ be the Cayley digraph associated with $Z/( N )$ and A, where N is a positive integer and A is a subset of $\{ 1,2, \ldots ,N - 1 \}$. Let $N( d,k )$ be the maximum N such that the diameter of $G( N,A )$ is less than or equal to d for some $A = \{ a_1 ,a_2 , \ldots , a_k \}$ with $1 = a_1 < a_2 < \cdots < a_k $. An exact formula for $N( d,2 )$ is given, and $N( d,k )$ is estimated for $k \geq 3$. These results provide new bounds for minimal diameter in the construction of loop networks. A relation between this problem and the postage stamp problem in additive number theory is established to enhance the study of these problems.