Cayley digraphs from complete generalized cycles

The complete generalized cycle G(d, n) is the digraph which has Z(n) x Z(d) as the vertex set and every vertex (i, x) is adjacent to the d vertices (i + 1, y) with y is an element of Z(d). As a main result, we give a necessary and sufficient condition for the iterated line digraph G(d, n, k) = L(k-1)G(d, n), with d a prime number, to be a Cayley digraph in terms of the existence of a group Gamma(d) of order d and a subgroup N of (Gamma(d))(n) isomorphic to (Gamma(d))(k). The condition is shown to be also sufficient for any integer d greater than or equal to 2. If Gamma(d) is a ring R and N is a submodule of R-n, it is said that G(d, n, k) is an R-Cayley digraph. By using some properties of the homogeneous linear recurrences in finite rings, necessary and sufficient conditions for G(d, n, k) to be an R-Cayley digraph are obtained. As a consequence, when R = Z(d) a new characterization for the digraphs G(d, n, k) to be Z(d)-Cayley digraphs is derived. As a corollary, sufficient conditions for the corresponding underlying graphs to be Cayley can be deduced. If d is a prime power and F-d is a finite field of order d, the digraphs G(d, n, k) which are F-d-Cayley digraphs are in 1-1 correspondence with the cyclic (n, k)-linear codes over F-d. (C) 1999 Academic Press.