SOME NEW MODELS FOR MULTIPROCESSOR INTERCONNECTION NETWORKS

Abstract

A multiprocessor system can be modeled by a graph G. The vertices of G
correspond to processors while edges represent links between processors. To find suitable
models for multiprocessor interconnection networks (briefly MINs), one can apply tools
and techniques of spectral graph theory. In this paper, we are extending some of the
existing results and present several graphs that could serve as models for ecient MINs
based on the small values of the previously introduced graph tightness. These examples
of possible MINs arise as a result of some well-known and widely used graph operations.
We also examine the suitability of strongly regular graphs (briefly SRGs) to model MINs,
and prove the uniqueness of some of them.
Keywords: Spectra of graphs, Tightness, Interconnection networks, Graph operation.