THE LAPLACIAN SPECTRUM OF GRAPHS

THE LAPLACIAN SPECTRUM OF GRAPHS

1991 | Bojan Mohar
The paper provides a comprehensive survey of the Laplacian spectrum of graphs, focusing on the second smallest Laplacian eigenvalue \(\lambda_2\) and its significance in various graph invariants. The Laplacian matrix \(Q(G)\) of a graph \(G\) is defined as \(D(G) - A(G)\), where \(D(G)\) is the diagonal matrix of vertex degrees and \(A(G)\) is the adjacency matrix. The paper discusses the basic properties of \(Q(G)\), including its real eigenvalues, positive semidefiniteness, and the fact that its smallest eigenvalue is 0 with multiplicity equal to the number of connected components. The paper also explores the spectra of graphs obtained through various operations such as disjoint union, Cartesian product, and complementation. It highlights the Matrix-Tree Theorem, which relates the number of spanning trees of a graph to the determinant of a modified Laplacian matrix. The physical and chemical applications of the Laplacian matrix are discussed, including its role in the vibration of membranes, electrical networks, and molecular structure analysis. A significant portion of the paper is dedicated to the second smallest Laplacian eigenvalue \(\lambda_2\), which is crucial for understanding graph connectivity, expandability, and other properties. The paper presents inequalities and bounds for \(\lambda_2\) in relation to vertex and edge connectivity, diameter, mean distance, and genus. It also discusses the concept of characteristic valuations and their applications in heuristic algorithms and optimal labeling problems. Finally, the paper touches on miscellaneous topics, including the relationship between the Laplacian and adjacency spectra of regular graphs, the study of cospectral graphs, and the permanental polynomial of the Laplacian matrix. The references section lists key works in the field, providing a comprehensive resource for further study.The paper provides a comprehensive survey of the Laplacian spectrum of graphs, focusing on the second smallest Laplacian eigenvalue \(\lambda_2\) and its significance in various graph invariants. The Laplacian matrix \(Q(G)\) of a graph \(G\) is defined as \(D(G) - A(G)\), where \(D(G)\) is the diagonal matrix of vertex degrees and \(A(G)\) is the adjacency matrix. The paper discusses the basic properties of \(Q(G)\), including its real eigenvalues, positive semidefiniteness, and the fact that its smallest eigenvalue is 0 with multiplicity equal to the number of connected components. The paper also explores the spectra of graphs obtained through various operations such as disjoint union, Cartesian product, and complementation. It highlights the Matrix-Tree Theorem, which relates the number of spanning trees of a graph to the determinant of a modified Laplacian matrix. The physical and chemical applications of the Laplacian matrix are discussed, including its role in the vibration of membranes, electrical networks, and molecular structure analysis. A significant portion of the paper is dedicated to the second smallest Laplacian eigenvalue \(\lambda_2\), which is crucial for understanding graph connectivity, expandability, and other properties. The paper presents inequalities and bounds for \(\lambda_2\) in relation to vertex and edge connectivity, diameter, mean distance, and genus. It also discusses the concept of characteristic valuations and their applications in heuristic algorithms and optimal labeling problems. Finally, the paper touches on miscellaneous topics, including the relationship between the Laplacian and adjacency spectra of regular graphs, the study of cospectral graphs, and the permanental polynomial of the Laplacian matrix. The references section lists key works in the field, providing a comprehensive resource for further study.
Reach us at info@study.space
[slides and audio] The Laplacian spectrum of graphs