Interconnection Networks and Their Eigenvalues
Ke Qiang Qiu, Sajal Kumar Das · International Journal of Foundations of Computer Science · 2003
Interconnection networks of various topologies have been widely used in designing multiprocessor architectures. Study of graph theoretical or combinatorial properties of such networks help us better understand them, as well as develop on these architectures more efficient parallel algorithms including fault-tolerant communication/routing algorithms. In this paper, we analyze a broad class of interconnection networks from a new angle by looking into the corresponding graph spectra (i.e., eigenvalues and their multiplicities). Since eigenvalues of the edjacency matrix of a graph can reveal many important properties of the graph that are closely related to its combinatorial invariants, we believe that the study of spectra of interconnection networks can be a more unified approach to studying their topological properties. As a first step) in this direction, here we mainly concentrate on finding out the spectra of some of the most studied interconnection networks. Specifically, after a brief survey of results that relate spectra of graphs to their structural properties, we summarize the existing results for eigenvalues and multiplicities of several popular interconnection networks such as the hypercube and mesh. We also derive some of these results in a more straightforward way. Then we present new results on spectra for some other known networks such as the line graph of the hypercube, followed by experimental results on a few others including the star and pancake networks.