DCC linear congruential graphs: a new class of interconnection networks
Jaroslav Opatrný, Dominique Sotteau, Narasimman Srinivasan, Krishnaiya Thulasiraman · IEEE Transactions on Computers · 1996
Let n be an integer and F={f/sub 1/:1/spl les/i/spl les/t for some integer t} be a finite set of linear functions. We define a linear congruential graph G(F, n) as a graph on the vertex set V={0, 1, ..., n-1}, in which any x/spl isin/V is adjacent to f/sub i/(x) mod n, 1/spl les/i/spl les/t. For a linear function g, and a subset V/sub 1/ of V we define a linear congruential graph G(F, n, g,V/sub 1/) as a graph on vertex set V, in which any x/spl isin/V is adjacent to f/sub i/(x) mod n, 1/spl les/i/spl les/t, and any x/spl isin/V/sub 1/ is also adjacent to g(x) mod n. These graphs generalize several well known families of graphs, e.g. the de Bruijn graphs. We give a family of linear functions, called DCC linear functions, that generate regular, highly connected graphs which are of substantially larger order than de Bruijn graphs of the same degree and diameter. Some theoretical and empirical properties of these graphs are given and their structural properties are studied.