The Laplacian Spectrum of a Graph II

Abstract

Let G be a graph. Denote by $D( G )$ the diagonal matrix of its vertex degrees and by $A( G )$ its adjacency matrix. Then $L( G ) = D( G ) - A( G )$ is the Laplacian matrix of G. The first section of this paper is devoted to properties of Laplacian integral graphs, those for which the Laplacian spectrum consists entirely of integers. The second section relates the degree sequence and the Laplacian spectrum through majorization. The third section introduces the notion of a d-cluster, using it to bound the multiplicity of d in the spectrum of $L( G )$.