The Laplacian eigenvalues of graphs: a survey

By Xiaodong Zhang. 2011

83 citations recorded by the source corpus.

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.

Subfields: Computational Theory and Mathematics, Geometry and Topology, Organic Chemistry

View Paper: https://www.semanticscholar.org/paper/4e10756e6c0920a89483c9b39d254f02e2dc21ed

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Theory and Mathematics

1. J. Shao
2. Shenglong Hu
3. Liqun Qi
4. Qun Wang
5. Yisheng Song
6. Chaoqian Li
7. Yaotang Li
8. Guanglu Zhou

In Geometry and Topology

1. Liqun Qi
2. J. Shao
3. Shenglong Hu
4. Qun Wang
5. Anirban Banerjee
6. Chaoqian Li
7. Yaotang Li

In Organic Chemistry

1. Shenglong Hu
2. Qun Wang
3. J. Shao
4. Liqun Qi

Citations in the corpus

• Regular Uniform Hypergraphs, $s$-Cycles, $s$-Paths and Their largest Laplacian H-Eigenvalues (2013, background): “The largest Laplacian eigenvalue of a graph plays an important role in spectral graph theory [1,17].”
• Cored Hypergraphs, Power Hypergraphs and Their Laplacian H-Eigenvalues (2013, background): “One classical result in spectral graph theory [2,29] is that the largest Laplacian eigenvalue of a graph is always less than or equal to the largest signless Laplacian eigenvalue, and when the graph is connected, equality holds if and only if the graph is bipartite.”