## Linear congruential graphs.(English)Zbl 0739.05074

Graph theory, combinatorics, algorithms, and applications, Proc. 2nd Int. Conf., San Francisco/CA (USA) 1989, 404-415 (1991).
Summary: [For the entire collection see Zbl 0734.00014.]
For an integer $$n$$ and a finite set of linear functions $$F=\{f_ i(x)=(a_ ix+c_ i)$$, $$1\leq i\leq k\}$$ we define a linear congruential graph of type 1 as a graph on vertex set $$\{0,1,\dots,n-1\}$$ in which any $$x\in\{0,1,\dots,n-1\}$$ is adjacent to $$f_ i(x)\hbox{ mod }n$$, $$1\leq i\leq k$$. Similarly, for an even integer $$n$$, a linear congruential graph of type 2 is a graph on vertex set $$\{0,1,\dots,n-1\}$$ in which any $$x\in\{0,1,\dots,n-1\}$$ is adjacent to $$f_ i(x)\hbox{ mod }n$$, $$1\leq i\leq k-1$$, and any even vertex $$x\in\{0,1,\dots,n-2\}$$ is adjacent to $$f_ k(x)\hbox{ mod }n$$.
Some theoretical and empirical properties of linear congruential graphs are given and the structure of these graphs is studied. A suitability of linear congruential graphs for interconnection networks is considered, and a comparison to other network models is done.

### MSC:

 05C75 Structural characterization of families of graphs 94C15 Applications of graph theory to circuits and networks

Zbl 0734.00014