Multidimensional linear congruential graphs. (English) Zbl 0883.68101

Koung, C. C.; Opatrny, J.

RAIRO, Inform. Théor. Appl. 28, No. 3-4, 187-199 (1994).

Summary: Let \(d\) be an integer, \(F\) be a finite set of \(d\)-dimensional linear functions and \(\vec s=(s_1,s_2, \dots, s_d)\), be a \(d\)-dimensional vector of positive integers. We define graph \(G(F,\vec s)\), called a linear congruential graph of dimension \(d\) as a graph on the vertex set \(V=Z_{s_1} \times Z_{s_2} \times \cdots \times Z_{s_d}\), in which any \(\vec x\in V\) is adjacent to the vertices \(f_i(\vec x) \bmod\vec s\), for any \(f_i\) in \(F\).
These graphs generalize several well known families of graphs, e.g. the de Bruijn graphs, chordal graphs, and linear congruential graphs. We show that, for a properly selected set of functions, multidimensional linear congruential graphs generate regular, highly connected graphs which are substantially larger than linear congruential graphs, or any other large family of graphs of the same degree and diameter. Some theoretical and empirical properties of these graphs are given and their structural properties are studied.

MSC:

68R10

Graph theory (including graph drawing) in computer science

Keywords:

linear congruential graph; Bruijn graphs; chordal graphs

References:

[1]	1. J. C. BERMOND, C. DELORME and J. J. QUISQUATER, Strategies for interconnection networks: some methods from graph theory, Journal of Parallel and Distributed Computing, 1986, 3, pp. 433-449.
[2]	2. J. C. BERMOND, C. PEYRAT, de BRUIJN and KAUTZ networks: a competitor for the hypercube? Hypercube and Distributed Computers, 1989, pp. 279-294.
[3]	3. J. A. BONDY and U. S. R. MURTY, Graphs Theory with Applications, North Holland, 1976. · Zbl 1226.05083
[4]	4. F. R. K. CHUNG, Diameters of graphs: old problems and new results, Proceedings of the 18th South-Eastern Conference on Combinatorics, Graph Theory, and Computing, Congressus Numerantium, 1987, pp. 295-317. Zbl0695.05029 MR945240 · Zbl 0695.05029
[5]	5. C. DELORME, A Table of Large Graphs of Small Degrees and Diameters, personal communication, 1990.
[6]	6. D. Z. DU and F. K. HWANG, Generalized de Bruijn Digraphs, Networks, 1988, 18, pp. 28-38. Zbl0654.05036 MR926031 · Zbl 0654.05036 · doi:10.1002/net.3230180105
[7]	7. B. ELPAS, Topological Constrains on Interconnection Limited Logic, Switching Circuits Theory and Logical Design, 1964, 5, pp. 133-147.
[8]	8. M. IMASE and M. ITOH, Design to minimize diameter on building block network, IEEE Trans. on Computers, 1981, C-30, pp. 439-442. Zbl0456.94030 MR626733 · Zbl 0456.94030 · doi:10.1109/TC.1981.1675809
[9]	9. W. H. KAUTZ, Bounds on directed (d, k) graphs, Theory of Cellular Logic Networks and Machines, SRI Project 7258, 1968, pp. 20-28.
[10]	10. D. E. KNUTH, The art of computer programming, Seminumerical Algorithms, Addison-Wesley, II, 1972. MR378456 · Zbl 0191.18001
[11]	11. C. C. KOUNG, Multi-dimensional Linear Congruential Network Models, Master’s Thesis, Dept. of Comp. Sci. Concordia University, Montreal, 1993. · Zbl 0804.05048
[12]	12. W. LELAND and M. SOLOMON, Dense trivalent graphs for processor interconnection, IEEE Trans, on Computers, 1982, 31, No. 3, pp. 219-222. Zbl0477.68068 MR648372 · Zbl 0477.68068 · doi:10.1109/TC.1982.1675977
[13]	13. J. OPATRNY and D. SOTTEAU, Linear Congruential Graphs, Graph Theory, Combinatorics, Algorithms, and Applications, SIAM proceedings series, 1991, pp. 404-426. Zbl0739.05074 MR1132923 · Zbl 0739.05074
[14]	14. J. OPATRNY, D. SOTTEAU, N. SRINIVASAN and K. THULASIRAMAN, DCC Linear Congruential Graphs, a New Network Model, IEEE Trans. Comput., to appear. MR1376915
[15]	15. M. R. SAMANTHAM and D. K. PRADHAM, The de Bruijn Multiprocessor Network: A Versatile Parallel Processing and Sorting Network for VLSI, IEEE Trans. Cornput., 1989,38, No. 4, pp. 567-581. Zbl0671.94028 MR984681 · Zbl 0671.94028 · doi:10.1109/12.21149