The Laplacian eigenvalues of graphs: a survey

Abstract

The Laplacian matrix of a simple graph is the difference of the diagonal matrix of vertex degree and the (0,1) adjacency matrix. In the past decades, the Laplacian spectrum has received much more and more attention, since it has been applied to several fields, such as randomized algorithms, combinatorial optimization problems and machine learning. This paper is primarily a survey of various aspects of the eigenvalues of the Laplacian matrix of a graph for the past teens. In addition, some new unpublished results and questions are concluded. Emphasis is given on classifications of the upper and lower bounds for the Laplacian eigenvalues of graphs (including some special graphs, such as trees, bipartite graphs, triangular-free graphs, cubic graphs, etc.) as a function of other graph invariants, such as degree sequence, the average 2-degree, diameter, the maximal independence number, the maximal matching number, vertex connectivity, the domination number, the number of the spanning trees, etc.

35 pages

References in corpus (2)

• The Matrix-Forest Theorem and Measuring Relations in Small Social Groups
• A majorization bound for the eigenvalues of some graph Laplacians

Cited by in corpus (9)

• Robust Consensus in the Presence of Impulsive Channel Noise
• Accelerated Distributed Dual Averaging over Evolving Networks of Growing Connectivity
• Graph Coordinates and Conventional Neural Networks -- An Alternative for Graph Neural Networks
• Task-Feature Collaborative Learning with Application to Personalized Attribute Prediction
• Learning Personalized Attribute Preference via Multi-task AUC Optimization
• Persistent spectral graph
• Consensus dynamics on temporal hypergraphs
• Exploring Graph Classification Techniques Under Low Data Constraints: A Comprehensive Study
• A spectral bound for graph irregularity