# Properties and Applications of the Eigenvector Corresponding to the Laplacian Spectral Radius of a Graph

Authors: Haizhou Song; Qiufen Wang
Journal: Mathematical Problems in Engineering
 (2013)

---

## Abstract

We study the properties of the eigenvector corresponding to the Laplacian spectral radius of a graph and show some applications. We obtain some results on the Laplacian spectral radius of a graph by grafting and adding edges. We also determine the structure of the maximal Laplacian spectrum tree among trees withn vertices and  k pendant vertices (n,  k fixed), and the upper bound of the Laplacian spectral radius of some trees.


---

## Body

## 1. Introduction

The theory of graph spectra has been established in the 1950s and 1960s. Chung has taken the investigation of the theory of graph spectra to a new level by a 45-minute report [1] presented at the World Congress of Mathematicians in 1994, and in monographs [2]. Applications of the theory of graph spectra have also been found in the fields of electrical networks and vibration theory [3, 4]. The wide range of the applications of the theory of graph spectra has led it to become a very active field of research of graph theory over the last thirty to forty years, and large numbers of results are continuously emerging.There are many results on the (adjacency) spectral radius for different classes of graphs. Guo et al. [5] have studied the largest and the second largest spectral radius of trees with n vertices and diameter d. Guo and Shao [6] have studied the first ⌊d/2⌋+1 (where ⌊x⌋ represents the maximal integer not more than x) spectral radii of graphs with n vertices and diameter d. Wu et al. [7] have studied the spectral radius of trees on k pendant vertices.There are also many results on the Laplacian spectral radius for different classes of graphs. Hong and Zhang [8] have studied the upper and lower bounds for the Laplacian spectral radius of trees. Guo [9] has studied the second largest Laplacian eigenvalues of trees. In the paper, we further study the properties of the eigenvector corresponding to the Laplacian spectral radius of a graph and obtain some applications on the Laplacian spectral radius of trees with k pendant vertices.LetG=(V(G),E(G)) be a simple connected graph with vertex set V(G)={v1,v2,…,vn} and edge set E(G). Let dG(vi) denote the degree of vertex vi (1≤i≤n) of graph G sometimes for convenience we denote by d(vi). If D(G)=diag(d(v1),d(v2),…,d(vn)) is the diagonal matrix of the vertex degree and A(G) is the (0,1) adjacency matrix of G, then the matrix L(G)=D(G)-A(G) is called the Laplacian matrix of graph G. When G is connected, A(G) is irreducible, and, by the Perron-Frobenius theorem [10–12], the spectral radius ρ(G) is simple and there is a unique positive unit eigenvector. We refer to such an eigenvector as the Perron vector of G. It is easy to see that L(G) is a positive semidefinite M matrix and its rows sum to 0,  L(G) is singular. Hence, the eigenvalues of L(G) can be ordered as μ1(G)≥μ2(G)≥⋯≥μn(G)=0. The largest eigenvalue μ1(G) of L(G) is called the Laplacian spectral radius of the graph G, denoted by μ(G). This has been used extensively in fields such as theoretical chemistry, combinatorial optimization, and communication networks [13, 14].A pendant vertex ofG is a vertex of degree 1. Let NG(v) denote the adjacent vertex set of v in G and dv the degree of v. 𝒯n,k denotes the set of trees for n vertices and k pendant vertices (n, k fixed). The tree Tn,k is obtained from a star K1,k and k paths of almost equal length by joining each pendant vertex of K1,k to an end of one path. Obviously, 2≤k≤n-1. Assume q=[(n-1)/k], n-1=kq+r  (0≤r≤k-1); Tn,k is shown in Figure 1.Figure 1In general,Tn,n-1=K1,n-1, Tn,2=Pn, and Tn,n-2=S(1,n-3), a tree is obtained from two stars K1,n-3 and K1,1 by joining their central vertices. For example, T6,5=K1,5, T6,4=S(1,3), and T6,2 is a path of length 6 (Figure 2).Figure 2In Section2, we describe some properties of the eigenvector corresponding to the Laplacian spectral radius of a graph. Section 3 presents some applications of the eigenvector corresponding to the Laplacian spectral radius of a graph, including some results on the Laplacian spectral radius of a graph by grafting and adding edges. Then we obtain the structure of the maximal Laplacian spectrum tree among trees with n vertices and k pendant vertices (n, k fixed), and the upper bound of the Laplacian spectral radius for some trees.


## 2. Properties of the Eigenvector Corresponding to the Laplacian Spectral Radius of a Graph

For convenience, we denoteL(G) by L sometimes. Since the Laplacian matrix L(G) is a real symmetric matrix, we have the following theorem.Theorem 1.
LetG be a simple connected graph of n vertices. L(G) is the Laplacian matrix of G, with vector x∈ℛn×1. Then (1)
μ(G)=max1≤i≤nμi, where μi is the eigenvalue of L(G);(2)
μ(G)=max∥x∥=1(x′Lx);(3)
if∥x∥=1 and x′L(G)x=μ(G), then L(G)x=μ(G)x.Proof.
(
1
) It is proved by the definition.
(
2
) Since L(G) is a real symmetric matrix, there exists an orthogonal matrix P for which P-1LP=diag(μ1,μ2,…,μn)≜D, where P=(W1,W2,…,Wn). Let x=Py, so x′Lx=y′P′LPy=y′P-1LPy=y′Dy=∑i=1nμiyi2.
P is an orthogonal matrix and x=Py. Then, when ∥x∥=1, we have ∥y∥=1. Assume, without loss of generality, that μ1≤μ2≤⋯≤μn. Thus,
(1)max∥x∥=1(x′Lx)=max∥y∥=1∑i=1nμiyi2≤max∥y∥=1∑i=1n‍μnyi2=μnmax∥y∥=1∑i=1n‍yi2=μn=μ(G).
Lety=en=(0,0,…,0,1)n×1′, so we have x=Py=Wn, and then the above equality holds. Therefore, μ(G)=max∥x∥=1(x′Lx).
(
3
) Since L(G) is a real symmetric matrix, there exists an orthogonal matrix P for which P-1LP=diag(μ1,μ2,…,μn)≜D, where P=(W1,W2,…,Wn), and Wi is the eigenvector corresponding to μi of L(G). Assume, without loss of generality, that μ1≤μ2≤⋯≤μn.
Letx=Py, and then x′L(G)x=y′P′LPy=y′Dy. Since x′L(G)x=μ(G), we have x′L(G)x=y′Dy=μn=μ(G). Thus, y=en=(0,0,…,0,1)n×1′ and then x=Py=Pen=Wn. However, Wn is the eigenvector corresponding to μn of L(G), that is, L(G)Wn=μnWn. Thus, L(G)x=μ(G)x.Definition 2.
LetG be a simple connected graph, G=(V,E). If vector x∈ℛn×1 satisfies ∥x∥=1 and x′L(G)x=μ(G), then we call x the standard Laplacian spectral vector of G.Theorem 3.
LetT be a tree, and V(T)={v1,v2,…,vn}. Let L be the Laplacian matrix of T and x be the standard Laplacian spectral vector of T. Then(1)
x is a real vector;(2)
|x|>0.Proof.
(
1
) Since L is a real symmetric matrix, we have μ(T)∈R. Thus, x is a real vector.
(
2
) Suppose that |x|>0 is not established. Then there exists vertex set H={vj1,vj2,…,vjt}, which means xji=0(i=1,2,…,t), where xj corresponds to vertex vj. Since x is the standard Laplacian spectral vector of T, we have ∥x∥=1. Thus, x≠0 and there exists vertex v∈V(T) that makes xv=0 and vertex u∈NT(v) that makes xu≠0.
LetT form a root tree with v as its root vertex. NT(v)={w1,w2,…,ws}≜W. Let Ti be the subtree of T obtained from vertex wi and all its descendants. Let yv=xv=0, ywi=|xwi|(i=1,2,…,s),yj=xj when xwi≥0, and let vj be the vertex of subtree Ti, yj=-xj when xwi<0 and vj be the vertex of subtree Ti(i=1,2,…,s).
Thus, we haveywi≥0(i=1,2,…,s), ∥y∥=1 and y′Ly=x′Lx=μ(L(T))≜μ(T). By Definition 2, we know that y is the standard Laplacian spectral vector of T. Then (D-A)y=μ(T)y. We have ((D-A)y)v=(μ(T)y)v. Thus, ∑i=1sywi=0.
However,ywi≥0 and there exists i0∈{1,2,…,s} that makes wi0=u, yu>0. Therefore, ∑i=1sywi>0. This contradiction completes the proof.Theorem 4.
Letv be a vertex of tree T and v1,v2,…,vs be the pendant vertices of T that are adjacent to v. If x=(x1,x2,…,xn)′ is the standard Laplacian spectral vector of T, where xi corresponds to the vertex vi(1≤i≤n). Then xvj=xvi, 1≤i<j≤s.Proof.
x
=
(
x
1
,
x
2
,
…
,
x
n
)
′ is the standard Laplacian spectral vector of T. By Definition 2 and Theorem 1, we have L(T)x=μ(T)x. L(T)=D(T)-A(T), so (D(T)-A(T))x=μ(T)x, and then we have (dT(vi)-μ(T))xvi=xv,1≤i≤s. Therefore, we have (1-μ(T))xv1=xv, (1-μ(T))xv2=xv,…,(1-μ(T))xvs=xv. Thus, xvj=xvi, 1≤i<j≤s.Theorem 5.
Letx=(x1,x2,…,xn)′ be the standard Laplacian spectral vector of tree T, where xi corresponds to vertex vi(1≤i≤n), T=(V,E). Then (1)
for∀uv∈E(T), we have xuxv<0;(2)
∑i=1nxi=0.Proof.
(
1
) Since x is the standard Laplacian spectral vector of T, by Definition 2 we have μ(T)=x′L(T)x=∑(i,j)∈E(xi-xj)2. By Theorem 3, we have |xu|>0 and |xv|>0. Thus, xuxv≠0.
Suppose that there exists edgeuv∈E(T) such that xuxv>0. Let tree T form a root tree with r as its root vertex. Assume, without loss of generality, that vertex u is the parent node of the vertex v (Figure 3). Let T1 be the subtree of T obtained from vertex v and all its descendants, and let T1 be a k-layer tree, T1=(V1,E1) (Figure 4). Without loss of generality, we assume that xu>0, so xv>0.
Letyi=xi (vi∈V∖V(T1)), yv=-xv, and yw1=|xw1| (∀w1 are the vertices in the second layer of T1), yw2=(-1)3|xw2|(∀w2aretheverticesinthethirdlayerofT1),…,ywk-1=(-1)k|xwk-1| (∀wk-1 are the vertices in the kth layer of T1). Then ∥y∥=∥x∥=1 and we have
(2)y′L(T)y=∑(i,j)∈E‍(yi-yj)2=∑(i,j)∈E∖E1‍(xi-xj)2+∑(i,j)∈E1∖uv‍(yi-yj)2+(xu+xv)2>∑(i,j)∈E∖E1‍(xi-xj)2+∑(i,j)∈E1∖uv‍(xi-xj)2+(xu-xv)2=∑(i,j)∈E‍(xi-xj)2=μ(T).
Thus, there exists a unit vector y=(y1,y2,…,yn)′ such that μ(T)<y′L(T)y. This implies a contradiction with Theorem 1. Therefore, xuxv<0.
(
2
) Since x is the standard Laplacian spectral vector of T, we have
(3)(D(T)-A(T))x=μ(T)x.
Then
(4)(dT(vi)-μ(T))xi=∑vj∈NT(vi)‍xj.
Thus, we have
(5)∑i=1n‍(dT(vi)-μ(T))xi=∑i=1n‍∑vj∈NT(vi)‍xj.
Therefore, ∑i=1ndT(vi)xi-μ(T)∑i=1nxi=∑i=1ndT(vi)xi. So ∑i=1nxi=0.Figure 3Figure 4


## 3. Applications of the Eigenvector Corresponding to the Laplacian Spectral Radius

In this section, we present some applications of the eigenvector of the Laplacian spectral radius of a graph.Theorem 6.
Letu and v be the vertices of tree T. Denote the distance of vertices u and v by d(u,v) and d(u,v)=k, where k is an odd number and k≥3. Let G′ be the graph obtained from T by adding edge (u,v). Then μ(G′)>μ(T).Proof.
Letx=(x1,x2,…,xn)′ be the standard Laplacian spectral vector of tree T, where xi corresponds to vertex vi(1≤i≤n). Since k is an odd number and k≥3, by Theorem 5 we have xuxv<0. Thus,
(6)μ(G′)=max∥y∥=1y′L(G′)y=max∥y∥=1∑(i,j)∈E(G′)‍(yi-yj)2≥∑(i,j)∈E(G′)‍(xi-xj)2>∑(i,j)∈E(T)‍(xi-xj)2=μ(T).
Therefore, μ(G′)>μ(T).According to the well-known Courant-Weyl inequalities, we have the following lemma.Lemma 7 (see [15]).
LetG be a graph with n vertices and let G′=G+e be the graph obtained by inserting a new edge e into G. Let μi(G) and μi(G′) be the eigenvalues of the Laplacian matrix of G and G′(i=1,2,…,n), respectively. Then μ1(G′)≥μ1(G)≥μ2(G′)≥μ2(G)≥⋯≥μn(G′)=μn(G)=0.Lemma 8 (see [16]).
LetG be a connected graph for n vertices with at least one edge. Then μ(G)≥Δ(G)+1, where Δ(G) is the largest degree of the graph G, and equality holds if and only if Δ(G)=n-1.Theorem 9.
LetG be a connected graph for n vertices, and let uj be the vertex of G and v1j,v2j,…,vmjj be the pendant vertices of G adjacent to vertex uj(1≤j≤k). Let G1 be the graph obtained from G by adding ∑j=1k‍qj(1≤qj≤mj(mj-1)/2) edges, where tj edges are among v1j,v2j,…,vmjj(j=1,2,…,k). Then μ(G)=μ(G1).Proof.
IfΔ(G)=n-1, by Lemma 8 we have μ(G)=Δ(G)+1=n. However, it is clear that μ(G1)=Δ(G1)+1=n-1+1=n, so μ(G)=μ(G1). We suppose that Δ(G)≤n-2.
LetG′ be the graph obtained from G by adding ∑j=1k‍tj(tj=mj(mj-1)/2) edges, where tj edges are among v1j,v2j,…,vmjj(j=1,2,…,k). By Lemma 7, we have μ(G)≤μ(G1)≤μ(G′). To obtain the result, we only need to prove that μ(G)≥μ(G′).
LetX=(X1,X2,…,Xn)′ be the standard Laplacian spectral vector of G′, then L(G′)X=μ(G′)X. For L(G′)=D(G′)-A(G′), we have
(7)(dG′(vil)-μ(G′))Xvil=Xul+∑j=1,j≠iml‍Xvjl,222222222221≤i≤ml,1≤l≤k.
Then, for 1≤i<j≤ml and 1≤l≤k, we have
(8)(dG′(vil)-μ(G′))Xvil-(dG′(vjl)-μ(G′))Xvjl=Xvjl-Xvil
since dG′(v1l)=dG′(v2l)=⋯=dG′(vqll)=ml≤n-2. Thus,
(9)(ml-μ(G′))(Xvil-Xvjl)=Xvjl-Xvil,222222221≤i<j≤ml,1≤l≤k.
ForΔ(G′)≤n-2, by Lemma 8 we have μ(G′)>Δ(G′)+1≥ml+1. So Xvil=Xvjl, 1≤i<j≤ml, 1≤l≤k. Thus, we have
(10)μ(G)≥X′L(G)X=∑(i,j)∈E(G)‍(Xi-Xj)2=∑(i,j)∈E(G′)‍(Xi-Xj)2=X′L(G′)X=μ(G′).
That is, μ(G)≥μ(G′). This completes the proof.Theorem 10.
Letu, v be two vertices of tree T. Suppose that v1,v2,…,vs(1≤s≤dv) are some vertices of NT(v)∖(NT(u)∪{u}), and x=(x1,x2,…,xn)′ is the standard Laplacian spectral vector of T, where xi corresponds to vertex vi(1≤i≤n). Let T* be the tree obtained from T by deleting the edges (v,vi) and adding the edges (u,vi)(1≤i≤s) (Figure 5). If |xu|≥|xv|, then μ(T)<μ(T*).Figure 5Proof.
For treeT, let T form a root tree with vertex v as the parent node of vertex vi(1≤i≤s), T=(V,E). Let T1 be the subtree of T obtained from the parent node v and v1,v2,…,vs and the v1 descendants, v2 descendants,…, vs descendants, T1=(V1,E1). For tree T*,   let T* form a root tree with vertex u as the parent node of vertex vi(1≤i≤s), T*=(V*,E*). Let T1* be the subtree of T* obtained from the parent node u and v1,v2,…,vs and the v1 descendants, v2 descendants,…, and vs descendants. Let subtree T1* be a k-layer tree with vertex u as the root node. Consider E1′=E1∖{vv1,vv2,…,vvs}.
Letyi=xi(vi∈V∖V(T1)), yv=xv, yw1=-(signxu)|xw1| (forallw1 are the vertices in the second layer of T1*), yw2=(-1)2(signxu)|xw2| (forallw2 are the vertices in the third layer of T1*),…, and ywk-1=(-1)k-1(signxu)|xwk-1| (forallwk-1 are the vertices in the kth layer of T1*). Then we have ∥y∥=1 and
(11)y′L(T*)y-x′L(T)x=∑‍(i,j)∈E*(yi-yj)2-∑‍(i,j)∈E(xi-xj)2=[∑(i,j)∈E1′‍(yi-yj)2+∑(i,j)∈E*∖E1′‍(yi-yj)2]-[∑(i,j)∈E1′‍(xi-xj)2+∑(i,j)∈E∖E1′‍(xi-xj)2]=∑(i,j)∈E*∖E1′‍(yi-yj)2-∑(i,j)∈E∖E1′‍(xi-xj)2=∑i=1s‍(|xu|+|xvi|)2-∑i=1s‍(|xv|+|xvi|)2=∑i=1s‍(|xu|2-|xv|2)+2∑i=1s‍|xvi|(|xu|+|xv|)≥0.
That is, y′L(T*)y≥x′L(T)x. Thus,
(12)μ(T)=x′L(T)x≤y′L(T*)y≤max∥y∥=1y′L(T*)y=μ(T*).
Therefore, μ(T)≤μ(T*).
Ifμ(T)=μ(T*), then the equalities in (12) hold. Thus, μ(T)=y′L(T*)y=μ(T*). By Theorem 1, we have L(T*)y=μ(T*)y. Thus,
(13)μ(T*)yv=(L(T*)y)v=dv*yv-∑vi∈NT*(v)‍yi,
where dv* is the degree of vertex v of tree T*.
In addition, fromL(T)x=μ(T)x we have
(14)μ(T)xv=(L(T)x)v=dvxv-∑vi∈NT(v)‍xi=dvyv-∑vi∈NT*(v)‍xi-∑i=1s‍xi,
where dv is the degree of vertex v of tree T.
By (13) and (14), we have
(15)(μ(T*)-μ(T))xv=∑i=1s‍xi-sxv+∑vi∈NT*(v)‍(xi-yi).
Assume, without loss of generality, that xv>0.
Ifxu>0, by Theorem 5, we have
(16)(μ(T*)-μ(T))xv=∑i=1s‍xi-sxv<0,
which implies the contradiction μ(T*)<μ(T).
Ifxu<0, by Theorem 5, we have
(17)(μ(T*)-μ(T))xv=∑i=1s‍xi-sxv+∑vi∈NT*(v)‍(xi-|xi|)<0,
which implies the contradiction μ(T*)<μ(T).
Thus, if|xu|≥|xv|, then μ(T)<μ(T*).Corollary 11.
Suppose thatT* is as defined as in Theorem 10  y=(y1,y2,…,yn)T is the standard Laplacian spectral vector of T*, and then |yu|>|yv|.Proof.
Otherwise, if|yu|≤|yv|, by Theorem 10, we have μ(T*)<μ(T). This contradiction completes the proof.Corollary 12.
LetG be a simple connected graph with n vertices. Let r, s, and t be three distinct vertices, where rs∈E(G) and rt∉E(G). Let G* be the simple connected graph obtained from G by deleting the edge rs and adding the edge rt. Suppose that x=(x1,x2,…,xn)′ is the standard Laplacian spectral vector of G, where xi corresponds to the vertex vi(1≤i≤n). x*=(x1*,x2*,…,xn*)′ is the standard Laplacian spectral vector of G*, where xi* corresponds to the vertex vi*(1≤i≤n). If |xt|≥|xs|, then |xt*|>|xs*|.Proof.
Obviously,G is obtained from G* by deleting the edge rt and adding the edge rs. Assume that |xt*|≤|xs*|. Since G* is a simple connected graph, by Theorem 10 we have μ(G*)<μ(G). If |xt|≥|xs|, by Theorem 10 we have μ(G)<μ(G*). This contradiction completes the proof.Lemma 13 (see [17]).
Letu be a vertex of tree G, and for positive integers k and l let Gk,l denote the tree obtained from G by adding pendant paths of length k and l at u (Figure 6). If k≥l≥1, then μ(Gk,l)>μ(Gk+1,l-1).Figure 6Theorem 14 (see [7, 8]).
Among all the trees forn vertices and k pendant vertices, the maximal Laplacian spectral radius is obtained uniquely at Tn,k.Proof.
We have to prove that ifT∈𝒯n,k, then μ(T)≤μ(Tn,k) with equality only when T=Tn,k. Let t be the cardinality of the vertices of degree 3 or greater.
Case  1. t=0. In this case, T is a path of length n, and hence T=Tn,2. We have μ(T)=μ(Tn,2).
Case  2. t=1. The result μ(T)≤μ(Tn,k) follows from repeated use of Lemma 13, and equality holds if and only if T=Tn,k.
Case  3. t>1. Let x=(x1,x2,…,xn)T be the standard Laplacian spectral vector of T, where xi corresponds to the vertex vi (1≤i≤n). Suppose that u,v are two vertices of T of degree 3 or greater, and |xu|≥|xv|. Since T is a tree, there is a unique path between u and v, and only one of the neighbors of v, say w, is on the path. Assume {v1,v2,…,vdv-2}⊂NT(v)∖{w}. Delete the edges (v,vi) and add the edges (u,vi) (1≤i≤dv-2). Then we obtain a new tree T1*. Obviously, T1* still has k pendant vertices. By Theorem 10, we have μ(T)<μ(T1*) and the cardinality of the vertices of degree 3 or greater decreases to t-1.
Ift-1>1, repeat the above step to T1* until the cardinality is only 1. Thus, we obtain trees T2*,T3*,…,Tt-1* and μ(T1*)<μ(T2*)<⋯<μ(Tt-1*). Moreover, each Ti* has k pendant vertices. Referring to Case 2, we have μ(Tt-1*)≤μ(Tn,k). Therefore, μ(T)<μ(Tn,k).
The cases complete the proof.Theorem 15 (see [8]).
μ
(
T
n
,
k
-
1
)
<
μ
(
T
n
,
k
)
,
3
≤
k
≤
n
-
1.Proof.
The proof is obvious from Lemma13.For the sake of clarity, we identify a graph by its characteristic polynomial. LetΦ(L(G)) be the characteristic polynomial of graph G. For convenience, we denote Φ(L(G)) by Φ(G) sometimes. First, we require some lemmas.Lemma 16 (see [9]).
Lete=uv be a cut edge of the simple connected graph G. G1 and G2 are two connected branches of G-uv, where u∈V(G1), v∈V(G2). Then Φ(G)=Φ(G1)Φ(G2)-Φ(G1)Φ(Lv(G2))-Φ(G2)Φ(Lu(G1)). Here, Φ(Lv(G2)) denotes the determinant obtained by deleting the row and column for vertex v of G2 from the determinant for L(G2), and Φ(Lu(G1)) denotes the determinant obtained by deleting the row and column for vertex u of G1 from the determinant for L(G1).Lemma 17 (see [18]).
LetPn be a path with n vertices, let Pn0 be the path obtained by adding a loop on a pendant vertex in Pn, and let Pn00 be the path obtained by adding loops on the two pendant vertices in Pn. Suppose that the degree of contribution corresponding to each loop is 1 and Φ(P0)=0, Φ(P00)=1, Φ(P000)=1. Then (1)
Φ(Pn+1)=(x-2)Φ(Pn)+Φ(Pn-1),(n≥1),(2)
xΦ(Pn0)=Φ(Pn+1)+Φ(Pn),(3)
Φ(Pn)=xΦ(Pn-100), (n≥1),(4)
Φ(Pn)=(x/x2-4x)(an-bn), where a=(x-2+x2-4x)/2 and b=(x-2-x2-4x)/2.From Lemma16, by induction we can obtain the following lemma.Lemma 18.
LetG1,G2,…,Gs,G be s+1 disjoint simple connected graphs, where vi∈Gi(i=1,2,…,s) and v∈G. Let Hs be the graph obtained from G1,G2,…,Gs and G by adding new edges vv1,vv2,…,vvs. Then
(18)Φ(Hs)=Φ(G)∏i=1s‍[Φ(Gi)-Φ(Lvi(Gi))]-Φ(Lv(G))×∑i=1s‍[Φ(Gi)∏j=1,j≠is‍(Φ(Gj)-Φ(Lvj(Gj)))].From Lemmas16, 17, and 18, we have the following theorem.Theorem 19.
The characteristic polynomial ofTn,k(2≤k≤n-1) is
(19)Φ(Tn,k)=[Φ(Pq+1)-Φ(Pq0)]r-1[Φ(Pq)-Φ(Pq-10)]k-r-1×{x[Φ(Pq+1)-Φ(Pq0)][Φ(Pq)-Φ(Pq-10)]2-r[Φ(Pq)-Φ(Pq-10)]Φ(Pq+1)2-(k-r)Φ(Pq)[Φ(Pq+1)-Φ(Pq0)]},
where q=[(n-1)/k], n-1=kq+r(0≤r≤k-1), and Pq is a path of length q.As for the Laplacian spectral radius ofTn,k, we only need to consider the greatest root of
(20)x[Φ(Pq+1)-Φ(Pq0)][Φ(Pq)-Φ(Pq-10)]-r[Φ(Pq)-Φ(Pq-10)]Φ(Pq+1)-(k-r)Φ(Pq)[Φ(Pq+1)-Φ(Pq0)]=0.In general, the Laplacian spectral radius is difficult to calculate although the characteristic polynomial can be identified by Chebvshev polynomials. Thus, we only give some results in some cases.Lemma 20.
For a univariate cubic equationx3+kx2+mx+n=0, we can obtain the roots as follows:
(21)x1=-q2+(q2)2+(p3)33x2=+-q2-(q2)2+(p3)33-k3,x2=ω-q2+(q2)2+(p3)33x2=+ω2-q2-(q2)2+(p3)33-k3,x3=ω2-q2+(q2)2+(p3)33x2=+ω-q2-(q2)2+(p3)33-k3,
where p=-(1/3)k2+m, q=(2/27)k3-(1/3)km+n and ω=e2πi/3.Proof.
The lemma is easy to prove.Theorem 21.
If[n/2]≤k≤n-1, then
(22)μ(Tn,k)=k+43+2k2-k+43cosθ3,θ=arccos2k3-3k2-48k+27n-162(k2-k+4)3/2,222222222222222222222(0<θ<π).
Moreover, if k=n-1, then μ(Tn,n-1)=n.Proof.
In this case, for[n/2]≤k≤n-1,q=1. By (20), we have
(23)x[Φ(Pq+1)-Φ(Pq0)][Φ(Pq)-Φ(Pq-10)]-r[Φ(Pq)-Φ(Pq-10)]Φ(Pq+1)-(k-r)Φ(Pq)[Φ(Pq+1)-Φ(Pq0)]=0.
Hence, x3-(k+4)x2+(3k+4)x-(k+r+1)=0.
Letf(x)=x3-(k+4)x2+(3k+4)x-(k+r+1), and then we have1o
forf(0)=-(k+r+1)<0 and f(1)=k-r>0, and thus f(x) has a root in (0,1),2o
forf(1)>0 and f(k)=-k(k-3)-r-1<0, and thus f(x) has a root in (1,k),3o
forf(k)<0 and f(+∞)>0, and thus f(x) has a root in (k,+∞).Therefore, the equation has three different real roots.
Letx=y+(k+4)/3, and then the equation can translate to y3+py+q=0, where p=-(1/3)(k2-k+4) and q=-(1/27)(2k3-3k2-21k+27r+11).
Lets=-q/2+-Δi=∥s∥eiθ, where Δ=(q/2)2+(p/3)3<0. Then(24)∥s∥=∥-q2+-Δi∥=(-q2)2+(-Δ)=q24-q24-p327=127(k2-k+4)3/2,θ=arccos-q/2∥s∥=arccos2k3-3k2-21k+27r+112(k2-k+4)3/2,22222222222222222222222222222(0<θ<π).
Thus, based on the Lemma 20, we can obtain three roots:
(25)x1=-q2+-Δi3+-q2--Δi3+k+43=∥s∥eiθ3+∥s∥e-iθ3+k+43=k2-k+43eiθ/3+k2-k+43e-iθ/3+k+43=k+43+2k2-k+43cosθ3,(26)x2=ω-q2+-Δi3+ω2-q2--Δi3+k+43=ω∥s∥eiθ3+ω2∥s∥e-iθ3+k+43=k2-k+43eiθ/3e2iπ/3+k2-k+43e-iθ/3e4iπ/3+k+43=k+43+2k2-k+43cos(θ3+2π3),(27)x3=ω2-q2+-Δi3+ω-q2--Δi3+k+43=ω2∥s∥eiθ3+ω∥s∥e-iθ3+k+43=k2-k+43eiθ/3e4iπ/3+k2-k+43e-iθ/3e2iπ/3+k+43=k+43+2k2-k+43cos(2π3-2θ3).
For 0<θ<π, then cos(θ/3)>cos(θ/3+2π/3) and cos(θ/3)>cos(2π/3-θ/3). Thus, x1>x2, x1>x3. So the largest root of the univariate cubic equation is
(28)μ(Tn,k)=k+43+2k2-k+43cosθ3,θ=arccos2k3-3k2-21k+27r+112(k2-k+4)3/2,222222222222222222222(0<θ<π).
For r=n-1-k, we have
(29)μ(Tn,k)=k+43+2k2-k+43cosθ3,θ=arccos2k3-3k2-48k+27n-162(k2-k+4)3/2,222222222222222222222(0<θ<π).
If k=n-1, then it is easy to prove that f(n)=0. Thus, μ(Tn,n-1)=n.From Theorems14, 15, and 21, we have the following corollaries.Corollary 22.
LetT be a tree for n vertices. Then μ(T)≤n and equality holds if and only if T=Tn,n-1(K1,n-1), the star with n vertices.Corollary 23.
LetT be a tree for n vertices with n≥4 and T≇Tn,n-1. Then
(30)μ(T)≤n+23+2n2-5n+103cosθ3,222θ=arccos2n3-15n2+15n+522(n2-5n+10)3/2,22222222222222222222(0<θ<π)
and equality holds if and only if T=Tn,n-2(S(1,n-3)).Corollary 24.
LetT be a tree for n vertices. Let M(T) denote one maximum matching of T and suppose that |M(T)|=i. Then
(31)μ(T)≤n+4-i3+2n2-(2i+1)n+i2+i+43cosθ3,(32)θ=arccos2n3-(6i+3)n2+(6i2+6i-21)n-2i3-3i2+48i-162[n2-(2i+1)n+i2+i+4]3/2222222222222222222222222222222222222222222(0<θ<π),
and equality holds if and only if T=Tn,n-i.Proof.
Letk denote the cardinality of the pendant vertices of T. For |M(T)|=i, we have k≤i+n-2i=n-i. By Theorems 14 and 15, we have μ(T)≤μ(Tn,k)≤μ(Tn,n-i), and equality holds if and only if T=Tn,n-i.
T
n
,
n
-
i is shown in Figure 7. Since i≤n/2,n-i≥n/2≥[n/2], by Theorem 21 we have
(33)μ(T)≤n+4-i3+2n2-(2i+1)n+i2+i+43cosθ3,(34)θ=arccos2n3-(6i+3)n2+(6i2+6i-21)n-2i3-3i2+48i-162[n2-(2i+1)n+i2+i+4]3/2,2222222222222222222222222222222222222222222(0<θ<π).Figure 7Corollary 25.
LetT be any tree for n=2i vertices and |M(T)|=i. Then
(35)μ(T)≤i+43+2i2-i+43cosθ3,2222θ=arccos2i3-3i2+6i-162(i2-i+4)3/2,2222222222222222222(0<θ<π)
and equality holds if and only if T=Tn,n-i.



---

*Source: 524162-2013-08-29.xml*