In this paper, we extend some of the existing results and present several graphs which could serve as models for efficient 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. | Yugoslav Journal of Operations Research 26 (2016), Number 4, 423–439 DOI: SOME NEW MODELS FOR MULTIPROCESSOR INTERCONNECTION NETWORKS ´ Dragoˇs CVETKOVIC Mathematical Institute SANU, Belgrade, Serbia ecvetkod@ ´ Tatjana DAVIDOVIC Mathematical Institute SANU, Belgrade, Serbia tanjad@ ´ Irena M. JOVANOVIC School of Computing, Union University, Belgrade, Serbia irenaire@ Received: March 2016 / Accepted: October 2016 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 extend some of the existing results and present several graphs which could serve as models for efficient 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. MSC: 05C50, 68M10. 1. INTRODUCTION Spectral graph theory is a mathematical theory in which linear algebra and graph theory meet. It is a very well developed mathematical field (see, for exam- 424 D. Cvetkovi´c, T. Davidovi´c, I. M. Jovanovi´c / Some new nodels for MINs ple, [7] or [8]), but also an engineering discipline [14]. Here it will be applied to the study of multiprocessor interconnection networks (briefly MINs). Let G be a simple graph on n vertices, with the adjacency matrix A = A(G). The characteristic polynomial PG (x) = det(xI − A) of G is the characteristic polynomial of its adjacency matrix A. The eigenvalues of A, in non-increasing order, are denoted by λ1 (G), . . . , λn (G) and .
