Electronic Journal of Graph Theory and Applications 5 (2) (2017), 276–303

Bounds for the Laplacian spectral radius of graphs
Kamal Lochan Patra, Binod Kumar Sahoo
School of Mathematical Sciences
National Institute of Science Education and Research, Bhubaneswar (HBNI)
At/Po- Jatni, District- Khurda, Odisha - 752050, India.
klpatra@niser.ac.in, bksahoo@niser.ac.in

Abstract
This paper is a survey on the upper and lower bounds for the largest eigenvalue of the Laplacian
matrix, known as the Laplacian spectral radius, of a graph. The bounds are given as functions
of graph parameters like the number of vertices, the number of edges, degree sequence, average
2-degrees, diameter, covering number, domination number, independence number and other parameters.
Keywords: graph, Laplacian matrix, Laplacian spectral radius, upper bound, lower bound
Mathematics Subject Classification: 05C50
DOI: 10.5614/ejgta.2017.5.2.10

1. Introduction
All graphs in this paper are finite and simple. We refer to [2] for the unexplained graph theoretic
terminology used here. Let G = (V, E) be a graph with vertex set V = {v1 , v2 , · · · , vn } and edge
set E = {e1 , e2 , · · · , em }. Let A(G) denote the (0, 1)-adjacency matrix and D(G) denote the
diagonal matrix of the vertex degrees of G. Then the Laplacian matrix L(G) of G is defined by
L(G) := D(G) − A(G). Another way to define the Laplacian matrix is the following. Fix an
orientation of the edges of G, that is, for each ei ∈ E, choose one of its end vertices as the initial
vertex and the other end vertex as the terminal vertex. The oriented vertex-edge incidence matrix
Received: 13 December 2015,

Revised: 15 August 2017,

276

Accepted: 2 September 2017.

www.ejgta.org

Bounds for the Laplacian spectral radius of graphs

|

K.L. Patra and B.K. Sahoo

of G is the n × m matrix B(G) = (bij ), where

 1 if vi is the initial vertex of ej
−1 if vi is the terminal vertex of ej
bij =

0 otherwise.
Then the n × n matrix B(G)B(G)T is independent of the orientation given to the edges of G
and L(G) = B(G)B(G)T . Kirchhoff proved a result, known as the “matrix-tree theorem”, that
relates the Laplacian matrix of a graph with the number of spanning trees in it. Since the 1970s
several authors from different disciplines have studied Laplacian matrices of graphs. The study
of Laplacian spectrum and its relation with the structural properties of graphs has been one of the
most attracting features of the subject.
Clearly, L(G) is a real, symmetric and positive semi-definite matrix. So all its eigenvalues are
real and non-negative. Since the sum of the entries in each row of L(G) is zero, the all one vector
e = [1, · · · , 1]T is an eigenvector of L(G) corresponding to the smallest eigenvalue 0, in particular,
L(G) is singular. We refer the reader to [13, 37, 33, 34] and the references therein for more on
the Laplacian matrix and its eigenvalues. The largest eigenvalue of L(G) is called the Laplacian
spectral radius of G and we denote it by λ(G). The Laplacian matrix L(G) of G depends on the
ordering of its vertices. However, Laplacian matrices afforded by different vertex orderings of the
same graph are permutation similar. So two isomorphic graphs have the same Laplacian spectrum.
The Laplacian matrix L(G) of G is irreducible if and only if G is connected. If G is disconnected, then L(G) is similar to a block diagonal matrix, where each block is the Laplacian matrix
of some connected component of G. So, if G1 , G2 , · · · , Gk are the connected components of G,
then λ(G) = max{λ(Gi ) : 1 ≤ i ≤ k}. Let W be the set of all unit vectors in Rn , that is,
W = {X ∈ Rn | X T X = 1}. By Rayleigh-Ritz theorem [21, p.176], we have
λ(G) = max X T L(G)X.
X∈W

If X is a unit eigenvector of L(G) corresponding to λ(G), then
X
λ(G) = X T L(G)X =
(xi − xj )2 ,
vi vj ∈E

where X T = [x1 , x2 , · · · , xn ]. Here for two distinct adjacent vertices vi and vj , vi vj ∈ E denotes
the corresponding edge.
The second smallest eigenvalue of L(G), denoted by a(G), is called the algebraic connectivity
of G by Fiedler [11] and has received a good deal of attention so far. From the Perron-Frobenius
theorem applied to the matrix (n − 1)I − L(G), it follows that a(G) is positive if and only if G is
connected. Fiedler proved that λ(G) = n − a(G), where G denotes the complement graph of G
[11, 3.7(1◦ )]). Thus information on the Laplacian spectral radius of a graph can be obtained from
the algebraic connectivity of the complement graph of it.
Several researchers have extensively studied the Laplacian spectral radius of graphs and obtained various bounds for it with respect to varying graph parameters and whenever possible,
277

www.ejgta.org

Bounds for the Laplacian spectral radius of graphs

|

K.L. Patra and B.K. Sahoo

the corresponding extremal graphs have been characterized. Information on the Laplacian spectral radius of a graph is also useful in several other areas like: combinatorial optimization (see
[38, 39, 42]), communication network (see [48]), theoretical chemistry (see [18, 19]) etc.
Starting from the very first result, this paper is a survey on the upper and lower bounds of the
Laplacian spectral radius as a function of graph parameters like the number of vertices, the number of edges, degree sequence, average 2-degrees, diameter, matching number, covering number,
domination number, independence number etc. We have organized the paper as follows: Sections
2 and 3 are dedicated to the upper bounds, and Section 4 is for the lower bounds.
Along with other results, the following are the three basic lemmas which are frequently used in
the proof of many of the bounds. Recall that if A is a nonnegative square matrix, then the spectral
radius of A is an eigenvalue of A [36, Theorem 4.2, p.14]. The following lemma says that the
largest eigenvalue of A is bounded by the minimal and maximal row sums of A [36, Theorem 1.1,
p.24].
Lemma 1.1. [36] Let A be a k × k nonnegative matrix with maximal eigenvalue η and row sums
r1 , r2 , · · · , rk . Then
r ≤ η ≤ R,
where r = min{ri : 1 ≤ i ≤ k} and R = max{ri : 1 ≤ i ≤ k}. If A is irreducible, then equality
can hold on either side of the above inequality if and only if all row sums of A are equal.
The matrix Q(G) := D(G) + A(G) is called the signless Laplacian matrix of G. Let ρ(G)
denote the largest eigenvalue of Q(G). The following relation between λ(G) and ρ(G) is proved
in [60, Lemma 2.1], also see [41, Theorem 2.3]. We note that Q(G) and L(G) are similar for a
bipartite graph G.
Lemma 1.2. [60] Let G be a graph. Then λ(G) ≤ ρ(G). If G is a bipartite graph, then equality
holds. Conversely, if G is connected and equality holds, then G is a bipartite graph.
The line graph LG of G is the graph whose vertices correspond to the edges of G, with two
distinct vertices of LG are adjacent if and only if the corresponding edges in G have a vertex in
common. If G has no isolated vertex, then LG is connected if and only if G is connected. The
vertex-edge incidence matrix of G is the n × m matrix R(G) = (rij ), where

1 if vi is incident with ej
rij =
0 otherwise.
Then R(G)R(G)T = D(G) + A(G) = Q(G) and R(G)T R(G) = 2Im + A(LG ). So, the largest
eigenvalue ρ(G) of Q(G) is equal to 2 + µ(LG ), where µ(LG ) denotes the largest eigenvalue of
the adjacency matrix A(LG ) of LG . Hence Lemma 1.2 implies the following (also see [47, Lemma
2]).
Lemma 1.3. Let G be a graph and LG be its line graph. If µ(LG ) is the largest eigenvalue of
A(LG ), then λ(G) ≤ 2 + µ(LG ). If G is a bipartite graph, then equality holds. Conversely, if G is
connected and equality holds, then G is a bipartite graph.
278

www.ejgta.org

Bounds for the Laplacian spectral radius of graphs

|

K.L. Patra and B.K. Sahoo

We observe that many results available in the literature on the bounds of the Laplacian spectral
radius of a graph are stated stipulating ‘connectedness’ of the graph a priori. However, most of
the given proofs could work well for disconnected graphs also and if necessary, with assumptions
like the graph has at least one edge or has no isolated vertex. We find that while listing the above
lemmas as preliminary results, connectedness of the graph is assumed in Lemmas 1.2, 1.3, and
irreducibility of the matrix is assumed in Lemma 1.1 from the beginning itself, which forces to
state the new bounds for connected graphs only. Confinement to connected graphs only simplifies
the study of the equality case of a given bound, though equality may hold good for some less
obvious disconnected graphs as well (for example, see the equality case of the bound (20) in the
next section).
We have tried here to state many of the bounds without restricting to connected graphs only,
unless it is necessary. However, connectedness is generally assumed to characterize the equality
cases. Note that if G is a graph with an isolated vertex v, then λ(G) = λ(G \ {v}). Therefore, we
assume throughout that all graphs are without any isolated vertices.
2. Upper Bounds
Let G = (V, E) be a graph with vertex set V = {v1 , v2 , · · · , vn } and edge set E. For each
vertex vi ∈ V , we denote by Ni the neighborhood of vi , that is, the set of vertices of G adjacent to
vi , and by di = d(vi ) the degree of the vertex vi (we may write dG (vi ) if more than one graph is
under consideration). So di = |Ni |. The minimal and maximal vertex degrees of G are denoted by
δ = δ(G) and ∆ = ∆(G), respectively. For each 1 ≤ i ≤ n, we denote by mi the average of the
degrees of the vertices adjacent to vi , that is,


X
1
dj  .
mi = 
di v ∈N
j

i

The integer mi is called the average 2-degree of the vertex vi . The degree sequence of G is
the non-increasing sequence of its vertex degrees. Whenever necessary, the vertices of G can be
renumbered so that di ≥ di+1 for 1 ≤ i ≤ n − 1. In that case, we say that G has degree sequence
d1 ≥ d2 ≥ · · · ≥ dn . Note that δ = dn ≥ 1, since we are considering graphs without isolated
vertices.
A bipartite graph G = (V, E) with bipartition V = V1 ∪ V2 is said to be semiregular if the
vertices in each Vi have the same degree for i = 1, 2. Here regular bipartite graphs are also
considered to be semiregular.
The first two upper bounds for the Laplacian spectral radius of a graph were given by Fiedler
in 1973 in terms of the number of vertices and the maximal vertex degree.
Theorem 2.1. [11] Let G be a graph with n vertices and maximal vertex degree ∆. Then
λ(G) ≤ n;

(1)

λ(G) ≤ 2∆.

(2)

and

279

www.ejgta.org

Bounds for the Laplacian spectral radius of graphs

|

K.L. Patra and B.K. Sahoo

Equality holds in (1) if and only if G is disconnected. If G is connected, then equality holds in (2)
if and only if G is a regular bipartite graph.
The bound (1) follows from the relation λ(G) = n − a(G), also see [1, Theorem 1]. The bound
(2) was proved in [11, 3.7(5◦ )]. The following bound (3) by Anderson and Morley in [1, Theorem
2] is an improvement of (2).
Theorem 2.2. [1] Let G = (V, E) be a graph with V = {v1 , v2 , · · · , vn } and vertex degrees di .
Then
λ(G) ≤ max {di + dj : vi vj ∈ E}.
(3)
If G is connected, then equality holds if and only if G is a semiregular bipartite graph.
The equality case of (2) for connected graphs is a consequence of Theorem 2.2. The following
bound (4) was given by Li and Zhang [25, Theorem 3.2] in terms of the largest three vertex degrees.
Theorem 2.3. [25] Let G = (V, E) be a graph with degree sequence d1 ≥ d2 ≥ · · · ≥ dn . Then
p
(4)
λ(G) ≤ 2 + (d1 + d2 − 2)(d1 + d3 − 2).
If G is connected, then equality holds if and only if G is either a regular bipartite graph or, a path
with three or four vertices.
The bounds (3) and (4) are not comparable in general, see the examples given in [35, p.34].
However, the following bound (5) mentioned in [25, Remark 1] is better than both (3) and (4). A
different proof of (5) was given by Pan in [41, Theorem 2.9], where the connected graphs achieving
this bound were determined.
Theorem 2.4. [25, 41] Let G = (V, E) be a graph with V = {v1 , v2 , · · · , vn } and vertex degrees
di . Let a = max {di + dj | vi vj ∈ E} and let vk vh ∈ E be such that a = dk + dh . Define
b = max {di + dj | vi vj ∈ E \ {vk vh }}. Then
p
(5)
λ(G) ≤ 2 + (a − 2)(b − 2).
If G is connected, then equality holds if and only if G is a semiregular bipartite graph or a path
with four vertices.
The following bound given by Zhang and Li [59, Corollary 4.4] is a further improvement of
(5).
Theorem 2.5. [59] Let G = (V, E) be a graph with V = {v1 , v2 , · · · , vn } and vertex degrees di .
Then
q

λ(G) ≤ 2 + max

(di + dj − 2)(di + dk − 2) ,

(6)

where the maximum is taken over all edges vi vj , vi vk ∈ E with vj 6= vk . Further, if G is connected,
then equality holds if and only if G is a semiregular bipartite graph or a path with four vertices.
280

www.ejgta.org

Bounds for the Laplacian spectral radius of graphs

|

K.L. Patra and B.K. Sahoo

The following bound (7) was given by Merris in [35, p.34] which improves (3). An alternative
proof of (7) was given by Pan in [41, Theorem 2.4], where the extremal connected graphs were
also characterized.
Theorem 2.6. [35, 41] Let G = (V, E) be a graph with V = {v1 , v2 , · · · , vn }, vertex degrees di
and average 2-degrees mi . Then
λ(G) ≤ max {di + mi | vi ∈ V }.

(7)

If G is connected, then equality holds if and only if G is a semiregular bipartite graph.
Merris has given examples in [35, p.34] showing that the bounds (7) and (5) are not comparable
in general. The following bound (8) given by Li and Zhang in [26, Theorem 3] improves (7).
Another proof of (8) was given by Pan in [41, Theorem 2.10], where necessary and sufficient
conditions were provided for the equality case (also see [59, Theorem 4.5]).
Theorem 2.7. [26, 41] Let G = (V, E) be a graph with V = {v1 , v2 , · · · , vn }, vertex degrees di
and average 2-degrees mi . Then


di (di + mi ) + dj (dj + mj )
: vi vj ∈ E .
(8)
λ(G) ≤ max
di + dj
If G is connected, then equality holds if and only if G is a semiregular bipartite graph.
The following bound (9) given by Pan in [41, Theorem 2.11] is a further improvement of (8).
Though connectedness of the graph is assumed in [41, Theorem 2.11], the given proof works for
any graph.
Theorem 2.8. [41] Let G = (V, E) be a graph with V = {v1 , v2 , · · · , vn }, vertex degrees di and
average 2-degrees mi . Define


di (di + mi ) + dj (dj + mj )
t = max
: vi vj ∈ E .
di + dj
h (dh +mh )
Let vk vh ∈ E be such that t = dk (dk +mdkk)+d
. Define
+dh


di (di + mi ) + dj (dj + mj )
s = max
: vi vj ∈ E \ {vk vh } .
di + dj

Then
λ(G) ≤ 2 +

p

(t − 2)(s − 2).

(9)

If G is connected, then equality holds if and only if G is a semiregular bipartite graph or a path
with four vertices.
For certain graphs, some of the above bounds could give results which are greater than the
number of vertices and so they become trivial bounds comparing to (1). Addressing this problem,
Rojo et al. gave the following bound (10) in [44, Theorem 4] whose value never exceeds the
number of vertices.
281

www.ejgta.org

Bounds for the Laplacian spectral radius of graphs

|

K.L. Patra and B.K. Sahoo

Theorem 2.9. [44] Let G = (V, E) be a graph with V = {v1 , v2 , · · · , vn } and vertex degrees di .
Then
λ(G) ≤ max {di + dj − |Ni ∩ Nj | : 1 ≤ i 6= j ≤ n}.
(10)
This upper bound for λ(G) is always less than or equal to n.
Note that the maximum in (10) is taken over all pairs of distinct vertices, a reason for which the
bounds (3) and (10) are not comparable in general (see the example given in [5, p.271]). Restricting
the maximum over pairs of adjacent vertices only, Das in [5, Theorem 2.1] gave the following
bound (11) which is always better than (3) and (10). The result for equality case of (11) was
conjectured by him in [7, Problem 2.17] and was proved by Yu et al. in [55, Theorem 2.2].
To state the equality case of (11), we define the following: Let H = (V, E) be a semiregular bipartite graph with bipartition V = V1 ∪ V2 and let H + = (V, E + ) be the supergraph of
H adding new edges by joining those pairs of vertices in V1 (respectively, in V2 ) which have
the same set of neighbors in V2 (respectively, in V1 ), if such pairs exist. Define H+ = {H + :
H is a semiregular bipartite graph}.
Theorem 2.10. [5, 55] Let G = (V, E) be a graph with V = {v1 , v2 , · · · , vn } and vertex degrees
di . Then
λ(G) ≤ max {di + dj − |Ni ∩ Nj | : vi vj ∈ E} .
(11)
If G is connected, then equality holds if and only if G ∈ H+ .
The following bound (12) was given by Rojo et al. in [45, Corollary 16] based on vertex
degrees and the number of vertices.
Theorem 2.11. [45] Let G = (V, E) be a graph with V = {v1 , v2 , · · · , vn } and vertex degrees di .
Then
! r
n
X
n−2
1
f (G),
(12)
di +
λ(G) ≤
n − 1 i=1
n−1
 n 2
n
P
P
1
where f (G) = di (di + 1) − n−1
di .
i=1

i=1

In [58, Lemma 3.2], Zhang and Li gave an upper bound for the sum of squares of the vertex
degrees of a graph in terms of the number of vertices and the number of edges. Using this as a tool,
the following bound (13) was obtained in [58, Theorem 3.3] in terms of the number of vertices and
edges of a graph.
Theorem 2.12. [58] Let G = (V, E) be a graph with n vertices and m edges. Let M be the
minimum of m2 (n − 4) + 2m(n − 1) and 2mn(n − 1) − 4m2 . Then

p
1 
λ(G) ≤
2m + (n − 2)M .
n−1

(13)

If G is connected, then equality holds if and only if G is the complete graph Kn or the star graph
K1,n−1 .
282

www.ejgta.org

Bounds for the Laplacian spectral radius of graphs

|

K.L. Patra and B.K. Sahoo

In [10, Theorem 1], de Caen had given another upper bound for the sum of squares of the vertex
degrees of a graph in terms of the number of vertices and the number of edges. Using de Caen’s
inequality as a tool, Li and Pan proved in [22, Theorem 3.1] the following bound (14) in terms
of the number of vertices and edges (their proof would work for any graph) and characterized the
connected graphs for which equality is achieved.
Theorem 2.13. [22] Let G = (V, E) be a graph with n vertices and m edges. Then
p
2m + (n − 2)m(n(n − 1) − 2m)
.
λ(G) ≤
n−1

(14)

If G is connected, then equality holds if and only if G is the star graph or the complete graph Kn .
For connected graphs, the bound (14) can be obtained without using de Caen’s inequality, see
the discussion in [4, p.1963]. It can be seen that when m ≥ n−1, in particular when G is connected,
the bound (14) is an improvement of (13). We note that, for connected graphs, the bounds (13)
and (14) always give values which are greater than or equal to the number n of vertices, see [7,
Theorem 2.18].
In [22, Theorems 3.2, 3.3], Li and Pan proved the following two bounds (15) and (16), also
see [7, Corollaries 2.10, 2.11]. In [46, Theorem 3.1], Shi gave a different proof of (16) and then
derived the bound (15) in [46, Corollary 3.1] as an application of (16). From the proof of [46,
Corollary 3.1], it follows that (16) is better than (15).
Theorem 2.14. [22, 46] Let G = (V, E) be a graph with n vertices, m edges, vertex degrees di ,
average 2-degrees mi , maximal vertex degree ∆ and minimal vertex degree δ. Then
p
(15)
λ(G) ≤ 2∆2 + 4m + 2∆(δ − 1) − 2δ(n − 1);
and

o
np
2di (di + mi ) : vi ∈ V .
λ(G) ≤ max

(16)

If G is connected, then equality holds in each of (15) and (16) if and only if G is a regular bipartite
graph.
Remark 2.1. The equality case of (16) in [46, Theorem 3.1] was characterized as the following: If
G is connected, then equality holds in (16) if and only if G is bipartite and the value d2i + di mi is
independent of the vertex vi ∈ V . It follows that a bipartite graph is regular if and only if d2i + di mi
is the same for all i. A direct proof of this fact can be given following an argument similar to the
proof of Proposition 2.1 below (also see Remark 2.2 after Theorem 2.25).
The following bound (17) given by Zhang and Luo in [61, Theorem 3.2] is an improvement
of (15). They stated this bound for connected mixed graphs but their proof works for any mixed
graph. Since the Laplacian matrix of a simple graph is consistent with the Laplacian matrix of
the associted mixed graph in which all edges are oriented, so their proof remains valid for simple
graphs also.

283

www.ejgta.org

Bounds for the Laplacian spectral radius of graphs

|

K.L. Patra and B.K. Sahoo

Theorem 2.15. [61] Let G be a graph with n vertices, m edges, maximal vertex degree ∆ and
minimal vertex degree δ. Then
p
(17)
λ(G) ≤ ∆ + 2m + ∆(δ − 1) − δ(n − 1).
If G is connected, then equality holds if and only if G is a regular bipartite graph.
The following bound (18), which is an improvement of (7), was given by Zhang and Luo in
[61, Theorem 3.4] more generally for mixed graphs. The same bound was obtained by Das in [7,
Theorem 2.14] (his proof would work for any graph without isolated vertices).
Theorem 2.16. [7, 61] Let G be a graph with V = {v1 , v2 , · · · , vn }, vertex degrees di and average
2-degrees mi . Then
 


q
1
2
di + dj + (di − dj ) + 4mi mj : vi vj ∈ E .
λ(G) ≤ max
(18)
2
If G is connected, then equality holds if and only if G is a semiregular bipartite graph.
In [5, Theorem 2.5], Das proved the following bound (19) which improves (16). The connected
graphs achieving this bound were characterized by him in [7, Theorem 2.9].
Theorem 2.17. [5, 7] Let G = (V, E) be a graph with V != {v1 , v2 , · · · , vn } and vertex degrees
P
(dj − |Ni ∩ Nj |) . Then
di . For 1 ≤ i ≤ n, define m0i = d1i
vj ∈Ni

np
o
0
λ(G) ≤ max
2di (di + mi ) : 1 ≤ i ≤ n .

(19)

If G is connected, then equality holds if and only if G is a regular bipartite graph.
The following bound (20) was given by Shu et al. for connected graphs based on the degree
sequence [47, Theorem 1]. However, their characterization of the connected graphs for the equality
case was incomplete as pointed out by K. C. Das in [3, p.283]. In [62, Theorem 3], Zhou and
Cho obtained the same bound and prescribed the conditions for equality case for any graph (not
necessarily connected).
Theorem 2.18. [47, 62] Let G be a graph with n vertices and degree sequence d1 ≥ d2 ≥ · · · ≥
dn ≥ 1. Then
v
u
2 X
n
1 u
1
λ(G) ≤ dn + + t dn −
+
di (di − dn ).
(20)
2
2
i=1
Further, equality holds if and only if G is a regular graph with at least one bipartite component,
or G is the disjoint union of a star graph and (possibly) some K2 ’s.
The following two bounds were given by Li and Pan in [23, Theorems 3.1, 3.2], also see [28,
Theorem 4] for the bound (22).
284

www.ejgta.org

Bounds for the Laplacian spectral radius of graphs

|

K.L. Patra and B.K. Sahoo

Theorem 2.19. [28, 23] Let G be a graph with n vertices, m edges, maximal vertex degree ∆ and
minimal vertex degree δ. Then the following hold:

p
1
2
2
δ − 1 + (δ − 1) + 8(∆ + 2m − δ(n − 1)) ;
λ(G) ≤
(21)
2

p
1
2
λ(G) ≤
(22)
(∆ + δ − 1) + (∆ + δ − 1) + 8(2m − δ(n − 1)) .
2
If G is connected, then equality holds in both cases if and only if G is a regular bipartite graph.
The next three bounds (23) − (25) were given by Zhang in [56, Theorems 1.1, 1.2, 3.2] for
connected graphs (though the given proofs work for any graph). The bound (23) is an improvement
of (16). Using the inequality in [17, Lemma 2.1], it can be seen that (23) is better than (17), and
(24) is better than (15). Based on the observation made by Wang in [51, Remark 1], the statement
in the equality case of (23) is modified from its original one.
Theorem 2.20. [56] Let G = (V, E) be a graph with V = {v1 , v2 , · · · , vn }, vertex degrees di and
average 2-degrees mi . Then the following hold:
n
o
p
(23)
λ(G) ≤ max di + di mi : vi ∈ V ;

q
λ(G) ≤ max
di (di + mi ) + dj (dj + mj ) : vi vj ∈ E ;

(24)



q
λ(G) ≤ max 2 + di (di + mi − 4) + dj (dj + mj − 4) + 4 : vi vj ∈ E .

(25)

If G is connected, then the following hold:
(i) Equality in (23) holds if and only if G is a regular bipartite graph.
(ii) Equality in (24) holds if and only if G is a semiregular bipartite graph.
(iii) Equality in (25) holds if and only if G is a semiregular bipartite grpagh or a path on 4
vertices.
The following upper bound (26) was given by Guo in [15, Theorem 1].
Theorem 2.21. [15] Let G = (V, E) be a graph with V = {v1 , v2 , · · · , vn } and vertex degrees di .
Then
(
)
p
di + d2i + 8di m0i
λ(G) ≤ max
: vi ∈ V ,
(26)
2
where m0i are defined as in Theorem 2.17. Further, if G is connected, then equality holds if and
only if G is a regular bipartite graph.
The following four bounds (27) − (30) were given by Das in [9, Theorems 5.1, 5.4, 5.7].

285

www.ejgta.org

Bounds for the Laplacian spectral radius of graphs

|

K.L. Patra and B.K. Sahoo

Theorem 2.22. [9] Let G be a graph with n vertices and degree sequence d1 ≥ d2 ≥ · · · ≥ dn ≥ 1.
Then, for dn = 1,
v
u n
uX
di (di − 1) − d1 + 1;
(27)
λ(G) ≤ 2 + t
i=1

and for dn ≥ 2,
v
u n
uX
λ(G) ≤ 2 + t
di (di − 1) −
i=1

!
n
1X
di − 1 (2dn − 2) + (2dn − 3)(2d1 − 2).
2 i=1

(28)

If G is connected, then equality holds in (27) if and only if G is a star graph, and equality holds in
(28) if and only if G a regular bipartite graph.
Theorem 2.23. [9] Let G be a graph with n vertices, m edges, maximal degree ∆, minimal degree
δ and average 2-degrees mi . Set θ = max{mi : 1 ≤ i ≤ n}. Then the following hold:
s


!
2m
1
n−2
∆
λ(G) ≤
∆ + ∆2 + 4θ
+
∆ + (∆ − δ) 1 −
;
(29)
2
n−1 n−1
n−1


2m
n−2
∆
λ(G) ≤
+
∆ + (∆ − δ) 1 −
.
n−1 n−1
n−1

(30)

If G is connected, then the following hold:
(i) Equality in (29) holds if and only if G is a regular bipartite graph.
(ii) Equality in (30) holds if and only if G is a star graph or a regular bipartite graph.
In [51, Theorems 2.6, 2.7, 2.10], the following three bounds (31) − (33) were obtained by
Wang for connected graphs (though the given proofs work for any graph). An alternative proof of
the bound (31) was given by Zhu in [63, Theorem 3.7].
Theorem 2.24. [51, 63] Let G = (V, E) be a graph with V = {v1 , v2 , · · · , vn }, m edges, vertex
degrees di and average 2-degrees mi . Then the following hold.


 
q
p
1
2
(31)
di + dj + (di − dj ) + 4 di dj mi mj : vi vj ∈ E ;
λ(G) ≤ max
2
s

 (d + d − 2)(d2 m + d2 m − 2d d )

i
j
i
i j
i
j j
λ(G) ≤ 2 + max
: vi vj ∈ E ;
(32)


di dj
λ(G) ≤ 2 +

sX

d2i − 2m − (m − 1)r0 + (r0 − 1)r1 ;

(33)

vi ∈V

where r0 = min {di + dj − 2 | vi vj ∈ E} and r1 = max {di + dj − 2 | vi vj ∈ E} in the last
inequality. If G is connected, then the following hold:
286

www.ejgta.org

Bounds for the Laplacian spectral radius of graphs

|

K.L. Patra and B.K. Sahoo

(i) Equality in (31) holds if and only if G is a semiregular bipartite graph.
(ii) Equality in each of (32) and (33) holds if and only if G is a semiregular bipartite graph or a
path with four vertices.
The following bound (34) given by Guo in [16, Theorem 2.2] is always better than the bound
(23). In fact, Guo proved more general results in [16, Theorem 2.1] (for which connectedness of
the graph is not necessary), as consequences of which the bounds (3), (7), (18), (23) and (34) could
be obtained.
Theorem 2.25. [16] Let G = (V, E) be a graph with V = {v1 , v2 , · · · , vn } and vertex degrees di .
Then




1 X p
dj : vi ∈ V .
(34)
λ(G) ≤ max di + √


di v v ∈E
i j

If G is connected, then equality holds if and only if G is a regular bipartite graph.
Remark 2.2. The equality case of (34) in [16, Theorem 2.2] was characterized as the following:
If G is connected,
P p then equality holds in (34) if and only if G is bipartite and the value ai =
dj is independent of the vertex vi ∈ V . We note that, for a bipartite graph, the
di + √1di
vi vj ∈E

condition that the values ai are the same for all i is equivalent to that the graph is regular. This
follows from the following proposition.
Proposition 2.1. Let G = (V, E) be a bipartite graph. Define ay = d(y) + √ 1

P p
d(w) for

d(y) yw∈E

each vertex y ∈ V . Then G is regular if and only if the values ay are the same for all y ∈ V .
Proof. If G is regular, then clearly ay is independent of the vertex y. Conversely, assume that ay is
the same for all y ∈ V . We show that G is regular.
Let V = X ∪ Y be a bipartition of V . Let u ∈ V be a vertex of maximal degree. Without loss
of generality, we may assume that u ∈ X. Let v ∈ Y be a vertex of minimal degree among all the
vertices in Y . Then d(u) ≥ d(v). Now
Xp
p
p
1
1
d(w) ≥ d(u) + p
(d(u) d(v)) = d(u) + d(u)d(v);
au = d(u) + p
d(u) uw∈E
d(u)
and
p
p
1 Xp
1
av = d(v) + p
d(w) ≤ d(v) + p
(d(v) d(u)) = d(v) + d(v)d(u).
d(v) vw∈E
d(v)
p
p
Since au = av , we get d(u) + d(u)d(v) ≤ d(v) + d(v)d(u) and this gives d(u) ≤ d(v). So
d(u) = d(v). It follows that all vertices in Y have the same degree and equal to d(u). Now let
x ∈ X. We have d(x) ≤ d(u) and
Xp
p
p
1
1
ax = d(x) + p
d(w) = d(x) + p
(d(x) d(u)) = d(x) + d(x)d(u).
d(x) xw∈E
d(x)
287

www.ejgta.org

Bounds for the Laplacian spectral radius of graphs

|

K.L. Patra and B.K. Sahoo

Then
2d(u) = au = ax = d(x) +

p
d(x)d(u) ≤ d(x) + d(u),

which gives d(u) ≤ d(x). So d(x) = d(u). Thus any two vertices in X have the same degree and
equal to d(u). Hence G is regular.
The following bound (35) was given by Yu in [53, Theorem 2.6] in terms of the degree sequence
of the line graph of a given graph. This bound is better than (5).
Theorem 2.26. [53] Let G be a graph with m edges and let t1 ≥ t2 ≥ · · · ≥ tm be the degree
sequence of the line graph of G. Then
)
(
p
ti + 3 + (ti + 1)2 + 4(i − 1)(t1 − ti )
.
(35)
λ(G) ≤ min
1≤i≤m
2
If G is connected, then equality holds if and only if G is a semiregular bipartite graph or G ' P2k,k ,
where P2k,k is the graph obtained from a path P2 on two vertices by adjoining k vertices to each
vertex of P2 .
In [63], the following bounds (36) − (41) were given by Zhu. The bound (41) is better than
(8), and (40) is better than (36).
Theorem 2.27. [63] Let G = (V, E) be a graph with V = {v1 , v2 , · · · , vn }, vertex degrees di and
average 2-degrees mi . Then the following hold.


mj
mi
+ dj
: vi vj ∈ E ;
(36)
λ(G) ≤ max di
dj
di
 r

r
mi
mj
λ(G) ≤ max di
+ dj
: vi vj ∈ E ;
(37)
dj
di
( √
)
p
di di + mi + dj dj + mj
p
λ(G) ≤ max
: vi vj ∈ E ;
(38)
di + dj
( √
)
p
√
√
di ( di + mi ) + dj ( dj + mj )
p
λ(G) ≤ max
: vi vj ∈ E ;
(39)
√
di + dj
n
o
p
λ(G) ≤ max 2 + (T (i, j) − 2)(T (i, k) − 2) : vi vj , vi vk ∈ E, vj 6= vk ;
(40)


 d (d + m ) + d (d + m )

X
2
i i
i
j j
j
λ(G) ≤ max
−
dk : vi vj ∈ E ;
(41)


di + dj
di + dj
vk ∈Ni ∩Nj

where T (s, t) = ddst ms + ddst mt in the inequality (40).

288

www.ejgta.org

Bounds for the Laplacian spectral radius of graphs

|

K.L. Patra and B.K. Sahoo

In fact, Zhu proved three general results [63, (2.1), (2.5), (2.6)] from which the above bounds
(36) − (41) are derived as consequences. The bounds (3), (5), (9) and (11) could also be obtained
as consequences of these general results.
In [52, Theorems 2.7, 2.8, 2.9], the following three bounds (42) − (44) were given by Wang
et al. and the connected graphs achieving these bounds were characterized. The bound (42) is an
improvement of (32).
Theorem 2.28. [52] Let G = (V, E) be a graph with V = {v1 , v2 , · · · , vn }, vertex degrees di and
average 2-degrees mi . Define
o
nq
(di + dj − 2)(d2i mi + d2j mj − 2di dj )/di dj : vi vj ∈ E
a = max
and
b = max

nq

o
(di + dj − 2)(d2i mi + d2j mj − 2di dj )/di dj : vi vj ∈ E \ {vk vh } ,

where a is attained by some edge vk vh ∈ E. Then the following hold:
√
λ(G) ≤ 2 + ab;


√
di (mi + mi )
√
λ(G) ≤ max di +
: vi ∈ V ;
di + di


di (di + mi ) + dj (dj + mj ) − 2(4i + 4j )
: vi vj ∈ E ;
λ(G) ≤ max
di + dj − |Ni ∩ Nj |

(42)
(43)
(44)

where 4k denotes the number of triangles associated with the vertex vk ∈ V . If G is connected,
then the following hold:
(i) Equality in (42) holds if and only if G is a semiregular bipartite graph or a path with four
vertices.
(ii) Equality in (43) holds if and only if G is a regular bipartite graph.
(iii) Equality in (44) holds if and only if G is a semiregular bipartite graph.
Recall that a clique in a graph G is a set of pairwise adjacent vertices. The clique number of
G, denoted by ω(G), is the maximum size of a clique in G. The next upper bound involving clique
number was given by Lu et al. in [30, Theorem 2.5].
Theorem 2.29. [30] Let G be a graph with n vertices, m edges, maximum degree ∆ and clique
number ω = ω(G). Then
s


1
λ(G) ≤ ∆ + 2m 1 −
.
(45)
ω
3. Upper Bounds for Special Classes of Graphs
In this section, we survey the results known for the upper bounds of the Laplacian spectral
radius of some special classes of graphs: Trees, Non-regular graphs, Triangular graphs, Trianglefree graphs, Maximal planner graphs and Bipartite graphs.
289

www.ejgta.org

Bounds for the Laplacian spectral radius of graphs

|

K.L. Patra and B.K. Sahoo

3.1. Trees
For a tree, Stevanović gave the following strict upper bound (46) in [49, Theorem 1] in terms
of the maximal vertex degree.
Theorem 3.1. [49] Let T be a tree with maximal vertex degree ∆. Then
√
λ(T ) < ∆ + 2 ∆ − 1.

(46)

We denote by d(u, v) the distance between two vertices u and v in a graph. The following
strict upper bound (47) given by Rojo in [43, Theorem 3] improves the bound (46) if σ1 < ∆, the
maximal vertex degree of the tree.
Theorem 3.2. [43] Let T be a tree with maximal vertex degree ∆ and u be a vertex of T of degree
d(u) = ∆. Let k − 1 be the maximal distance from u to any vertex of T . For j = 1, · · · , k − 2,
define σj = max {d(v) : d(u, v) = j}. Then


√
√
p
p
√
σj − 1 + σj + σj−1 − 1 , σ1 − 1 + σ1 + ∆, ∆ + ∆ . (47)
λ(T ) < max
max
2≤j≤k−2

Let G be a graph with edge set E. Two distinct edges in E are said to be independent if they are
not incident with a common vertex of G. A subset Y of E is called a matching of G if the edges in
Y are pairwise independent. The matching number of G, denoted by β(G), is the maximum size
of a matching of G.
Guo in [14, Theorem 1] proved the following upper bound (48) for the Laplacian spectral radius
of a tree relating to its matching number.
Theorem 3.3. [14] Let T be a tree with n vertices and matching number β = β(T ). Let κ be the
largest root of the equation x3 − (n − β + 4)x2 + (3(n − β) + 4)x − n = 0. Then
λ(T ) ≤ κ,

(48)

and equality holds if and only if T is the tree obtained from the star graph K1,n−β by adding
pendant edges to β − 1 of the n − β pendant vertices of K1,n−β .
Note that the tree obtained from K1,n−β in the equality case of (48) is well-defined, since
β(T1 ) ≤ bn/2c for any tree T1 with n vertices.
Let G be a graph with vertex set V . A subset U of V is called an independent set of G if no
two vertices of U are adjacent in G. The independence number of G, denoted by α(G), is the
maximum size of an independent set of G.
In the sprit of Theorem 3.3, Zhang proved in [57, Theorem 2.6, Lemma 2.7] the following
upper bound (49) for a tree relating to its independence number.
Theorem 3.4. [57] Let T be a tree with n vertices and independence number α = α(T ). Let ξ be
the largest root of the equation x3 − (α + 4)x2 + (3α + 4)x − n = 0. Then
λ(T ) ≤ ξ,

(49)

and equality holds if and only if T is the tree obtained from the star graph K1,α by adding pendant
edges to n − α − 1 of the α pendant vertices of K1,α .
290

www.ejgta.org

Bounds for the Laplacian spectral radius of graphs

|

K.L. Patra and B.K. Sahoo

The tree obtained from K1,α in the equality case of (49) is well-defined, since α(T1 ) ≥ dn/2e
for any tree T1 with n vertices. As an application of Theorem 3.4, Zhang obtained the following
bound (50) for a tree in terms of its independence number [57, Corollary 2.8, Theorem 2.9].
Theorem 3.5. [57] Let T be a tree with n vertices and independence number α = α(T ). Then
λ(T ) ≤ α + 1 +

n−α−1
< 2 + α.
(α − 1)2

(50)

Further, equality holds in the first inequality if and only if T is the star graph K1,n−1 .
3.2. Non-regular graphs
The following four upper bounds (51) − (54) for the Laplacian spectral radius of non-regular
connected graphs are known. The bound (51) was given by Shi in [46, Theorem 3.5].
Theorem 3.6. [46] Let G be a connected non-regular graph on n vertices with diameter D and
maximal vertex degree ∆. Then
λ(G) < 2∆ −

2
.
(2D + 1)n

(51)

For a connected graph G, its diameter is always less than the number of vertices. In that case,
Theorem 3.6 implies the following [46, Theorem 3.4].
Theorem 3.7. [46] Let G be a connected non-regular graph with n vertices and maximal vertex
degree ∆. Then
λ(G) < 2∆ − 2/n(2n − 1).
(52)
The bound (53) below, which is an improvement of (51), was given by Liu and Lu in [27,
Theorem 2.1].
Theorem 3.8. [27] Let G be a connected non-regular graph with n vertices, m edges, diameter D
and maximal vertex degree ∆. Then
λ(G) < 2∆ −

2n∆ − 4m
.
n(D(2n∆ − 4m) + 1)

(53)

In [24, Theorem 2.3], Li et al. gave the following bound (54) which further improves the bound
(53).
Theorem 3.9. [24] Let G be a connected non-regular graph with n vertices, diameter D and
maximal vertex degree ∆. Then
1
.
(54)
λ(G) < 2∆ −
nD

291

www.ejgta.org

Bounds for the Laplacian spectral radius of graphs

|

K.L. Patra and B.K. Sahoo

3.3. Triangular graphs
A graph G is called a triangular graph if every pair of adjacent vertices of G has at least one
common neighbour vertex. The following upper bound (55) for triangular graphs was obtained by
Lu et al. in [31, Theorem B].
Theorem 3.10. [31] Let G be a graph with n vertices, m edges, maximal vertex degree ∆ and
minimal vertex degree δ. If G is triangular such that each edge of G belongs to at least t ≥ 1
triangles, then

p
1
2
2
2∆ − t + (2∆ − t) + 8m − 4δ(n − 1) − 4δ + 4(δ − 1)∆ ,
λ(G) ≤
2

(55)

and equality occurs if G is the complete graph Kt+2 .
Guo et al. proved in [17, Theorem 3.2] the following upper bound (56) which improves (55).
By [17, Remark 3.1], (56) is always better than (23) for triangular graphs.
Theorem 3.11. [17] Let G be a graph with V = {v1 , v2 , · · · , vn }, vertex degrees di and average
2-degrees mi . If G is triangular such that each edge of G belongs to at least t ≥ 1 triangles, then

 

p
1
2
2di − t + 4di mi − 4tdi + t : vi ∈ V ,
(56)
λ(G) ≤ max
2
and equality occurs if G is the complete graph Kt+2 .
3.4. Maximal planar graphs
A planar graph G is called a maximal planar graph if for every pair of nonadjacent vertices vi
and vj of G, the graph G + vi vj is non-planar. In a maximal planar graph G, each pair of adjacent
vertices has at least two common neighbour vertices and so G is a triangular graph in particular.
Taking t = 2 in Theorems 3.10 and 3.11, the following two upper bounds (57) and (58) are
obtained for maximal planar graphs. The bound (57) appeared in [31, Theorem C], and (58)
appeared in [17, Theorem 3.3] which is an improvement of (57).
Theorem 3.12. [31, 17] Let G be a maximal planar graph with n ≥ 4 vertices, m edges, vertex
degrees di , average 2-degrees mi , maximal vertex degree ∆ and minimal vertex degree δ. Then
p
λ(G) ≤ ∆ − 1 + (∆ − 1)2 + 2m − δ(n − 1) − δ 2 + (δ − 1)∆;
(57)
and

o
n
p
λ(G) ≤ max di − 1 + di mi − 2di + 1 : 1 ≤ i ≤ n .

292

(58)

www.ejgta.org

Bounds for the Laplacian spectral radius of graphs

|

K.L. Patra and B.K. Sahoo

3.5. Triangle-free graphs
The following two upper bounds (59) and (60) were given by Li et al. in [24, Theorem 3.2,
Corollary 3.3] for triangle-free graphs.
Theorem 3.13. [24] Let G be a triangle-free graph with n vertices, m edges and maximal vertex
degree ∆. Then
√
(59)
λ(G) ≤ ∆ + m;
and

n
.
2
In both the bounds, equality holds if G is the complete bipartite graph K∆,∆ .
λ(G) ≤ ∆ +

(60)

The bound (60) follows from (59) using Turán’s theorem which says that the number of edges
in any triangle-free graph is at most n2 /4.
3.6. Bipartite graphs
For a bipartite graph G = (V, E) with bipartition V = V1 ∪ V2 , let ∆1 (respectively, ∆2 ) denote
the maximal vertex degree among the vertices in V1 (respectively, V2 ). Similarly, δ1 and δ2 are
defined for the minimal vertex degrees in V1 and V2 , respectively. The following upper bound was
given by Li et al. in [24, Theorem 3.9] for connected graphs (however, connectedness of the graph
is not required in the proof).
Theorem 3.14. [24] Let G = (V1 ∪ V2 , E) be a bipartite graph with m edges. If |V1 | = n1 and
|V2 | = n2 , then
λ(G) ≤ max {θ1 , θ2 },
(61)
where


p
1
∆1 + δ2 + (∆1 + δ2 )2 + 8(m − n2 δ2 ) ;
2

p
1
2
∆2 + δ1 + (∆2 + δ1 ) + 8(m − n1 δ1 ) .
θ2 =
2
Further, equality holds if and only if G is semiregular.
θ1 =

4. Lower Bounds
Unlike many upper bounds, only few lower bounds are known for the Laplacian spectral radius
of a graph. For any graph G, λ(G) ≥ 0, and equality holds if and only if G has no edge. Recall
that we are assuming all our graphs G to be without isolated vertices and hence at least one edge,
so that λ(G) > 0.
The following bound (62) which is the first lower bound for the Laplacian spectral radius of a
graph was given by Fiedler in 1973 [11, 3.7(5◦ )].
Theorem 4.1. [11] Let G be a graph with n vertices and maximal vertex degree ∆. Then
λ(G) ≥

n
∆.
n−1

293

(62)

www.ejgta.org

Bounds for the Laplacian spectral radius of graphs

|

K.L. Patra and B.K. Sahoo

In [12, Corollary 2], Grone and Merris obtained the following lower bound (63) which improves (62). In [60, Theorem 2.3], Zhang and Luo gave an alternate proof of (63) and characterized
the equality case for connected graphs.
Theorem 4.2. [12, 60] Let G be a graph with n vertices and maximal vertex degree ∆. Then
λ(G) ≥ ∆ + 1.

(63)

If ∆ = n−1, then equality holds. Conversely, if G is connected and equality holds, then ∆ = n−1.
The following lower bound (64) was given by Zhang and Li in [58, Theorem 2.1] in terms of
number of vertices and edges of a graph.
Theorem 4.3. [58] Let G be a graph with n vertices and m edges. Then
s
!
1
2m(n(n − 1) − 2m)
λ(G) ≥
2m +
.
n−1
n(n − 2)

(64)

If G is connected, then equality holds if and only if G is the complete graph Kn .
In [6, Theorem 2.4], Das gave the following lower bound (65) which is an improvement of the
bound (63).
Theorem 4.4. [6] Let G = (V, E) be a graph with V = {v1 , v2 , · · · , vn } and vertex degrees di .
Then
!)
(
r
q
1
d2i + 2di − 2dj − 2 + (d2i + 2di + 2dj + 4)2 + 4ri rj
(65)
λ(G) ≥ max √
vi vj ∈E
2
where ri = di − cij − 1, rj = dj − cij − 1 and cij is the number of common neighbours of vi and
vj .
The following bound (66) was given by Lu et al. in [29, Lemma 3]. The original result was
stated for connected graphs, but their proof works for any graph.
Theorem 4.5. [29] Let G = (V, E) be a graph with P
n vertices and H = (V
P1 , E1 ) be an induced
subgraph of G with t vertices, where t < n. Let a =
dH (v)/t and b =
dG (v)/t. Then
v∈V1

λ(G) ≥

v∈V1

n(b − a)
.
n−t

(66)

If equality holds, then |K1 (u)| is independent of u ∈ V1 and |K2 (u)| is independent of u ∈ V2 ,
where V2 = V \ V1 , Ki (u) = {v ∈ Vj : uv ∈ E} for u ∈ Vi , {i, j} = {1, 2}.
The following lower bound (67) was given by Lu et al. in [32, Theorem 3].

294

www.ejgta.org

Bounds for the Laplacian spectral radius of graphs

|

K.L. Patra and B.K. Sahoo

Theorem 4.6. [32] Let G be a graph and P = v1 v2 · · · vs+1 be a path in G such that the induced
subgraph of G on the vertices v1 , v2 , · · · , vs+1 is P itself. Then
!
s+1
X
1
di + 2s
(67)
λ(G) ≥
s + 1 i=1
As an application of Theorem 4.6, the following lower bound (68) was obtained in [32, Corollary 6] for connected graphs.
Theorem 4.7. [32] Let G be a connected graph with n vertices, degree sequence d1 ≥ d2 ≥ · · · ≥
dn and diameter D. Then
(D + 1)eD+1 + 2D
λ(G) ≥
,
(68)
D+1
1
(dn−D + dn−D+1 + · · · + dn ). If G is a complete graph, then equality holds in
where eD+1 = D+1
(68).

As consequences of Theorem 4.7, the following lower bounds (69) and (70) were obtained in
[32, Corollaries 8, 9]. The bound (70) is better than (69) if the minimal vertex degree is at least
two.
Theorem 4.8. [32] Let G be a connected graph with diameter D and minimal vertex degree δ.
Then
4D
,
(69)
λ(G) ≥
D+1
and
(D + 1)δ + 2D
λ(G) ≥
.
(70)
D+1
The above lower bounds are given in terms of the number of vertices, vertex degrees, diameter,
maximal and minimal vertex degrees of a graph. Some lower bounds for the Laplacian spectral radius of a graph are given involving other graph parameters like independence number, domination
number and covering number of the graph.
We have defined the independence number of a graph in Section 3.1. In [57, Theorems 3.1,
3.2], Zhang proved the following lower bounds (71) − (73) involving independence number of a
graph.
Theorem 4.9. [57] Let G be a graph with n vertices and independence number α = α(G). Then
λ(G) ≥

n
,
α

(71)

with equality if and only if α is a factor of n and G has α components each of which is the complete
graph K αn .

295

www.ejgta.org

Bounds for the Laplacian spectral radius of graphs

|

K.L. Patra and B.K. Sahoo

Theorem 4.10. [57] Let G be a graph with n vertices and independence number α = α(G). Then
λ(G) ≥

where Σα (G) = max

α
P

nΣα (G)
,
α(n − α)

(72)


d(ui ) : {u1 , · · · , uα } is an independent set of G .

i=1

By our assumption, the minimal vertex degree δ of G is at least one. As an application of (72),
n
nδ
≥ n−α
. In particular,
it follows using the fact Σα (G) ≥ αδ that λ(G) ≥ n−α
λ(G) ≥

n
.
min{α, n − α}

(73)

Further, equality holds in (73) if and only if either α is a factor of n and G has α components each
of which is the complete graph K αn , or n − α is a factor of n and G has n − α components each of
α
which is the star graph K1, n−α
[57, Colollary 3.4].
A dominating set of a graph G is a subset X of the vertex set V of G such that each vertex
of V \ X is adjacent to at least one vertex of X. The minimum cardinality of a dominating set is
called the domination number of G, denoted by γ(G). We have γ(G) > 0 (since V is nonempty).
In [29, Theorem 10], Lu et al. proved the following bound (74) in terms of the number of
vertices and the domination number of a connected graph (however, their proof could work for
disconnected graphs also).
Theorem 4.11. [29] Let G be a graph with n vertices and domination number γ = γ(G). Then
λ(G) ≥ n/γ.

(74)

If G is connected, then equality holds if and only if ∆(G) = n − 1.
The following lower bound (75) was given by Nikiforov [40, Theorem 3] which slightly improves the bound (74).
Theorem 4.12. [40] Let G be a graph with n vertices and domination number γ = γ(G). Then
λ(G) ≥ dn/γe.

(75)

Further, equality holds if and only if G = G1 ∪ G2 , where the graphs G1 and G2 satisfy the
conditions: (i) |G1 | = dn/γe and γ(G1 ) = 1; (ii) γ(G2 ) = γ − 1 and λ(G2 ) ≤ dn/γe.
A cover of a graph G is a subset X of the vertex set of G such that every edge of G is incident
with at least one vertex of X. The minimum cardinality of a cover is called the covering number
of G, denoted by τ (G). Since all graphs are without isolated vertices by our assumption, it follows
that every cover of G is also a dominating set of G. So γ(G) ≤ τ (G). Using Theorem 4.11, the
following lower bound follows [29, Corollary 11].

296

www.ejgta.org

Bounds for the Laplacian spectral radius of graphs

|

K.L. Patra and B.K. Sahoo

Theorem 4.13. [29] Let G be a graph with n vertices and covering number τ = τ (G). Then
λ(G) ≥ n/τ.

(76)

If G is connected, then equality holds if and only if G is the star graph.
The bound (76) was improved by Shi in [46, Theorem 3.6].
Theorem 4.14. [46] Let G be a graph with n vertices, minimal vertex degree δ ≥ 1 and covering
number τ = τ (G). Then
λ(G) ≥ δn/τ.
(77)
4.1. Trees
The following lower bound (78) for a tree was given by Das in [8, Theorem 2.4], which is an
improvement of (63) in the case of trees.
Theorem 4.15. [8] Let T = (V, E) be a tree with V = {v1 , v2 , · · · , vn }, vertex degrees di and
average 2-degrees mi . Then
 h

i
p
1
2
λ(T ) ≥ max
(di + mi + 1) + (di + mi + 1) − 4(di mi + 1) : vi ∈ V .
(78)
2
Further, equality holds in (78) if and only if T is isomorphic to the tree T (di , dj ) formed by joining
the centers of di copies of K1,dj −1 to a new vertex wi .
4.2. Triangle-free graphs
In [60, Theorems 3.1, 3.4], Zhang and Luo proved the following two lower bounds for trianglefree graphs: one is in terms of the number of vertices and edges, and the other is in terms of vertex
degrees and average 2-degrees.
Theorem 4.16. [60] Let G = (V, E) be a triangle-free graph with n vertices, m edges, vertex
degrees di and average 2-degrees mi . Then the following hold:


16m2 2m
m3/4
,
+ √
;
(79)
λ(G) ≥ max
n3
n
2n 2
 

p
1
2
λ(G) ≥ max
di + mi + (di − mi ) + 4di : vi ∈ V
.
(80)
2
Moreover, equality holds in (79) if n is even and G is the complete bipartite graph K n2 , n2 .
n 2
√ o
As a consequence of the above two bounds it follows that λ(G) ≥ max 4kn , k + k for a
k-regular triangle-free graph G on n vertices [60, Corollary 3.5]. By the remark in [60, p.38], (80)
is better than (63) for triangle-free graphs.

297

www.ejgta.org

Bounds for the Laplacian spectral radius of graphs

|

K.L. Patra and B.K. Sahoo

4.3. Bipartite graphs
We now state the lower bounds known for bipartite graphs. The first result in this direction was
obtained by Yu et al. in [54, Theorem 9].
Theorem 4.17. [54] Let G = (V, E) be a bipartite graph with V = {v1 , · · · , vn }, vertex degrees
di and average 2-degrees mi . Then
v
!
!
u
X
u X
2
(d2i + mi di ) /
d2i .
λ(G) ≥ t
(81)
vi ∈V

vi ∈V

If G is connected, then equality holds if and only if G is semiregular.
As an application of Theorem 4.17 together with the Cauchy-Schwarz inequality, the following
bound is obtained in [54, Corollary 10], also see [20, Theorem 3.2].
Theorem 4.18. [54] Let G be a bipartite graph with V = {v1 , v2 , · · · , vn } and vertex degrees di .
Then
s
1 X 2
d.
(82)
λ(G) ≥ 2
n v ∈V i
i

If G is connected, then equality holds if and only if G is regular.
≥ 2δ for a bipartite graph G, where G has
From the above theorem, it follows that λ(G) ≥ 4m
n
n vertices, m edges and minimal vertex degree δ [54, Corollary 11]. The following lower bound
was given by Hong and Zhang in [20, Theorem 3.3].
Theorem 4.19. [20] Let G = (V, E) be a bipartite graph with V = {v1 , · · · , vn }, m edges and
vertex degrees di . Then
s
1 X
(di + dj − 2)2 .
(83)
λ(G) ≥ 2 +
m v v ∈E
i j

If G is connected, then equality holds if and only if G is a semiregular graph or a path with four
vertices.
In [46, Theorems 3.1, 3.3, Corollary 3.1], Shi gave the following three lower bounds for the
Laplacian spectral radius of bipartite graphs.
Theorem 4.20. [46] Let G = (V, E) be a bipartite graph with V = {v1 , v2 , · · · , vn }, m edges,
vertex degrees di , average 2-degrees mi , maximal vertex degree ∆ and minimal vertex degree δ.
Then the following hold:
np
o
λ(G) ≥ min
2di (di + mi ) : vi ∈ V ;
(84)
p
λ(G) ≥ 2δ 2 + 4m − 2∆(n − 1) + 2δ(∆ − 1);
(85)


2
1/2
X
X p
di3/2 +
λ(G) ≥ 
dj  /(2m) .
(86)
vi ∈V

vi vj ∈E

If G is connected, then equality holds in each of these three bounds if and only if G is regular.
298

www.ejgta.org

Bounds for the Laplacian spectral radius of graphs

|

K.L. Patra and B.K. Sahoo

Though connectedness is assumed in [46, Theorems 3.3] for the proof of the bound (86), a
careful application of Lemma 1.2 shows that the given proof would work for disconnected graphs
also. The equality case of (84) in [46, Theorem 3.1] was characterized as the following: If the
bipartite graph G is connected, then equality holds in (84) if and only if the value d2i + di mi is
independent of the vertex vi ∈ V , but this is equivalent to that G is regular (see Remark 2.1).
The following bound was given by Guo in [16, Theorem 4.1]. The same bound was also
obtained in [24, Theorem 3.6], where equality case was characterized. Their proofs work for any
bipartite graph.
Theorem 4.21. [16, 24] Let G = (V, E) be a bipartite graph with n vertices and m edges. Suppose
that V has bipartition V = V1 ∪ V2 with |V1 | = n1 and |V2 | = n2 . Then
λ(G) ≥

mn
.
n1 n2

(87)

Further, equality holds if and only if G is semiregular.
The following bound was given in [24, Theorem 3.5] for non-regular bipartite graphs in terms
of the number of vertices and edges.
Theorem 4.22. [24] Let G be a non-regular bipartite graph with n vertices and m edges. Then
λ(G) ≥

4m
1
+
.
n
m+n

(88)

The next bound was given by Tian et al. in [50, Theorem 1], as a corollary of which the bound
(81) was obtained in [50, Corollary 2].
Theorem 4.23. [50] Let G = (V, E) be a bipartite graph with V = {v1 , v2 , · · · , vn }, vertex
degrees di and average 2-degrees mi . Then
v
2

u
!
uX
n
n
X
X
u
di (d2i + mi di ) +
λ(G) ≥ t
(d2j + mj dj ) /
(d2i + mi di )2 .
(89)
i=1

vi vj ∈E

i=1

If G is connected, then equality holds if and only if there exists a positive constant t such that
P
di (d2i + mi di ) + vi vj ∈E (d2j + mj dj )
=t
d2i + mi di
for all i ∈ {1, 2, · · · , n}. In fact t = λ(G).
References
[1] W.N. Anderson and T.D. Morley, Eigenvalue of the Laplacian of a graph, Linear Multilinear
Algebra 18 (1985), 141–145.
299

www.ejgta.org

Bounds for the Laplacian spectral radius of graphs

|

K.L. Patra and B.K. Sahoo

[2] J.A. Bondy and U.S.R. Murty, Graph Theory with Applications, American Elsevier Publishing Co., Inc., New York, 1976.
[3] R.A. Brualdi, From the Editor-in-Chief, Linear Algebra Appl. 360 (2003), 279–283.
[4] S.M. Cioabǎ, Sums of powers of the degrees of a graph, Discrete Math. 306 (2006), 1959–
1964.
[5] K.C. Das, An improved upper bound for Laplacian graph eigenvalues, Linear Algebra Appl.
368 (2003), 269–278.
[6] K.C. Das, The largest two Laplacian eigenvalues of a graph, Linear Multilinear Algebra 52
(2004), 441–460.
[7] K.C. Das, A characterization on graphs which achieve the upper bound for the largest Laplacian eigenvalue of graphs, Linear Algebra Appl. 376 (2004), 173–186.
[8] K.C. Das, Sharp lower bounds on the Laplacian eigenvalues of trees, Linear Algebra Appl.
384 (2004), 155–169.
[9] K.C. Das, Sharp upper bounds on the spectral radius of the Laplacian matrix of graphs, Acta
Math. Univ. Comenian. 74 (2005), 185–198.
[10] D. de Caen, An upper bound on the sum of squares of degrees in a graph, Discrete Math. 185
(1998), 245–248.
[11] M. Fiedler, Algebraic connectivity of graphs, Czechoslovak Math. J. 23(98) (1973), 298–305.
[12] R. Grone and R. Merris, The Laplacian spectrum of a graph II, SIAM J. Discrete Math. 7
(1994), 221–229.
[13] R. Grone, R. Merris and V.S. Sunder, The Laplacian spectrum of a graph, SIAM J. Matrix
Anal. Appl. 11 (1990), 218–238.
[14] J.M. Guo, On the Laplacian spectral radius of a tree, Linear Algebra Appl. 368 (2003), 379–
385.
[15] J.M. Guo, A new upper bound for the Laplacian spectral radius of graphs, Linear Algebra
Appl. 400 (2005), 61–66.
[16] J.M. Guo, Sharp upper and lower bounds for the Laplacian spectral radius and the spectral
radius of graphs, Acta Math. Appl. Sin. Engl. Ser. 24 (2008), 289–296.
[17] J.M. Guo, J. Li and W.C. Shiu, A note on the upper bounds for the Laplacian spectral radius
of graphs, Linear Algebra Appl. 439 (2013), 1657–1661.
[18] I. Gutman, V. Gineityte, M. Lepovic and M. Petrovic, The high-energy band in the photoelectron spectrum of alkanes and its dependence on molecular structure, J. Serb. Chem. Soc.
64 (1999), 673–680.
300

www.ejgta.org

Bounds for the Laplacian spectral radius of graphs

|

K.L. Patra and B.K. Sahoo

[19] I. Gutman, D. Vidovic and D. Stevanovic, Chemical applications of the Laplacian spectrum.
VI. On the largest Laplacian eigenvalue of alkanes, J. Serb. Chem. Soc. 67 (2002), 407–413.
[20] Y. Hong and X.D. Zhang, Sharp upper and lower bounds for largest eigenvalue of the Laplacian matrices of trees, Discrete Math. 296 (2005), 187–197.
[21] R.A. Horn and C.R. Johnson, Matrix Analysis. Reprinted with corrections, Cambridge University Press, Cambridge, 1990.
[22] J.S. Li and Y.L. Pan, de Caen’s inequality and bounds on the largest Laplacian eigenvalue of
a graph, Linear Algebra Appl. 328 (2001), 153–160.
[23] J.S. Li and Y.L. Pan, Upper bounds for the Laplacian graph eigenvalues, Acta Math. Sin. 20
(2004), 803–806.
[24] J. Li, W.C. Shiu and A. Chang, The Laplacian spectral radius of graphs, Czechoslovak Math.
J. 60(135) (2010), 835–847.
[25] J.S. Li and X.D. Zhang, A new upper bound for eigenvalues of the Laplacian matrix of a
graph, Linear Algebra Appl. 265 (1997), 93–100.
[26] J.S. Li and X.D. Zhang, On the Laplacian eigenvalues of a graph, Linear Algebra Appl. 285
(1998), 305–307.
[27] H. Liu and M. Lu, Bounds for the Laplacian spectral radius of graphs, Linear Multilinear
Algebra 58 (2010), 113–119.
[28] H. Liu, M. Lu and F. Tian, On the Laplacian spectral radius of a graph, Linear Algebra Appl.
376 (2004), 135–141.
[29] M. Lu, H. Liu and F. Tian, Bounds of Laplacian spectrum of graphs based on the domination
number, Linear Algebra Appl. 402 (2005), 390–396.
[30] M. Lu, H. Liu and F. Tian, Laplacian spectral bounds for clique and independence numbers
of graphs, J. Combin. Theory Ser. B 97 (2007), 726–732.
[31] M. Lu, H. Liu and F. Tian, An improved upper bound for the Laplacian spectral radius of
graphs, Discrete Math. 309 (2009), 6318–6321.
[32] M. Lu, L.Z. Zhang and F. Tian, Lower bounds of the Laplacian spectrum of graphs based on
diameter, Linear Algebra Appl. 420 (2007), 400–406.
[33] R. Merris, Laplacian matrices of graphs: a survey, Linear Algebra Appl. 197/198 (1994),
143–176.
[34] R. Merris, A survey of graph Laplacians, Linear Multilinear Algebra 39 (1995), 19–31.
[35] R. Merris, A note on Laplacian graph eigenvalues, Linear Algebra Appl. 285 (1998), 33–35.
301

www.ejgta.org

Bounds for the Laplacian spectral radius of graphs

|

K.L. Patra and B.K. Sahoo

[36] H. Minc, Nonnegative Matrices. Wiley-Interscience Series in Discrete Mathematics and Optimization. John Wiley & Sons, Inc., New York, 1988.
[37] B. Mohar, The Laplacian spectrum of graphs, Graph theory, combinatorics, and applications,
Vol. 2, 871–898, Wiley-Intersci. Publ., Wiley, New York, 1991.
[38] B. Mohar and S. Poljak, Eigenvalues and max-cut problem, Czechoslovak Math. J. 40(115)
(1990), 343–352.
[39] B. Mohar and S. Poljak, Eigenvalues in combinatorial optimization, Combinatorial and
graph-theoretical problems in linear algebra, 107–151, IMA Vol. Math. Appl., 50, Springer,
New York, 1993.
[40] V. Nikiforov, Bounds of graph eigenvalues I, Linear Algebra Appl. 420 (2007), 667–671.
[41] Y.L. Pan, Sharp upper bounds for the Laplacian graph eigenvalues, Linear Algebra Appl. 355
(2002), 287–295.
[42] S. Poljak and Z. Tuza, Maxinum cuts and large bipartite subgraphs, Combinatorial optimization, 181–244, DIMACS Ser. Discrete Math. Theoret. Comput. Sci., 20, Amer. Math. Soc.,
Providence, RI, 1995.
[43] O. Rojo, Improved bounds for the largest eigenvalue of trees, Linear Algebra Appl. 404
(2005), 297–304.
[44] O. Rojo, R. Soto and H. Rojo, An always nontrivial upper bound for Laplacian graph eigenvalues, Linear Algebra Appl. 312 (2000), 155–159.
[45] O. Rojo, R. Soto and H. Rojo, Bounds for sums of eigenvalues and applications, Comput.
Math. Appl. 39 (2000), 1–15.
[46] L. Shi, Bounds on the (Laplacian) spectral radius of graphs, Linear Algebra Appl. 422 (2007),
755–770.
[47] J.L. Shu, Y. Hong and W.R. Kai, A sharp upper bound on the largest eigenvalue of the Laplacian matrix of a graph, Linear Algebra Appl. 347 (2002), 123–129.
[48] P. Solé, Expanding and forwarding, Discrete Appl. Math. 58 (1995), 67–78.
[49] D. Stevanović, Bounding the largest eigenvalue of trees in terms of the largest vertex degree,
Linear Algebra Appl. 360 (2003), 35–42.
[50] G.X. Tian, T.Z. Huang and B. Zhou, A note on sum of powers of the Laplacian eigenvalues
of bipartite graphs, Linear Algebra Appl. 430 (2009), 2503–2510.
[51] T.F. Wang, Several sharp upper bounds for the largest Laplacian eigenvalue of a graph, Sci.
China Ser. A 50 (2007), 1755–1764.
302

www.ejgta.org

Bounds for the Laplacian spectral radius of graphs

|

K.L. Patra and B.K. Sahoo

[52] T. Wang, J. Yang and B. Li, Improved upper bounds for the Laplacian spectral radius of a
graph, Electron. J. Combin. 18 (2011), no. 1, Paper 35, 11 pp.
[53] A. Yu, A new upper bound for the Laplacian spectral radius of a graph, Electron. J. Linear
Algebra 20 (2010), 730–738.
[54] A. Yu, M. Lu and F. Tian, On the spectral radius of graphs, Linear Algebra Appl. 387 (2004),
41–49.
[55] A. Yu, M. Lu and F. Tian, Characterization on graphs which achieve a Das’ upper bound for
Laplacian spectral radius, Linear Algebra Appl. 400 (2005), 271–277.
[56] X.D. Zhang, Two sharp upper bounds for the Laplacian eigenvalues, Linear Algebra Appl.
376 (2004), 207–213.
[57] X.D. Zhang, On the two conjectures of Graffiti, Linear Algebra Appl. 385 (2004), 369-379.
[58] X.D. Zhang, J.S. Li, On the k-th largest eigenvalue of the Laplacian matrix of a graph, Acta
Math. Appl. Sinica 17 (2001), 183–190.
[59] X.D. Zhang, J.S. Li, The Laplacian spectrum of a mixed graph, Linear Algebra Appl. 353
(2002), 11–20.
[60] X.D. Zhang and R. Luo, The spectral radius of triangle-free graphs, Australas. J. Combin. 26
(2002), 33-39.
[61] X.D. Zhang and R. Luo, The Laplacian eigenvalues of mixed graph, Linear Algebra Appl.
362 (2003), 109–119.
[62] B. Zhou and H.H. Cho, Remarks on spectral radius and Laplacian eigenvalues of a graph,
Czechoslovak Math. J. 55(130) (2005), 781–790.
[63] D. Zhu, On upper bounds for Laplacian graph eigenvalues, Linear Algebra Appl. 432 (2010),
2764–2772.

303

www.ejgta.org