Linear congruential graphs. (English) Zbl 0739.05074

Opatrny, J.; Sotteau, D.

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

Keywords:

linear congruential graph of type 1; linear congruential graph of type 2

Citations:

Zbl 0734.00014