THE LAPLACIAN SPECTRUM OF GRAPHS

THE LAPLACIAN SPECTRUM OF GRAPHS

1991 | Bojan Mohar
The paper surveys known results about the Laplacian spectrum of graphs, with a focus on the second smallest eigenvalue λ₂ and its connections to various graph invariants. The Laplacian matrix of a graph, defined as D(G) - A(G), where D(G) is the degree matrix and A(G) is the adjacency matrix, is central to the study. The eigenvalues of the Laplacian matrix, particularly λ₂, are important for understanding properties such as connectivity, expansion, isoperimetric number, maximum cut, and others. The paper discusses the spectral properties of the Laplacian matrix, including its positive semidefiniteness and the fact that its smallest eigenvalue is zero. It also covers operations on graphs, such as disjoint unions, Cartesian products, and joins, and their effects on the Laplacian spectrum. The Matrix-Tree-Theorem is highlighted as a key application of the Laplacian matrix, relating the number of spanning trees to the eigenvalues. The paper also explores the relationship between λ₂ and other graph properties, such as diameter, mean distance, and bandwidth. It discusses the algebraic connectivity of graphs, which is defined as λ₂, and its role in determining graph expansion and connectivity. The paper also touches on the use of the Laplacian spectrum in physical and chemical applications, such as modeling molecular structures and analyzing electrical networks. The results are summarized with a focus on the significance of λ₂ in graph theory and its practical implications.The paper surveys known results about the Laplacian spectrum of graphs, with a focus on the second smallest eigenvalue λ₂ and its connections to various graph invariants. The Laplacian matrix of a graph, defined as D(G) - A(G), where D(G) is the degree matrix and A(G) is the adjacency matrix, is central to the study. The eigenvalues of the Laplacian matrix, particularly λ₂, are important for understanding properties such as connectivity, expansion, isoperimetric number, maximum cut, and others. The paper discusses the spectral properties of the Laplacian matrix, including its positive semidefiniteness and the fact that its smallest eigenvalue is zero. It also covers operations on graphs, such as disjoint unions, Cartesian products, and joins, and their effects on the Laplacian spectrum. The Matrix-Tree-Theorem is highlighted as a key application of the Laplacian matrix, relating the number of spanning trees to the eigenvalues. The paper also explores the relationship between λ₂ and other graph properties, such as diameter, mean distance, and bandwidth. It discusses the algebraic connectivity of graphs, which is defined as λ₂, and its role in determining graph expansion and connectivity. The paper also touches on the use of the Laplacian spectrum in physical and chemical applications, such as modeling molecular structures and analyzing electrical networks. The results are summarized with a focus on the significance of λ₂ in graph theory and its practical implications.
Reach us at info@futurestudyspace.com
[slides and audio] The Laplacian spectrum of graphs