Published in

Elsevier, Applied Mathematics and Computation, 6(217), p. 2468-2480

DOI: 10.1016/j.amc.2010.07.058

Links

Tools

Export citation

Search in Google Scholar

Graphs for small multiprocessor interconnection networks

This paper is available in a repository.
This paper is available in a repository.

Full text: Download

Green circle
Preprint: archiving allowed
Red circle
Postprint: archiving forbidden
Red circle
Published version: archiving forbidden
Data provided by SHERPA/RoMEO

Abstract

Let D be the diameter of a graph G and let λ1 be the largest eigenvalue of its (0, 1)-adjacency matrix. We give a proof of the fact that there are exactly 69 non-trivial connected graphs with (D + 1)λ1 ⩽ 9. These 69 graphs all have up to 10 vertices and were recently found to be suitable models for small multiprocessor interconnection networks. We also examine the suitability of integral graphs to model multiprocessor interconnection networks, especially with respect to the load balancing problem. In addition, we classify integral graphs with small values of (D + 1)λ1 in connection with the load balancing problem for multiprocessor systems.