Spectra of weighted compound graphs of generalized Bethe trees

Abstract

A generalized Bethe tree is a rooted tree in which vertices at the same distance from the root have the same degree. Let G_m be a connected weighted graph on m vertices. Let {B_i :1≤ i ≤ m} be a set of trees such that, for i =1 ,2,...,m ,

(i) Bi is a generalized Bethe tree of k_i levels,

(ii) the vertices of B_i at the level j have degree d_i,ki−j+1 for j =1 ,2,...,k_i, and

(iii) the edges of B_i joining the vertices at the level j with the vertices at the level (j + 1) have weight w_i,ki−j for j =1 ,2,...,k _{i −1}.

Let G_m{Bi :1≤ i ≤ m} be the graph obtained fromG_m and the trees B₁,B₂,...,B_m by identifying the root vertex of B_i with the ith vertex of G_m. A complete characterization is given of the eigenvalues of the Laplacian and adjacency matrices of G_m {B_i :1≤ i ≤ m} together with results about their multiplicities. Finally, these results are applied to the particular case B₁ = B₂ = ···= B_m.