THE HAMILTONIAN PROPERTY OF CONSECUTIVE-D DIGRAPHS

A consecutive-d digraph with n nodes is a digraph whose nodes are labe led by the residues modulo n and a link from node i to node j exists i ff j = qi + r, qi + r + 1,..., qi + r + d - 1 (mod n) where q and r ar e given. Many computer networks and multiprocessor systems use consecu tive-d digraphs as their interconnection networks. A digraph is called Hamiltonian if it contains a spanning circuit. The Hamiltonian proper ty provides the capability of configuring the interconnection network as a linear array, which is the configuration with broadcast practical significance of either n - 1 or n nodes in the presence of a single f aulty node or link. Characterization of Hamiltonian consecutive-1 digr aph has been previously given. In this paper, we prove that for gcd(n, q) > 1 the consecutive-d digraph is Hamiltonian iff d greater-than-or -equal-to gcd(n, q); and for gcd(n, q) = 1 it is Hamiltonian if d grea ter-than-or-equal-to 5.