Linear Algebra and its Applications 368 (2003) 379–385
www.elsevier.com/locate/laa
On the Laplacian spectral radius of a tree
Ji-Ming Guo
Department of Mathematics, University of Petroleum, ShanDong 257061, China
Received 1 March 2001; accepted 27 November 2002
Submitted by R.A. Brualdi
Abstract
Let G be a graph; its Laplacian matrix is the difference of the diagonal matrix of its ver-
tex degrees and its adjacency matrix. In this paper, we present a sharp upper bound for the
Laplacian spectral radius of a tree in terms of the matching number and number of vertices,
and deduce from that the largest few Laplacian spectral radii over the class of trees on a given
number of vertices.
© 2003 Published by Elsevier Science Inc.
AMS classification: 05C50
Keywords: Laplacian spectral radius; Matching number; Retraction
1. Introduction
Let G = (V , E) be a graph on vertex set V = {v1 , v2 , . . . , vn }. Let |G| denote
the number of vertices of G. The Laplacian matrix L(G) = D(G) − A(G) is the
difference of D(G) = diag(d(v1 ), d(v2 ), . . . , d(vn )), the diagonal matrix of vertex
degrees, and the adjacency matrix. The Laplacian spectral radius of G is the largest
eigenvalue of its Laplacian matrix, denoted by λ1 (G). Since the 1980s, many au-
thors, for example Anderson and Morley [1], Li and Zhang [5,6], Merris [7], and
Rojo et al. [9] have done a lot of work on the Laplacian spectral radius of graphs. In
this paper, a sharp upper bound for the Laplacian spectral radius of a tree is given in
terms of the matching number and number of vertices.
Two distinct edges in a graph G are independent if they are not incident with a
common vertex in G. A set of pairwise independent edges of G is called a matching
0024-3795/03/$ - see front matter 2003 Published by Elsevier Science Inc.
doi:10.1016/S0024-3795(02)00716-4
380 J.-M. Guo / Linear Algebra and its Applications 368 (2003) 379–385
in G, while a matching of maximum cardinality is a maximum matching in G. The
matching number β(G) of G is the cardinality of a maximum matching of G.
Throughout this paper, we shall denote the characteristic polynomial of L(G) by
µ(G, x) = det(xI − L(G)).
2. Lemmas and results
Lemma 1 [2]. The maximum eigenvalue r of every principal submatrix (of order
less than n) of a non-negative matrix A (of order n) does not exceed the maximum
eigenvalue r of A. If A is irreducible, then r < r always holds. If A is reducible,
then r = r holds for at least one principal submatrix.
Lemma 2 [2]. The increase of any element of a non-negative matrix A does not
decrease the maximum eigenvalue. The maximum eigenvalue increases strictly if A
is an irreducible matrix.
Lemma 3 [3]. Let G be a bipartite graph. Then B(G) = D(G) + A(G) and L(G)
are unitarily similar; in particular, the maximum eigenvalue of L(G) is simple pro-
vided G is connected.
From Lemmas 1–3, we have the following result:
Corollary 1. Let G be a connected bipartite graph, and let G be a subgraph of G.
Then λ1 (G ) λ1 (G), and equality holds if and only if G = G.
Lemma 4 [3]. Let T be a tree. Suppose v1 and vk are vertices each of degree at
least three. Suppose the unique path v1 , v2 , . . . , vk from v1 to vk is homeomorphic
to an edge (i.e., apart from the endpoints, each vertex on the path has degree two).
Let T be the tree obtained from T by retracting along the entire path (i.e., delet-
ing all edges {v1 v2 , v2 v3 , . . . , vk−1 vk } and identifying vertices v1 , v2 , . . . , vk ). Then
λ1 (T ) > λ1 (T ).
Lemma 5 [1]. Let G be a graph. Then λ1 (G) max{d(u) + d(v) : uv ∈ E}.
Lemma 6 [8]. If G has at least one edge, then λ1 (G) d1 (G) + 1. For G a connec-
ted graph on n > 1 vertices, equality holds if and only if d1 (G) = n − 1.
Let Tmn (2m n + 1) denote the tree graph with n vertices obtained from a star
K1,n−m by joining m − 1 pendants (degree 1 vertices) of K1,n−m to the m − 1 iso-
lated vertices by m − 1 edges.
J.-M. Guo / Linear Algebra and its Applications 368 (2003) 379–385 381
Theorem 1. Let T be a tree on n vertices with matching number β = β(T ). Then
λ1 (T ) r, where r is the maximum root of the equation
x 3 − (n − β + 4)x 2 + (3n − 3β + 4)x − n = 0.
The equality holds if and only if T = Tβn .
Proof. By the direct computation, we have the characteristic polynomial of the tree
Tβn is
µ(Tβn , x) = x(x − 1)n−2β (x 2 − 3x + 1)β−2
× [x 3 − (n − β + 4)x 2 + (3n − 3β + 4)x − n].
Suppose that v1 and v2 are vertices of T each of degree at least three and the
unique path from v1 to v2 is homeomorphic to an edge. Then we can apply Lemma
4 to T . Thus, a new tree T1 can be constructed by retracting T along the entire path.
Go on the above process until we obtain a tree Ti = T̃ (T0 = T ) such that we can not
apply Lemma 4 to T̃ . Then, we have
|T̃ | |T |, β(T̃ ) β(T )
and
λ1 (T ) λ1 (T̃ ) (λ1 (T ) = λ1 (T̃ ) if and only if T̃ = T ).
Further, we have β(T ) − β(T̃ ) |T | − |T̃ | and there exists at most one vertex
w of T̃ such that d(w) 3. If there is no such vertex w, then T̃ is a path. From
the above discussions, we conclude that T = T̃ = Pn , a path with n vertices. Since
λ1 (Pn ) = 4 sin2 ((n − 1)π /2n) (see [1]) and β(Pn ) = [n/2], the result is obvious. If
there is such a vertex w such that d(w) 3. We distinguish the following two cases:
|T̃ |
Case 1. Assume that T̃ = K1,|T̃ |−1 or T . Since β(T ) − β(T̃ ) |T | − |T̃ |, then
β(T̃ )
T̃ is an induced subgraph of Tβn . We have from Corollary 1 that λ1 (T̃ ) λ1 (Tβ(T
n ),
)
the equality holds if and only if T = T̃ = K1,n−1 or Tβ(T
n .
)
|T̃ |
Case 2. Assume that T̃ =
/ K1,|T̃ |−1 , T . Then there exists a w − v path of T̃
β(T̃ )
W : w = w0 , w1 , w2 , . . . , wk−1 , wk = v,
such that k 3 and v is a pendant vertex of T̃ .
Let T ∗ = T̃ − wk−2 wk−1 + wwk−1 , then |T ∗ | = |T̃ |. Further, we verify that
β(T ∗ ) = β(T̃ ). Suppose M is a maximum matching of T̃ . Then either wk−2 wk−1
∈ M or wk−1 wk ∈ M. If wk−2 wk−1 ∈ M, then M ∗ = {M − {wk−2 wk−1 }} ∪
{wk−1 wk } is a matching of T ∗ and |M ∗ | = |M|; if wk−2 wk−1 ∈
/ M, then wk−1 wk ∈
M. Thus, M is also a matching of T ∗ . So, we have β(T ∗ ) |M| = β(T̃ ). By similar
reasoning, we have β(T ∗ ) β(T̃ ). Hence, we have β(T ∗ ) = β(T̃ ).
382 J.-M. Guo / Linear Algebra and its Applications 368 (2003) 379–385
We have from Lemmas 5 and 6 that
λ1 (T ∗ ) > d1 (T ∗ ) + 1 = d1 (T̃ ) + 2 λ1 (T̃ ).
|T̃ |
Continuing the above process we have λ1 (T̃ ) < λ1 T . From the discussion
β(T̃ )
) , and the proof is complete.
n
of Case 1, We conclude that λ1 (T ) < λ1 Tβ(T
We have from Lemmas 4 and 5 that
λ1 (Tin ) > d1 (Tin ) + 1 = n − i + 1 = d1 (Ti+1
n
) + 2 λ1 (Ti+1
n
). (1)
Then, the following two results hold.
Corollary 2 [1]. Let T be a tree of order n, then λ1 (T ) n, and equality holds if
and only if T = T1n = K1,n−1 .
/ K1,n−1 then λ1 (T ) r1 , where r1
Corollary 3. Let T be a tree of order n. If T =
is the maximum root of the equation
x 3 − (n + 2)x 2 + (3n − 2)x − n = 0.
The equality holds if and only if T = T2n .
Let T (s, t) denote the tree of diameter 3 having exactly two non-pendant ver-
tices, one of which is adjacent to s pendants and the other of which is adjacent to t
pendants. In particular n = s + t + 2. Let
F = {T (s, t) | s + t + 2 = n, s 1, t 1}.
Corollary 4. Let T be a tree with n 6 vertices, T = / K1,n−1 and T = / T (n −
3, 1) = T2n . Then λ1 (T ) r2 , where r2 is the maximum root of the equation
x 3 − (n + 2)x 2 + (4n − 7)x − n = 0.
The equality holds if and only if T = T (n − 4, 2).
Proof. We have from [4] that the characteristic polynomials of L(T (s, t)) and
L(T (s + 1, t − 1)) are
µ(T (s, t), x) = x(x − 1)n−4 [x 3 − (n + 2)x 2 + (2n + st + 1)x − n],
µ(T (s + 1, t − 1), x) = x(x − 1)n−4 [x 3 − (n + 2)x 2
+ (2n + (s + 1)(t − 1) + 1)x − n].
In particular,
µ(T (n − 4, 2), x) = x(x − 1)n−4 [x 3 − (n + 2)x 2 + (4n − 7)x − n].
and
µ(T (n − 5, 3), x) = x(x − 1)n−4 [x 3 − (n + 2)x 2 + (5n − 14)x − n].
J.-M. Guo / Linear Algebra and its Applications 368 (2003) 379–385 383
Let
f1 (x) = x 3 − (n + 2)x 2 + (2n + st + 1)x − n,
f2 (x) = x 3 − (n + 2)x 2 + (2n + (s + 1)(t − 1) + 1)x − n,
f (x) = x 3 − (n + 2)x 2 + (4n − 7)x − n,
g(x) = x 3 − (n + 2)x 2 + (5n − 14)x − n.
If s t, x > 0, then f1 (x) − f2 (x) = (s − t + 1)x > 0, we have
λ1 (T (s, t)) < λ1 (T (s + 1, t − 1)) (s t). (2)
Let H (s, t) denote trees of diameter 4 obtained from T (s, t) by removing the non-
pendant edge e = uv and adding a new vertex w and edges uw and vw. In particular
n = s + t + 3. Suppose s t 1. Let H = {H (s, t) | s + t + 3 = n, s 1, t 1},
then we have from Lemmas 4 and 5 that
λ1 (H (s, t)) d1 (H (s, t)) + 2 = s + 3
= d1 (H (s + 1, t − 1)) + 1 < λ1 (H (s + 1, t − 1)). (3)
By the direct computation, we have
µ(H (n − 4, 1), x) = x(x − 1)n−5
× [x 4 − (n + 3)x 3 + (5n − 4)x 2 − (6n − 10)x + n].
µ(T3n , x) = x(x − 1)n−6 (x 2 − 3x + 1)[x 3 − (n + 1)x 2 + (3n − 5)x − n].
Let
h(x) = x 4 − (n + 3)x 3 + (5n − 4)x 2 − (6n − 10)x + n,
i(x) = x 3 − (n + 1)x 2 + (3n − 5)x − n.
Then
(x − 2)i(x) − h(x) = x 2 − nx + n.
Note that when h(x) = 0, we have
(x 2 − 2x − 1)(x 2 − nx + n) = (x − 2)[x 2 − (2n − 5)x + n].
The right-hand side is easily seen to be negative when 4 n − 2 x n − 1
and since
n − 2 λ1 (H (n − 4, 1)) n − 1.
We see that at x = λ1 (H (n − 4, 1)), we have i(x) < 0. Since i(n − 1) > 0, it
now follows that λ1 (T3n ) > λ1 (H (n − 4, 1)). Since
384 J.-M. Guo / Linear Algebra and its Applications 368 (2003) 379–385
i(x) − f (x) = x 2 − (n − 2)x > 0, (x > n − 2),
we have λ1 (T3n ) < λ1 (T (n − 4, 2)). Clearly, if β(T ) = 2, then either T ∈ F or T ∈
H . From (2) and (3), we conclude that if T is a tree on n vertices with matching
number two and T = / T (n − 3, 1), then
λ1 (T ) max{λ1 (T (n − 4, 2)), λ1 (H (n − 4, 1))}.
From (1) and Theorem 1, we conclude that if T is a tree on n vertices with match-
ing number β(T ) 3, then
λ1 (T ) λ1 (Tβ(T
n
) ) λ1 (T3 ).
n
Since
λ1 (H (n − 4, 1)) < λ1 (T3n ) < λ1 (T (n − 4, 2)).
Then, we complete this proof.
Corollary 5. Let T be a tree with n 6 vertices, and let T = / K1,n−1 , T =
/ T (n −
3, 1) and T =/ T (n − 4, 2). Then λ1 (T ) r3 , where r3 is the maximum positive root
of the equation x 3 − (n + 1)x 2 + (3n − 5)x − n = 0. The equality holds if and only
if T = T3n .
Proof. If n = 6, 7, then it is easy to show this result holds.
Suppose that n 8. Since T = / K1,n−1 , we have β(T ) 2. If β(T ) = 2 and T =
/
T (n − 3, 1), T (n − 4, 2), we have from (2) and (3) that
λ1 (T ) max{λ1 (T (n − 5, 3)), λ1 (H (n − 4, 1))}.
Since for n 8, x < n − 1(x ∈ R), we have g(x) − i(x) = −x 2 + (2n − 9)x >
0. Then, for n 8, λ1 (T3n ) > λ1 (T (n − 5, 3)). Combined with λ1 (T3n ) > λ1 (H (n −
4, 1)). We have λ1 (T ) < λ1 (T3n ).
From (1) and Theorem 1, we conclude that if T is a tree on n vertices with match-
ing number β(T ) 3, then
λ1 (T ) λ1 (Tβ(T
n
) ) λ1 (T3 ),
n
and equality holds if and only if T = T3n . We complete this proof.
In particular, we have
Corollary 6. Let T be a tree on n = 2k vertices with a perfect matching. Then
√
k + 2 + k2 + 4
λ1 (T ) ,
2
and equality holds if and only if T = Tkn .
Proof. By the direct computation, we have the characteristic polynomial of
L(Tkn ) is
J.-M. Guo / Linear Algebra and its Applications 368 (2003) 379–385 385
µ(Tkn , x) = x(x 2 − 3x + 1)k−2 [x 3 − (k + 4)x 2 + (3k + 4)x − 2k]
= x(x − 2)(x 2 − 3x + 1)k−2 [x 2 − (k + 2)x + k].
By Theorem 1, we complete this proof.
Acknowledgement
The author is grateful to the anonymous referee for giving valuable suggestions
towards improving the proofs of the original version of this paper.
References
[1] W.N. Anderson, T.D. Morley, Eigenvalues of the Laplacian of a graph, Linear and Multilinear Alge-
bra 18 (1985) 141–145.
[2] D.M. Cvetkovic, M. Doob, H. Sachs, Spectra of graph-theoryand applications, VEB Deutscher Verlag
d. Wiss. Berlin, 1979; Academic Press, New York, 1979.
[3] R. Grone, R. Merris, V.S. Sunder, The Laplacian spectrum of a graph, SIAM J. Matrix Anal. Appl.
11 (2) (1990) 218–238.
[4] R. Grone, R. Merris, Ordering trees by algebraic connectivity, Graphs Combin. 6 (1990) 229–237.
[5] J.-S. Li, X.-D. Zhang, A new upper bound for eigenvalues of the Laplacian matrix of a graph, Linear
Algebra Appl. 265 (1997) 93–100.
[6] J.-S. Li, X.-D. Zhang, On the Laplacian eigenvalues of a graph, Linear Algebra Appl. 285 (1998)
305–307.
[7] R. Merris, A note on Laplacian graph eigenvalues, Linear Algebra Appl. 285 (1998) 33–35.
[8] R. Merris, Laplacian matrices of graphs: a survey, Linear Algebra Appl. 197&198 (1994) 143–176.
[9] O. Rojo, R. Soto, H. Rojo, An always non-trivial upper bound for Laplacian graph eigenvalues, Linear
Algebra Appl. 312 (2000) 155–159.
