THE HAMILTONIAN PROPERTY OF THE CONSECUTIVE-3 DIGRAPH

A consecutive-d digraph is a digraph G(d, n, q, r) whose n nodes are l abeled by the residues module n and a link from node i to node j exist s if and only if j = qi + k (mod n) for some Ic with r less than or eq ual to k less than or equal to r + d - 1. Consecutive-d digraphs are u sed as models for many computer networks and multiprocessor systems, i n which the existence of a Hamiltonian circuit is important. Condition s for a consecutive-d graph to have a Hamiltonian circuit were known e xcept for gcd(la, d) = 1 and d = 3 Or 4. It was conjectured by Du, Hsu , and Hwang that a consecutive-3 digraph is Hamiltonian. This paper pr oduces several infinite classes of consecutive-3 digraphs which are no t (respectively, are) Hamiltonian, thus suggesting that the conjecture needs modification.