The Spectra of Knodel Graphs

Knodel graphs W-d,W-n are regular graphs on n vertices and degree d. They have been introduced by W. Knodel and have been proved to be minimum gossip graphs and minimum broadcast graphs for d = [logn]. They became even more interesting in the light of recent results regarding the diameter, which is, up to now, the smallest known diameter among all minimum broadcast graphs on 2(d) vertices. Also, the logarithmic time routing algorithm that we have found, the bipancyclicity property, embedding properties and, nevertheless, Cayley graph structure, impel these graphs as good candidates for regular network constructions, especially in supercomputing. In this paper we describe an efficient way to com-pute the spectra of Knodel graphs using results from Fourier analysis, circulant matrices and PD-matrices. Based on this result we give a formula for the number of spanning trees in Knodel graphs.