On a Lower Bound for the Laplacian Eigenvalues of a Graph

Greaves, Gary; Munemasa, Akihiro; Peng, Anni
November 2017
Graphs & Combinatorics;Nov2017, Vol. 33 Issue 6, p1509
Academic Journal
If $$\mu _m$$ and $$d_m$$ denote, respectively, the m-th largest Laplacian eigenvalue and the m-th largest vertex degree of a graph, then $$\mu _m \geqslant d_m-m+2$$ . This inequality was conjectured by Guo (Linear Multilinear Algebra 55:93-102, 2007) and proved by Brouwer and Haemers (Linear Algebra Appl 429:2131-2135, 2008). Brouwer and Haemers gave several examples of graphs achieving equality, but a complete characterisation was not given. In this paper we consider the problem of characterising graphs satisfying $$\mu _m = d_m-m+2$$ . In particular we give a full classification of graphs with $$\mu _m = d_m-m+2 \leqslant 1$$ .


Related Articles

  • On the sum of the two largest Laplacian eigenvalues of unicyclic graphs. Zheng, Yirong; Chang, An; Li, Jianxi // Journal of Inequalities & Applications;9/18/2015, Vol. 2015 Issue 1, p1 

    Let G be a simple graph and $S_{2}(G)$ be the sum of the two largest Laplacian eigenvalues of G. Guan et al. (J. Inequal. Appl. 2014:242, 2014) determined the largest value for $S_{2}(T)$ among all trees of order n. They also conjectured that among all connected graphs of order n with m ( $n...

  • SOME RESULTS FOR THE LAPLACIAN EIGENVALUES OF GRAPHS. Al-Saket, Amal // Advances & Applications in Discrete Mathematics;Oct2013, Vol. 12 Issue 2, p151 

    In this paper, we present bounds for Laplacian eigenvalues and the Laplacian spread of graphs by employing the Cauchy interlacing property and some known inequalities. Then we apply these bounds to some examples of graphs and make comparisons with some known bounds.

  • Faber-Krahn Inequalities for the Robin-Laplacian: A Free Discontinuity Approach. Bucur, Dorin; Giacomini, Alessandro // Archive for Rational Mechanics & Analysis;Nov2015, Vol. 218 Issue 2, p757 

    Isoperimetric inequalities for the principal eigenvalues of the Robin-Laplacian are interpreted as free discontinuity problems (of unusual type). We prove a full range of Faber-Krahn inequalities in a nonlinear setting and for non smooth domains, including the open case of the torsional...

  • Bounds for the Largest Laplacian Eigenvalue of Weighted Graphs. Sorgun, Sezer // International Journal of Combinatorics;2013, p1 

    Let G be weighted graphs, as the graphs where the edge weights are positive definite matrices. The Laplacian eigenvalues of a graph are the eigenvalues of Laplacian matrix of a graph G. We obtain two upper bounds for the largest Laplacian eigenvalue of weighted graphs and we compare these bounds...


    Let G be an undirected simple and connected graph with n vertices .n ≥ 3/ and m edges. Denote by μ1 ≥ μ2 ≥ ... ≥ μn-1 > μn = 0, γ1 ≥ γ2 ≥ ... ≥ γn, and ρ1 ≥ ρ2 ≥ ... ≥ ρn-1 > ρn = 0, respectively, the...

  • Some families of Laplacian inegral graphs. Lu, QIAO // Basic Sciences Journal of Textile Universities / Fangzhi Gaoxia;Dec2012, Vol. 25 Issue 4, p399 

    Let G be a simple graph of order n. Let A(G) be its adjacency matrix, and D(G) denotes the degree matrix of graph G. The Laplacian matrix of graph G is L(G) =D(G) -A(G). Graph G is called Laplacian integrai if the Laplacian eigenvaiues of graph G are ali integers. In this paper, some Laplacian...

  • Laplacian Energy of Binary Labeled Graph. Bhat, Pradeep G.; D'Souza, Sabitha; Nayak, Swati S. // International Journal of Mathematical Combinatorics;Jun2015, Vol. 2, p106 

    Let G be a binary labeled graph and Al (G) = (lij) be its label adjacency matrix. For a vertex vi, we define label degree as ... . In this paper, we define label Laplacian energy LEl (G). It depends on the underlying graph G and labels of the vertices. We compute label Laplacian spectrum of...

  • The New Class of Laplacian Integral Graphs. Lu shi-fang; Zou jin-yu // Advanced Materials Research;7/24/2014, Vol. 989-994, p2643 

    Graph G is Laplacian integral, if all the eigenvalues of its Laplacian matrix are integral. In this paper, we obtain that the Laplacian characteristic polynomials of graphs Kn-tk2 by calculation. Characterizes the new class of Laplacian integral graphs.

  • An upper bound on the largest signless Laplacian of an odd unicyclic graph. COLLAO, MACARENA; PIZARRO, PAMELA; ROJO, OSCAR // Proyecciones - Journal of Mathematics;Mar2012, Vol. 31 Issue 1, p39 

    We derive an upper bound on the largest signless Laplacian eigenvalue of an odd unicyclic graph. The bound is given in terms of the largest vertex degree and the largest height of the trees obtained removing the edges of the unique cycle in the graph.

  • Trees, unicyclic graphs and bicyclic graphs with exactly two Q-main eigenvalues. Chen, Lin; Huang, Qiong // Acta Mathematica Sinica;Nov2013, Vol. 29 Issue 11, p2193 

    The signless Laplacian matrix of a graph G is defined to be the sum of its adjacency matrix and degree diagonal matrix, and its eigenvalues are called Q-eigenvalues of G. A Q-eigenvalue of a graph G is called a Q-main eigenvalue if it has an eigenvector the sum of whose entries is not equal to...


Read the Article


Sorry, but this item is not currently available from your library.

Try another library?
Sign out of this library

Other Topics