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

Koung, C. C.; Opatrny, J.

Congr. Numerantium 95, 163-172 (1993).

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.

Reviewer: Du Ding-Zhu (Minneapolis)

MSC:

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

Keywords:

linear congruential graph; digraphs