Eigenvalues of the Laplacian of a graph
Anderson, William N.; Morley, Thomas D.; Anderson, William N.; Fairleigh Dickinson University; Morley, Thomas D.; Fairleigh Dickinson University
Журнал:
Linear and Multilinear Algebra
Дата:
1985
Аннотация:
Let G be a finite undirected graph with no loops or multiple edges. We define the Laplacian matrix of G,Δ(G)by Δ<sub>ij</sub>= degree of vertex i and Δ<sub>ij</sub>−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.
1.175Мб