Eigenvalues of the Laplacian of a graph∗
- 1 October 1985
- journal article
- research article
- Published by Taylor & Francis in Linear and Multilinear Algebra
- Vol. 18 (2) , 141-145
- https://doi.org/10.1080/03081088508817681
Abstract
Let G be a finite undirected graph with no loops or multiple edges. We define the Laplacian matrix of G,Δ(G)by Δij= degree of vertex i and Δij−1 if there is an edge between vertex i and vertex j. In this paper we relate the structure of the graph G to the eigenvalues of A(G): in particular we prove that all the eigenvalues of Δ(G) are non-negative, less than or equal to the number of vertices, and less than or equal to twice the maximum vertex degree. Precise conditions for equality are given.Keywords
This publication has 4 references indexed in Scilit:
- Algebraic connectivity of graphsCzechoslovak Mathematical Journal, 1973
- On characterizing certain graphs with four eigenvalues by their spectraLinear Algebra and its Applications, 1970
- GRAPH THEORYPublished by Defense Technical Information Center (DTIC) ,1969
- On hearing the shape of a drumJournal of Combinatorial Theory, 1966