Construction and Analysis of Graph Models for Multiprocessor Interconnection Networks

Abstract

A graph G can serve as a model for the Multiprocessor Interconnection Networks (MINs) in which the vertices represent the processors, while the edges represent connections between processors. This paper presents several graphs that could qualify as models for efficient MINs based on the small values of the graph tightness previously introduced by Cvetković and Davidović in 2008.  These graphs are constructed using some well-known and widely used graph operations. The tightness values of these graphs range from  $O(\sqrt[4]{N})$ to $O(\sqrt{N})$ where $N$ is the order of a graph under consideration.  Also, two  new graph tightness values namely \textit{Third type mixed tightness $t_3(G)$} and \textit{Second type of Structural tightness $t_4(G)$} are defined in this paper.