ELA
SPECTRA OF WEIGHTED COMPOUND GRAPHS OF GENERALIZED BETHE TREES
∗OSCAR ROJO† AND LUIS MEDINA†
Abstract. A generalized Bethe tree is a rooted tree in which vertices at the same distance from the root have the same degree. LetGmbe a connected weighted graph on mvertices. Let {Bi: 1≤i≤m}be a set of trees such that, fori= 1,2, . . . , m,
(i)Biis a generalized Bethe tree ofkilevels,
(ii) the vertices ofBiat the leveljhave degreedi,ki−j+1forj= 1,2, . . . , ki, and
(iii) the edges ofBijoining the vertices at the leveljwith the vertices at the level (j+ 1) have weightwi,ki−jforj= 1,2, . . . , ki−1.
LetGm{Bi: 1≤i≤m}be the graph obtained fromGmand the treesB1,B2, . . . ,Bmby identify- ing the root vertex ofBiwith theith vertex ofGm. A complete characterization is given of the eigen- values of the Laplacian and adjacency matrices ofGm{Bi: 1≤i≤m}together with results about their multiplicities. Finally, these results are applied to the particular caseB1=B2=· · ·=Bm.
Key words. Weighted graph, Generalized Bethe tree, Laplacian matrix, Adjacency matrix, Spectral radius, Algebraic connectivity.
AMS subject classifications.5C50, 15A48.
∗Received by the editors June 30, 2008. Accepted for publication December 30, 2008. Handling Editor: Michael Neumann.
†Department of Mathematics, Universidad Cat´olica del Norte, Antofagasta, Chile ([email protected]).
The work of the first author was supported by Project Fondecyt 1070537, Chile. The work of the second author was supported by Project Mecesup UCN0202, Chile.
Electronic Journal of Linear Algebra ISSN 1081-3810 A publication of the International Linear Algebra Society Volume 18, pp. 30-57, January 2009
http://math.technion.ac.il/iic/ela
