Abstract

A generalized Bethe tree is a rooted unweighted tree in which vertices at the same level have the same degree. Let G be any connected graph. Let G {B} be the graph obtained from G by attaching a generalized Bethe tree B, by its root, to each vertex of G. We characterize completely the eigenvalues of the signless Laplacian, Laplacian and adjacency matrices of the graph G {B} including results on the eigenvalue multiplicities. Finally, for the Laplacian and signless Laplacian matrices, we recall a procedure to compute a tight upper bound on the algebraic connectivity of G {B} as well as on the smallest eigenvalue of the signless Laplacian matrix of G {B} whenever G is a non-bipartite graph. © 2009 Elsevier Inc. All rights reserved.