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

  • 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...

  • 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 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.

  • Laplacian Energy of Certain Graphs. Sarasija, P. B.; Nageswari, P. // International Journal of Mathematical Combinatorics; 

    Let G be a graph with n vertices and m edges. Let µ1, µ2, …, µn be the eigenvalues of the Laplacian matrix of G. The Laplacian energy Due to image rights restrictions, multiple line equation(s) cannot be graphically displayed.. In this paper, we calculate the exact Laplacian...

  • 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...

  • Some further bounds for the Q-index of nested split graphs. Anđelić, M.; Fonseca, C.; Simić, S.; Tošić, D. // Journal of Mathematical Sciences;Apr2012, Vol. 182 Issue 2, p193 

    The Q-index of a simple graph is the largest eigenvalue of its signless Laplacian, or Q-matrix. In our previous paper [] we gave three lower and three upper bounds for the Q-index of nested split graphs, also known as threshold graphs. In this paper, we give another two upper bounds, which are...


Read the Article


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

Try another library?
Sign out of this library

Other Topics