Scalable sparse topologies with small spectrum
One of the fundamental properties of a graph is the number of distinct eigenvalues of its adjacency or Laplacian matrix. Determining this number is of theoretical interest and also of practical impact. Graphs with small spectra exhibit many symmetry properties and are well suited as interconnection topologies. Especially load balancing can be done on such interconnection topologies in a small number of steps. In this paper we are interested in graphs with maximal degree \(O(\log n)\), where \(n\) is the number of vertices, and with a small number of distinct eigenvalues. Our goal is to find scalable families of such graphs with polylogarithmic spectrum in the number of vertices. We present also the eigenvalues of the Butterfly graph. For the entire collection see [Zbl 0958.00036].
This page was built for publication: Scalable sparse topologies with small spectrum
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2762507)