Authors: Cvetković, Dragoš
Davidović, Tatjana 
Title: Application of some graph invariants to the analysis of multiprocessor interconnection networks
Journal: Yugoslav Journal of Operations Research
Volume: 18
Issue: 2
First page: 173
Last page: 186
Issue Date: 1-Jan-2008
ISSN: 0354-0243
DOI: 10.2298/YJOR0802173C
Let G be a graph with diameter D, maximum vertex degree Δ, the largest eigenvalue λ1 and m distinct eigenvalues. The products mΔ and (D+1) λ1 are called the tightness of G of the first and second type, respectively. In the recent literature it was suggested that graphs with a small tightness of the first type are good models for the multiprocessor interconnection networks. We study these and some other types of tightness and some related graph invariants and demonstrate their usefulness in the analysis of multiprocessor interconnection networks. Tightness values for graphs of some standard interconnection networks are determined. We also present some facts showing that the tightness of the second type is a relevant graph invariant. We prove that the number of connected graphs with a bounded tightness is finite.
Keywords: Diameter | Interconnection topologies | Maximum vertex degree | Multiprocessor systems | Spectra of graphs
Publisher: Fakultet organizacionih nauka, Beograd
Project: Graph theory and mathematical programming with applications in chemistry and engineering 

Show full item record


checked on Jun 13, 2024

Page view(s)

checked on May 9, 2024

Google ScholarTM




Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.