Geodesic
Application of some Graph Invariants to the Analysis of Multiprocessor Interconnection Networks
Yugoslav journal of operations research, Tome 18 (2008) no. 2, p. 173 .

Voir la notice de l'article provenant de la source eLibrary of Mathematical Institute of the Serbian Academy of Sciences and Arts

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 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.
Classification : 90B10 68M07
Keywords: Multiprocessor systems, interconnection topologies, spectra of graphs, maximum vertex degree, diameter. 
@article{YJOR_2008_18_2_a3,
     author = {Drago\v{s} Cvetkovi\'c and Tatjana Davidovi\'c},
     title = {Application of some {Graph} {Invariants} to the {Analysis} of {Multiprocessor} {Interconnection} {Networks}},
     journal = {Yugoslav journal of operations research},
     pages = {173 },
     publisher = {mathdoc},
     volume = {18},
     number = {2},
     year = {2008},
     zbl = {1183.90070},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/YJOR_2008_18_2_a3/}
}
TY  - JOUR
AU  - Dragoš Cvetković
AU  - Tatjana Davidović
TI  - Application of some Graph Invariants to the Analysis of Multiprocessor Interconnection Networks
JO  - Yugoslav journal of operations research
PY  - 2008
SP  - 173 
VL  - 18
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/YJOR_2008_18_2_a3/
LA  - en
ID  - YJOR_2008_18_2_a3
ER  - 
%0 Journal Article
%A Dragoš Cvetković
%A Tatjana Davidović
%T Application of some Graph Invariants to the Analysis of Multiprocessor Interconnection Networks
%J Yugoslav journal of operations research
%D 2008
%P 173 
%V 18
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/YJOR_2008_18_2_a3/
%G en
%F YJOR_2008_18_2_a3
Dragoš Cvetković; Tatjana Davidović. Application of some Graph Invariants to the Analysis of Multiprocessor Interconnection Networks. Yugoslav journal of operations research, Tome 18 (2008) no. 2, p. 173 . http://geodesic.mathdoc.fr/item/YJOR_2008_18_2_a3/