\(d\)-dimensional linear congruential graphs. (English) Zbl 0804.05048

The \(d\)-dimensional linear congruential graph is defined as follows: The vertex set is a finite \(d\)-dimensional linear space \(Z_{s_ 1} \times \cdots \times Z_{s_ d}\) where \(Z_{s_ i}\) is the residue group modulo \(s_ i\). The edge set is defined by \(d\) linear functions. This is a generalization of de Bruijn digraphs, Kautz digraphs, generalized de Bruijn digraphs, and Imase-Itoh digraphs. In this paper, the authors show that for properly selected functions, 2-dimensional linear congruential graphs generate regular, highly connected graphs.


05C50 Graphs and linear algebra (matrices, eigenvalues, etc.)
05C20 Directed graphs (digraphs), tournaments