DCC linear congruential graphs: a new class of interconnection networks

Let n be an integer and F={f₁:1⩽i⩽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∈V is adjacent to f_i(x) mod n, 1⩽i⩽t. For a linear function g, and a subset V₁ of V we define a linear congruential graph G(F, n, g,V₁) as a graph on vertex set V, in which any x∈V is adjacent to f_i(x) mod n, 1⩽i⩽t, and any x∈V₁ 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