MULTIDIMENSIONAL LINEAR CONGRUENTIAL GRAPHS

Let d be an integer, F be a finite set of d-dimensional linear functio ns and s over arrow pointing right = (s1, s2,..., s(d)), be a dimensio nal vector of positive integers. We define graph G (F, s over arrow po inting right), called a linear congruential graph of dimension d as a graph on the vertex set V = Z(s1) x Z(s2) x ... x Z(sd), in which any x over arrow pointing right is-an-element-of V is adjacent to the vert ices f(i) (x over arrow pointing right) mod s over arrow pointing righ t for any f(i) in F. These graphs generalize several well known famili es of graphs. e.g. the de Bruijn graphs, chordal graphs, and linear co ngruential graphs. We show that, for a properly selected set of functi ons, multidimensional linear congruential graphs generate regular, hig hly connected graphs which are substantially larger than linear congru ential graphs, or any other large family of graphs of the same degree and diameter. Some theoretical and empirical properties of these graph s are given and their structural properties am studied.