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(4√N) to O(√N), where N is the order of the graph under consideration. Also, two new graph tightness values, namely Third type mixed tightness t3(G) and Second type of Structural tightness t4(G) are defined in this paper. It has been shown that these tightness types are easier to calculate than the others for the considered graphs. Moreover, their values are significantly smaller.

Keywords

• interconnection networks
• graph tightness
• line graph
• chromatic number
• chromatic index