MULTIPROCESSOR INTERCONNECTION NETWORKS WITH SMALL TIGHTNESS

作者：Cvetkovic Dragos^*; Davidovic Tatjana

来源：International Journal of Foundations of Computer Science, 2009, 20(5): 941-963.

DOI：10.1142/S0129054109006978

• Multiprocessor Systems
• Interconnection Topologies
• Spectra of Graphs
• Graph Invariants

Homogeneous multiprocessor systems are usually modelled by undirected graphs. Vert ices of these graphs represent the processors,while edges denote the connection links between adjacent processors. Let G be a graph with diameter D, maximum vertex degree Delta, the largest eigenvalue lambda(1) and m distinct eigenvalues. the products m Delta and (D 1)lambda(1) are called the tightness of G of the first and second type,respectively. in recent literature it was suggested that graphs with a small tightness of the first type are good models for the multiprocessor interconnection networks. in a previous paper we studied the se and some other types of tightness and some related graph invariants and demonstrated their usefulness in the analysis of multiprocessor interconnection networks. We proved that the number of connected graphs with a bounded tightness is finite. In this paper we determine explicitly graphs with tightness values not exceeding 9. There are 69 such graphs and they contain up to 10 vertices. in addition we identify graphs with minimal tightness values when the number of vertices is n = 2,...,10.

• 出版日期2009-10