# The Largest Laplacian Spectral Radius of Unicyclic Graphs with

Authors: Haixia Zhang
Journal: Journal of Applied Mathematics
 (2013)

---

## Abstract

We identify graphs with the maximal Laplacian spectral radius among all unicyclic graphs withn vertices
and diameter d.


---

## Body

## 1. Introduction

Following [1], letG=(V(G),E(G))be a simple undirected graph onnvertices and m edges (son=|V(G)|is its order and m=|E(G)|is its size). Forv∈V(G),dG(v)ord(v)denotes the degree ofvandN(v)denotes the set of all neighbors of vertexv. A pendant vertex is a vertex of degree 1 and a pendant edge is an edge incident with a pendant vertex. LetPV(G)={v:dG(v)=1}. For two verticesuandv(u≠v), the distance between u and v is the number of edges in the shortest path joining u and v. The diameter of a graph is the maximum distance between any two vertices ofG. LetP=v0v1,…,vs (s≥1) be a path ofGwithd(v1)=⋯=d(vs-1)=2(unlesss=1). Ifd(v0),d(vs)≥3, then we call P an internal path of G; ifd(v0)≥3andd(vs)=1, then we callPa pendant path ofG; if the subgraph induced byV(P)inGisPitself, that is,G[V(P)]=P, then we callPan induced path. Obviously, the shortest path between any two distinct vertices ofGis an induced path. We will useG-v,G-uvto denote the graph obtained fromGby deleting a vertexv∈V(G), or an edgeuv∈E(G), respectively (this notation is naturally extended if more than one vertex, or edge, is deleted).Denote byCnandPnthe cycle and the path with n vertices, respectively. We callGa unicyclic graph if m=n, where n is the number of vertices andmis the number of edges. We will use𝒞ndto denote the sets of all unicyclic graphs withnvertices and diameterd. Let⋄nkbe a graph of ordernobtained from the cycleC4by attachingn-d-2pendant edges and a path of lengthd-k-1at one vertex of the cycle, and a path of lengthk-1to another nonadjacent vertex of the cycle respectively, where 0≤k-1≤d-k-1.LetL(G)=D(G)-A(G)be the Laplacian matrix, whereD(G)is the diagonal matrix andA(G)is the adjacency matrix. The matrixL(G)is real symmetric and positive semidefinite; the eigenvalues of L(G) can be arranged asμ1(G)≥⋯≥μn(G)=0, where the largest eigenvalueμ1(G)is called the Laplacian spectral radius ofG.The investigation on the Laplacian spectral radius of graphs is an important topic in the theory of graph spectra. Recently, the problem concerning graphs with maximal Laplacian spectral radius of a given class of graphs has been studied extensively. Li et al. [2] determined those graphs which maximized Laplacian spectral radius among all bipartite graphs with (edge-) connectivity at mostkand characterized graphs of ordernwithkcut-edges, having Laplacian spectral radius equal ton. X. L. Zhang and H. P. Zhang [3] studied the largest Laplacian spectral radius of the bipartite graphs with n vertices andkcut edges and the bicyclic bipartite graphs, respectively. The Laplacian spectral radius of unicyclic graphs has been studied by many authors (see [4–6]). Liu et al. [7] determined the graphs with the largest Laplacian spectral radii among all unicyclic graphs and bicyclic graphs with n vertices andkpendant vertices. Hua et al. [8] determined extremal graphs with maximal Laplacian spectral radius among all unicyclic graphs with given order and given pendant vertices number.In 2007, Liu et al. [9] determined graphs with the maximal spectral radius among all unicyclic graphs with n vertices and diameterd. In 2012, He and Li [6] identified graphs with the maximal signless Laplacian spectral radius among all unicyclic graphs with n vertices of diameterd. Next, Guo [4] considered the Laplacian spectral radius of unicyclic graphs with fixed diameter and proposed Conjecture 1.In this paper, we prove the conjecture as Theorem1.Theorem 1.
LetGbe a graph in𝒞nd,3≤d≤n-2. Consider the following.(i)
Ifdis odd,μ1(G)≤μ1(⋄n⌊d/2⌋)and equality holds if and only ifG≅⋄n⌊d/2⌋.(ii)
Ifdis even andn-d-2=0,1,μ1(G)≤μ1(⋄n⌊d/2⌋)and equality holds if and only ifG≅⋄n⌊d/2⌋.(iii)
Ifdis even andn-d-2≥2,μ1(G)≤μ1(⋄n⌊d/2⌋-1)and equality holds if and only ifG≅⋄n⌊d/2⌋-1.The rest of this paper is organized as follows. In Section2, we present some notations and lemmas which will be used later on. In Section 3, we determine graphs with the largest Laplacian spectral radius among all unicyclic graphs withnvertices and diameterd.


## 2. Lemmas

In this section, we list some lemmas which will be used to prove our main results.Lemma 2 (see [10]).
Suppose thatu,vare two distinct vertices of a connected graphG. LetGtbe the graph obtained from G by attachingtnew paths vvi1vi2,…,viqi(i=1,2,…,t)at v. Let X=(x1,x2,…,xn)T, where xi corresponds to the vertexvi(1≤i≤n), be a unit eigenvector of Gt corresponding to μ1(Gt)≥4. Let
(1)Gu=Gt-vv11-vv21-⋯-vvt1+uv11+uv21+⋯+uvt1.
If|xu|≥|xv|, thenμ1(Gu)≥μ1(Gt). Further, if|xu|>|xv|, thenμ1(Gu)>μ1(Gt).Lemma 3 (see [10]).
Letuvbe a pendant edge of a connected graphGwithn≥2vertices and let vbe a pendant vertex. LetG1,G2,…,Gk(k≥2)bekdisjoint connected graphs and let vibe a vertex of Gi(i=1,2,…,k). LetG′be the graph obtained by addingknew edges vv1,vv2,…,vvk among G,G1,G2,…,Gk. Let
(2)G*=G′-vv1-vv2-⋯-vvk+uv1+uv2+⋯+uvk.
(i)
Ifn=2, thenμ1(G*)=μ1(G′).
(ii)
Ifn≥3, thenμ1(G*)≥μ1(G′), with equality if and only if eitherμ1(G*)=μ1(G)or there exists somei(1≤i≤k)such thatμ1(G*)=μ1(Gi).Letvbe a vertex of a connected graphGwith at least two vertices. Let Gk,l(l≥k≥1) be the graph obtained fromGby attaching two new paths P:v(=v0)v1v2,…,vk and Q:v(=v0)u1u2,…,ul of length k and l, respectively, at v, where u1,u2,…,ul and v1,v2,…,vk are distinct new vertices. Let Gk-1,l+1=Gk,l-vk-1vk+ulvk.Lemma 4 (see [11]).
LetGbe a connected graph onn≥2vertices andvbe a vertex ofG. LetGk,lbe the graph defined as previously mentioned. Ifl≥k≥1, thenμ1(Gk-1,l+1)≤μ1(Gk,l), with equality if and only if there exists a unit eigenvector ofGk,lcorresponding toμ1(Gk,l)taking the value0on vertexv.Lemma 5 (see [1]).
LetG′be a graph obtained by deleting an edge from the graphG. Then μi(G)≥μi(G′)≥μi+1(G), i=1,…,n-1.LetS3ibe a graph obtained from the cycleC3by attaching i pendant edges at one vertex of the cycleC3.Lemma 6 (see [5]).
LetGbe a unicyclic graph onnvertices; thenμ1(G)≥μ1(Cn); whenn≠4, the equality holds if and only ifG≅Cn; whenn=4, the equality holds if and only ifG≅C4,G≅S31.Lemma 7.
LetGbe a connected graph with at least one edge, let Δ(G) be its maximal degree, and let di be the degree of vertexviandmi=∑vj∈N(vi)‍dj/di; then(i)μ1(G)≥Δ(G)+1; the equality holds if and only ifΔ(G)=n-1 [12];(ii)μ1(G)≤max{di+mi∣vi∈V(G)}; the equality holds if and only ifGis regular or semiregular bipartite graph [13].LetLvi(G)be the principal submatrix obtained fromL(G)by deleting the corresponding row and column ofvi. Generally, letLS(G)be the principal submatrix obtained fromL(G)by deleting the corresponding rows and columns of all vertices of S. For any square matrix B, denote by Φ(B)=Φ(B,x)=det(xI-B) the characteristic polynomial of B. In particular, if B=L(G), we write Φ(L(G)) by Φ(G) for convenience. If G=u, then suppose that Φ(Lu(G))=1.LetG=G1u:vG2be the graph obtained by joining the vertexuof the graphG1to the vertex ofvof the graphG2by an edge. We callGa connected sum ofG1atuandG2atv.Lemma 8.
LetG1andG2be two graphs. If Φ(G1)>Φ(G2) for x≥μ1(G2), then μ1(G1)<μ1(G2). (In general, let f(x) and g(x) be polynomials with positive leading coefficients. If f(x)>g(x) for x≥μ1(g(x)), then μ1(f(x))<μ1(g(x)), where μ1(g(x)) and μ1(f(x)) are the largest roots of g(x)=0 and f(x)=0, resp.)Proof.
Ifμ1(G1)≥μ1(G2), thenΦ(G1)|x=μ1(G1)=0,Φ(G2)|x=μ1(G1)≥0, a contradiction.Lemma 9 (see [14]).
LetG=G1u:vG2be a connected sum ofG1atuandG2atv; then
(3)Φ(G)=Φ(G1)Φ(G2)-Φ(G1)Φ(Lv(G2))-Φ(G2)Φ(Lu(G1)).Lemma 10 (see [14]).
LetGbe a connected graph withnvertices which consists of a subgraphHand n-|V(H)| distinct pendant edges (not in H) attaching to a vertexvinH. Then
(4)Φ(G)=(x-1)n-|V(H)|Φ(H)-(n-|V(H)|)x(x-1)n-|V(H)|-1Φ(Lv(H)).Lemma 11 (see [15]).
LetDn(n≥1)be the matrix obtained fromL(Pn+2)by deleting the rows and columns corresponding to two pendant vertices ofPn+2; suppose thatΦ(D0)=1,Φ(D-n)=0; then(i)
xΦ(Dn-1)=Φ(Pn);(ii)
Φ(Dn+1)=(x-2)Φ(Dn)-Φ(Dn-1);(iii)
Φ(Dm+1)Φ(Dn)-Φ(Dm)Φ(Dn+1)=Φ(Dm)Φ(Dn-1)-Φ(Dm-1)Φ(Dn), (n,m≥1);(iv)
Φ(Cn)=Φ(Dn)-Φ(Dn-2)+2(-1)n+1.From Lemma11(i), all eigenvalues ofDnare2+2cos(iπ/(n+1)), where1≤i≤n. Other characterizations ofΦ(Dn)can be shown below.Lemma 12.
LetDn(n≥1)be the matrix as above. Consider the following.(i)
Ifn≥1, thenΦ(Dn)>Φ(Dn-1)whenx≥4.(ii)
Ifn≥1, thenΦ(Dn)>2Φ(Dn-1)whenx≥5.(iii)
Φ(Dm)Φ(Dn)-Φ(Dm-1)Φ(Dn+1)=Φ(Dn-m), where0≤m≤n.Proof.
From Lemma11(ii), it is easy to prove (i) and (ii) by introduction onn.
By Lemma11(iii), we have
(5)Φ(Dm)Φ(Dn)-Φ(Dm-1)Φ(Dn+1)=Φ(Dm-1)Φ(Dn-1)-Φ(Dm-2)Φ(Dn)=Φ(Dm-2)Φ(Dn-2)-Φ(Dm-3)Φ(Dn-1)=⋯=Φ(D0)Φ(Dn-m)-Φ(D-1)Φ(Dn-m+1)=Φ(Dn-m)
as desired.Lemma 13.
Suppose thatu,vare two adjacent vertices of the cycleCq, whereqis even. LetHk,l(l≥k≥1) be the graph obtained fromCqby attaching two new paths P:v(=v0)v1v2,…,vk and Q:u(=u0)u1u2,…,ul of length k and l at v and u, respectively, where u1,u2,…,ul and v1,v2,…,vk are distinct new vertices. Let Hk-1,l+1=Hk,l-vk-1vk+ulvk. Then μ1(Hk-1,l+1)<μ1(Hk,l).Proof.
Using Lemma9, we have
(6)Φ(Hk-1,l+1)-Φ(Hk,l)=x[Φ(Lvk-1(Hk-1,l))-Φ(Lul(Hk-1,l))]=x{[(x-1)Φ(Lvk-1,ul(Hk-1,l))-Φ(Lvk-1,ul,ul-1(Hk-1,l))]-[(x-1)Φ(Lul,vk-1,(Hk-1,l))-Φ(Lul,vk-1,vk-2(Hk-1,l))]}=⋯=x[bk,l(x)-ak,l(x)],
where
(7)ak,l(x)=[Φ(Cq)-2Φ(Dq-1)+Φ(Dq-2)]Φ(Dl-k)-[Φ(Dq-1)-Φ(Dq-2)]Φ(Dl-k-1),bk,l(x)=[Φ(Dq-1)-Φ(Dq-2)]Φ(Dl-k+1)-Φ(Dq-2)Φ(Dl-k).
From Lemmas11(ii) and 11(iv), (6) becomes
(8)Φ(Hk-1,l+1)-Φ(Hk,l)=xΦ(Dl-k)[(x-2)Φ(Dq-2)-2Φ(Dq-3)+2],
which is greater than 0 whenx≥4by Lemma 12(i). And μ1(Hk,l)>4follows from Lemma 7(i). Thusμ1(Hk-1,l+1)<μ1(Hk,l)holds by Lemma 8.ForG∈𝒞nd, we haven≥3and 1≤d≤n-2. If d=1, then G≅C3. If d=2, then G≅C4, G≅C5 or G≅S3n-3. By Lemma 7, μ1(S3n-3) has the largest Laplacian spectral radius.Therefore, in the following, we assume that3≤d≤n-2.LetH0be the unicyclic graph of orderd+2shown in Figure 1. LetH0(p2,…,pd,pd+2)be a graph of ordernobtained fromH0by attachingpipendant vertices to eachvi∈V(H0)∖{v1,vd+1}, respectively, wherepd+2=0whenk=1ork=d. Denote that
(9)ℋ~nd={H0(p2,…,pd,pd+2):∑i=2d‍pi+pd+2=n-d-2},ℋ-nd={H0(0,…,0,pi,0,…,0)=H0(pi):pi=n-d-2}.(a)
(b)Lemma 14.
LetG∈ℋ~nd. Then there is a graph G*∈ℋ-nd such that μ1(G*)≥μ1(G).Proof.
LetG∈ℋ~nd∖ℋ-ndand let X=(x1,x2,…,xn)Tbe a unit eigenvector of μ1(G), where xi corresponds to the vertexvi(1≤i≤n). Lett=|{pi:pi≠0}|. Thent≥2. Letpi,pj≠0, i<j. Assume, without loss of generality, that|xi|≥|xj|. LetN(vj)⋂‍PV(G)={u1,u2,…,upj}. Let
(10)G1*=G-vju1-⋯-vjupj+viu1+⋯+viupj.
By Lemma 2, we haveμ1(G*)≥μ1(G). Note thatG1∈ℋ-ndfort=2andG1∈ℋ~nd∖ℋ-ndfort>2. If t>2, then we will useG1*to repeat the above step until the cardinality ofpi, being nonzero, is only one. So we haveG2*,G3*,…,Gt-1*andμ1(G2*)≤μ1(G3*)≤⋯≤μ1(Gt-1*). Note thatGt-1*∈ℋ-nd, and hence the lemma holds.Lemma 15.
For anyG∈ℋ-nd,μ1(G)≤μ1(H0(pk+1)), where0≤k-1≤d-k; the equality holds if and only ifG≅H0(pk+1).Proof.
Suppose thatn-d-2=t. If t=0, the result is obvious.
Ift≥1, by Lemma 7, we have
(11)μ1(G)<max{max{di+mi∣vi∈V(G)}∣G∈ℋ-nd,i∉{d+2,k,k+1}max{di+mi∣vi∈V(G)}∣G∈ℋ-nd}=t+2+2+3+tt+2≤t+4=Δ(H0(pk+1))+1<μ1(H0(pk+1)).
Case
1.
k
-
1
<
d
-
k.
Wheni=d+2, letN(vi)⋂‍PV(G)={u1,u2,…,ut}. Let
(12)G*={H0(pi)-viu1-⋯-viut+vku1+⋯+vkut,hhhhhhhhhhhhhhhhhhhhhhhhhhl|xk|≥|xi|,H0(pi)-vk-1vk+vk-1vi,hhhhhhhhhhhhhhhhhhhhhhhhhhl|xk|<|xi|.
Then, in all cases,G*≅H0(pk). Thus by Lemma 2,μ1(H0(pd+2))≤μ1(H0(pk)).
Next, we show thatΦ(H0(pk))>Φ(H0(pk+1))forx≥μ1(H0(pk+1)). BecauseH0-vk≅Pk-1⋃‍Pd-k+2, we can getΦ(H0)in which the rows and columns correspond to vertices as the ordering v1,…,vk-1,vd+2,vk+1,vk+2,…,vd+1. Furthermore, letE11=[ei,j]be a square matrix of orderk-1, whereek-1,k-1=1andei,j=0wheneveri≠k-1andj≠k-1; letFkk=[fi,j]be a square matrix of orderd-k+2, wherefk,k=1andfi,j=0wheneveri≠kandj≠k. Then
(13)Lvk(H0)=(L(Pk-1)+E1100L(Pd-k+2)+F11+F22).
Hence,
(14)Φ(Lvk(H0))=Φ(L(Pk-1)+E11)Φ(L(Pd-k+2)+F11+F22).
In order to simplify the notation, we denoteΦ(L(Pk-1)+E11)andΦ(L(Pd-k+2)+F11+F22)by fk-1,1(x) andfd-k+2,2(x), respectively. Similarly,
(15)Φ(Lvk+1(H0))=Φ(L(Pd-k)+E11)Φ(L(Pk+1)+F11+F22)=fd-k,1(x)fk+1,2(x).
In general, by Lemma 11(ii), we have
(16)fn1,1(x)=Φ(Dn1)+Φ(Dn1-1),fn2,2(x)=(x-1)(x-3)Φ(Dn2-2)-(2x-3)Φ(Dn2-3).
Hence, by Lemma12(iii),
(17)Φ(Lvk+1(H0))-Φ(Lvk(H0))=fd-k,1(x)fk+1,2(x)-fk-1,1(x)fd-k+2,2(x)=(x-1)(x-3)×[Φ(Dk-1)Φ(Dd-k-1)-Φ(Dk-2)Φ(Dd-k)]+(2x-3)[Φ(Dk-1)Φ(Dd-k-1)-Φ(Dk-2)Φ(Dd-k)]=x(x-2)Φ(Dd-2k).
From (17) and Lemma 10,
(18)Φ(H0(pk))-Φ(H0(pk+1))=t(x-2)(x-1)t-1x2Φ(Dd-2k)>0
holds forx≥μ1(H0(pk+1)).
Thusμ1(H0(pk))<μ1(H0(pk+1))follows from Lemma 8.
Case
2.
k
-
1
=
d
-
k.
First note thatH0(pk)≅H0(pk+1).
Next, sinceH0-vd+2=Pd+1, we can deriveΦ(Lvd+2(H0))in which the rows and columns correspond to vertices as the orderingv1,…,vk-1,vk,vk+1,…,vd+1. Then
(19)Φ(Lvd+2(H0))=[Φ(Dk-1)+Φ(Dk-2)]×[(x2-5x+5)Φ(Dk-1)-(2x-5)Φ(Dk-1)]-[Φ(Dk-2)+Φ(Dk-3)]×[(x-2)Φ(Dk-1)-2Φ(Dk-2)].
Combining Lemma10 with (15) and (19), we get
(20)Φ(H0(pd+2))-Φ(H0(pk+1))=t(x-1)t-1xΦ(Dk-2)[(x-2)Φ(Dk-1)-2Φ(Dk-2)],
which is greater than 0 whenx≥μ1(H0(pk+1))by Lemma 12(i). Thus, by Lemma 8, μ1(H0(pd+2))<μ1(H0(pk+1)) holds. Hence, the proof is completed.LetΔnkbe a graph of ordernobtained from a triangle by attachingn-d-2pendant edges and a path of length d-k at one vertex of the triangle, and a path of length k-1 to another vertex of the triangle, respectively, where0≤k-1≤d-k.Lemma 16.
μ
1
(
Δ
n
k
-
1
)
<
μ
1
(
Δ
n
k
), where2≤k≤⌈d/2⌉.Proof.
Suppose thatn-d-2=t; by Lemma 7(i),μ1(Δnk)>t+4. LetH*=H0-v1; by Lemma 9,
(21)Φ(Δd+2k-1)-Φ(Δd+2k)=x[Φ(Lv2(H*))-Φ(Lvd+1(H*))]=x[(x-1)Φ(Lv2,vd+1(H*))-Φ(Lv2,vd+1,vd(H*))-(x-1)Φ(Lvd+1,v2(H*))+Φ(Lvd+1,v2,v3(H*))]=⋯=x[gd,k(x)-fd,k(x)],
where
(22)fd,k(x)=(x3-8x2+18x-8)Φ(Dd-2k+1)-(x2-5x+5)Φ(Dd-2k),gd,k(x)=(x2-5x+5)Φ(Dd-2k+2)-(x-2)Φ(Dd-2k+1).
By Lemmas 10 and 11(ii) and (15) and (21),
(23)Φ(Δnk-1)-Φ(Δnk)=(x-1)t[Φ(Δd+2k-1)-Φ(Δd+2k)]-tx(x-1)t-1[Φ(Lvk(Δd+2k-1))-Φ(Lvk+1(Δd+2k))]=(x-1)tx2(x-4)Φ(Dd-2k+1)-tx(x-1)t-1×[fd-k+1,1(x)fk,2(x)-fd-k,1(x)fk+1,2(x)]=x2(x-1)t-1×[(x-1)(x-t-4)Φ(Dd-2k+1)+t(x-2)Φ(Dd-2k)]>0
forx≥μ1(Δnk).
Soμ1(Δnk-1)<μ1(Δnk)follows from Lemma 8.In view of Lemma16, the next corollary is obvious.Corollary 17.
μ
1
(
Δ
n
k
)
≤
μ
1
(
Δ
n
⌈
d
/
2
⌉
), where1≤k≤⌈d/2⌉; the equality holds if and only ifΔnk≅Δn⌈d/2⌉.LetU0 be the unicyclic graph of order d+2 shown in Figure 1. LetU0(p2,…,pd,pd+2)be a graph of ordernobtained fromU0by attachingpipendant vertices to eachvi∈V(U0)∖{v1,vd+1}, respectively. Denote
(24)𝒰~nd={U0(p2,…,pd,pd+2):∑i=2d‍pi+pd+2=n-d-2},𝒰-nd={U0(0,…,0,pi,0,…,0)=U0(pi):pi=n-d-2}.Lemma 18.
LetG∈𝒰~nd. Then there is a graphG*∈𝒰-ndsuch thatμ1(G*)≥μ1(G).Proof.
The proof is similar to that of Lemma14.Lemma 19.
For anyG∈𝒰-nd,μ1(G)≤μ1(U0(pk+2)), where0≤k-1≤d-k-1; the equality holds if and only ifG≅U0(pk+2).Proof.
Suppose thatn-d-2=t. Ift=0, the result is trivial.
Ift≥1, by Lemma 7, we have
(25)μ1(G)<max{max{di+mi∣vi∈V(G)}∣G∈𝒰-nd,i∉{d+2,k,k+1,k+2}{max{di+mi∣vi∈V(G)}∣G∈𝒰-nd,}=t+2+2+3+tt+2≤t+4=Δ(U0(pk+2))+1<μ1(U0(pk+2)).
Case
1. i=k.
Ifk-1=d-k-1,U0(pk)≅U0(pk+2).
Ifk-1<d-k-1, we can obtainΦ(Lvk+2(U0))in which the rows and columns correspond to vertices as the orderingvd+2,vk+1,vk,…,v1,vk+3,…,vd+1. Then by Lemma 11(ii),
(26)Φ(Lvk+2(U0))=(x-2)[(x2-4x+2)Φ(Dk-1)-2(x-1)Φ(Dk-2)]×[Φ(Dd-k-1)+Φ(Dd-k-2)].
Similarly,
(27)Φ(Lvk(U0))=(x-2)[(x2-4x+2)Φ(Dd-k-1)-2(x-1)Φ(Dd-k-2)]×[Φ(Dk-1)+Φ(Dk-2)].
Combining the two equations above with Lemmas 10 and 12(iii), we get
(28)Φ(U0(pk))-Φ(U0(pk+2))=tx(x-1)t-1[Φ(Lvk+2(U0))-Φ(Lvk(U0))]=tx2(x-2)2(x-1)t-1Φ(Dd-2k-1)>0
forx≥μ1(U0(pk+2)).
From Lemma8,μ1(U0(pk))<μ1(U0(pk+2))holds.
Case
2. i=k+1, d+2.
From Lemma7, whent≥2, we have
(29)μ1(U0(pk+1))<max{di+mi∣vi∈V(U0(pk+1))}=t+2+3+3+tt+2≤t+4=Δ(U0(pk+2))+1<μ1(U0(pk+2)).
Fort=1, we can obtainΦ(Lvk+1(U0))in which the rows and columns correspond to vertices as the orderingv1,…,vk-1,vk,vd+2,vk+2,…,vd+1. Then
(30)Φ(Lvk+1(U0))=[Φ(Dk-1)+Φ(Dk-2)]f(x)-[Φ(Dk-2)+Φ(Dk-3)]g(x)=[(x-2)g(x)-h(x)]Φ(Dk-1)-[2g(x)+h(x)]Φ(Dk-2),
where
(31)f(x)=(x3-7x2+14x-7)Φ(Dd-k-1)-(2x2-9x+7)Φ(Dd-k-2),g(x)=(x-1)(x-3)Φ(Dd-k-1)-(2x-3)Φ(Dd-k-2),h(x)=(x-3)g(x)-f(x)=(x-2)Φ(Dd-k-1)-2Φ(Dd-k-2).
By (26) and (30),
(32)Φ(Lvk+2(U0))-Φ(Lvk+1(U0))=x{(x-1)Φ(Dd-k-2)[(x-3)Φ(Dk-1)-2Φ(Dk-2)]-Φ(Dd-k-1)Φ(Dk-2)}.
From Lemmas 11(ii) and 12(i), whenx≥5,
(33)(x-1)Φ(Dd-k-2)-Φ(Dd-k-1)=Φ(Dd-k-2)+Φ(Dd-k-3)>0,(x-3)Φ(Dk-1)-3Φ(Dk-2)={(x2-5x+3)Φ(Dk-2)-(x-3)Φ(Dk-3)>0ifk≥2,x-3>0ifk=1
hold (since(x2-5x+3)-(x-3)=x2-6x+6>0forx≥5).
By Lemma9 and (32), whenx≥5,
(34)Φ(U0(pk+1))-Φ(U0(pk+2))=x[Φ(Lvk+2(U0))-Φ(Lvk+1(U0))]>0.
From Lemma 8,μ1(U0(pk+1))<μ1(U0(pk+2))holds.
Hence, we complete the proof.Let⋄nkbe a graph of ordernobtained from the cycleC4by attaching n-d-2pendant edges and a path of lengthd-k-1at one vertex of the cycle and a path of lengthk-1to another nonadjacent vertex of the cycle, respectively, where0≤k-1≤d-k-1.Lemma 20.
Let⋄nkbe a graph defined as above; then(i)
ifk-1<d-k-1, thenμ1(⋄nk-1)<μ1(⋄nk), where2≤k≤⌊d/2⌋;(ii)
ifk-1=d-k-1(i.e., k=⌊d/2⌋), then
(a)
whenn-d-2=0, or1,μ1(⋄nk-1)<μ1(⋄nk);(b)
whenn-d-2≥2,μ1(⋄nk)<μ1(⋄nk-1).Proof.
Suppose thatn-d-2=t; by Lemma 7(i),μ1(⋄nk)>t+4holds. LetU*=U0-v1; by Lemma 9,
(35)Φ(⋄d+2k-1)-Φ(⋄d+2k)=x[Φ(Lv2(U*))-Φ(Lvd+1(U*))]=x[Φ(Lvd+1,v2,v3(U*))-Φ(Lv2,vd+1,vd(U*))]=⋯=x[sd,k(x)-td,k(x)],
where
(36)sd,k(x)=(x-2)[(x-1)(x-4)Φ(Dd-2k+1)-(x-2)Φ(Dd-2k)],td,k(x)=(x-2)[(x-3)(x2-5x+2)Φ(Dd-2k)-(x-1)(x-4)Φ(Dd-2k-1)(x-3)(x2-5x+2)Φ(Dd-2k)].
By Lemmas 10 and 11(ii) and (26) and (35),
(37)Φ(⋄nk-1)-Φ(⋄nk)=(x-1)t[Φ(⋄d+2k-1)-Φ(⋄d+2k)]-tx(x-1)t-1[Φ(Lvk+1(⋄d+2k-1))-Φ(Lvk+2(⋄d+2k))]=x2(x-1)t-1(x-2)u(x),
whereu(x)=(x2-(t+5)x+4)Φ(Dd-2k)+t(x-2)Φ(Dd-2k-1).
Whenk-1<d-k-1, by Lemma 11(ii), we get
(38)u(x)=(x-2)(x2-(t+5)x+t+4)Φ(Dd-2k-1)-(x2-(t+5)x+4)Φ(Dd-2k-2).
Denote bye(t)the largest root ofx2-(t+5)x+4=0. Then
(39)x2-(t+5)x+4≤0,ifx∈(t+4,e(t)],x2-(t+5)x+t+4>x2-(t+5)x+4>0,ifx>e(t).
Hence, by Lemma 12(i), (37) is greater than0whenx≥μ1(⋄nk). Soμ1(⋄nk-1)<μ1(⋄nk)follows from Lemma 8.
Whenk-1=d-k-1, (37) becomes
(40)Φ(⋄nk-1)-Φ(⋄nk)=x2(x-1)t-1(x-2)[(x2-(t+5)x+4)].
Ift=1, let⋄72and⋄71be two graphs withd=4. Through Maple 15, the largest root ofx2-6x+4=0is e(1)=5.2363 (up to four decimal places), which is less thanμ1(⋄72)=5.3145andμ1(⋄71)=5.3008. From Lemma 5,μ1(⋄72)≤μ1(⋄nk)andμ1(⋄71)≤μ1(⋄nk-1)hold whenn≥7. So, (40) is greater than 0 for x≥μ1(⋄nk). By Lemma 8,μ1(⋄nk-1)<μ1(⋄nk)holds.
Ift≥2, by Lemmas 11(ii) and 12(iii),
(41)t(x)-[(x2-(t+5)x+4)]×[(x-2)Φ2(Dm)-(t+4)Φ(Dm)Φ(Dm-1)]=2t(x-1)Φ2(Dm)-[(t2+3t+4)x-4]×Φ(Dm)Φ(Dm-1)+2(t+2)(x-1)Φ2(Dm-1)=[2tx2-(t2+9t+4)x+(4t+4)]Φ(Dm)Φ(Dm-1)-2t(x-1)Φ(Dm)Φ(Dm-2)+2(t+2)(x-1)Φ2(Dm-1)=[2tx2-(t2+9t+4)x+(4t+4)]Φ(Dm)Φ(Dm-1)+4(x-1)Φ2(Dm-1)+2t(x-1),
where
(42)t(x)=[x3-(t+7)x2+(4t+14)x-(2t+8)]×Φ2(Dm)-[(t+4)x2-(6t+16)x+(4t+12)]×Φ(Dm)Φ(Dm-1)+2(t+2)(x-1)Φ2(Dm-1)
(one may refer to (52) in Lemma 24).
By Lemma12(ii),(x-2)Φ2(Dm)-(t+4)Φ(Dm)Φ(Dm-1)>0whenx≥t+4. And by derivative, 2tx2-(t2+9t+4)x+(4t+4)>0whenx≥t+4.
Thus, (41) is greater than0forx≥e(t)>t+4. From Lemma 8,μ1(⋄nk)<e(t)holds. Putx=μ1(⋄nk)into (40), whose right side is less than 0. Soμ1(⋄nk)<μ1(⋄nk-1). We complete the proof.Form Lemma20, the below corollary holds.Corollary 21.
When1≤k≤⌊d/2⌋,(i)
ifdis odd, thenμ1(⋄nk)≤μ1(⋄n⌊d/2⌋); the equality holds if and only if⋄nk≅⋄n⌊d/2⌋;(ii)
ifdis even, then
(a)
whenn-d-2=0,1,μ1(⋄nk)≤μ1(⋄n⌊d/2⌋); the equality holds if and only if⋄nk≅⋄n⌊d/2⌋;(b)
whenn-d-2≥2,μ1(⋄nk)≤μ1(⋄n⌊d/2⌋-1); the equality holds if and only if⋄nk≅⋄n⌊d/2⌋-1.LetW0be the unicyclic graph of orderd+3shown in Figure 2. LetW0(p2,…,pd,pd+2,pd+3)be a graph of ordernobtained fromW0by attachingpipendant vertices to eachvi∈V(H0)∖{v1,vd+1}, respectively. Whenk=2,pd+2andpd+3=0. Denote that
(43)𝒲~nd={∑i=2d‍W0(p2,…,pd,pd+2,pd+3):∑i=2d‍pi+pd+2+pd+3=n-d-3},𝒲-nd={W0(0,…,0,pi,0,…,0)=W0(pi):pi=n-d-3}.(a)
(b)Lemma 22.
LetG∈𝒲~nd. Then there is a graphG*∈𝒲-ndsuch thatμ1(G*)≥μ1(G).Proof.
The proof is similar to that of Lemma14.Lemma 23.
For anyG∈𝒲-nd,μ1(G)≤μ1(W0(pk)), where1≤k-1≤d-k+1; the equality holds if and only ifG≅W0(pk+1).Proof.
Suppose thatn-d-3=t. Ift=0, the result is obvious.
Ift≥1, by Lemma 7, we have
(44)μ1(G)<max{max{di+mi∣vi∈V(G)}∣G∈𝒲-nd,i≠k}=t+2+2+4+tt+2<t+5=Δ(W0(pk))+1<μ1(W0(pk)).
Hence, the lemma holds.


## 3. Main Results and Their Proofs

In this section, we first show thatμ1(∇n⌊d/2⌋+1)<μ1(Δn⌈d/2⌉)<μ1(⋄n⌊d/2⌋).Lemma 24.
μ
1
(
Δ
n
⌈
d
/
2
⌉
)
<
μ
1
(
⋄
n
⌊
d
/
2
⌋
).Proof.
Suppose thatn-d-2=t; by Lemma 7,t+4<μ1(Δn⌈d/2⌉), μ1(⋄n⌊d/2⌋)<t+5holds. We distinguish the following two cases.
Case
1. d=2m+1(m≥1).
LetΔnm+1and⋄nmbe two graphs on the left of Figure 3. Ift=0, denoteΔnm+1and⋄nmbyG1andG2, respectively. LetH1=G1-vm+3-⋯-vd+1andH2=G2-vm+3-⋯-vd+1. By Lemma 9,
(45)Φ(G1)=[Φ(Pm)-Φ(Lvm+2(Pm))]Φ(H1)-Φ(Pm)Φ(Lvm+2(H1)),Φ(G2)=[Φ(Pm)-Φ(Lvm+2(Pm))]Φ(H2)-Φ(Pm)Φ(Lvm+2(H2)),
where
(46)Φ(H1)=x(x-3)[(x-3)Φ(Dm)-2Φ(Dm-1)],Φ(Lvm+2(H1))=(x-1)(x-3)Φ(Dm)-(2x-3)Φ(Dm-1),Φ(H2)=x(x-2)×[(x-2)(x-4)Φ(Dm-1)-2(x-3)Φ(Dm-2)],Φ(Lvm+2(H2))=(x-2)[(x2-4x+2)Φ(Dm-1)-2(x-1)Φ(Dm-2)].
Note thatΦ(Pm)=xΦ(Dm-1)andΦ(Lvm+2(Pm))=Φ(Dm-1)+Φ(Dm-2).
Combining the equations above with Lemma10, we get
(47)Φ(Δnm+1)=(x-1)t-1[(x-1)Φ(G1)-txΦ(Lvm+2(G1))]=x(x-1)t-1{(x-1)(x-3)(x-3-t)Φ2(Dm)-[(t+4)x2-(6t+16)x+(6t+12)]×Φ(Dm)Φ(Dm-1)+[(2t+3)x-3(t+1)]Φ2(Dm-1)},(48)Φ(⋄nm)=(x-1)t-1[(x-1)Φ(G2)-txΦ(Lvm+2(G2))]=x(x-2)(x-1)t-1×{(x-1)[x3-(t+8)x2+(4t+18)x-(2t+10)]×Φ2(Dm-1)-[3x3-(3t+19)x2+8(t+4)x-4(t+4)]×Φ(Dm-1)Φ(Dm-2)+2(x-1)(x-3-t)×Φ2(Dm-1)}.
Hence, by Lemmas 11(ii) and 12(i), whenμ1(⋄nm+1)≤x<t+5,
(49)Φ(Δnm+1)-Φ(⋄nm)=x(x-1)t[d(x)Φ2(Dm-1)+e(x)Φ(Dm-1)Φ(Dm-2)-r(x)Φ2(Dm-2)]>x(x-1)t[d(x)+e(x)-r(x)]Φ2(Dm-2)≥0,
where
(50)d(x)=-(x-1)(x-t-5)>0,e(x)=(x2-2x+2)(x-t-4)>0,r(x)=(x-1)(x-t-3)>0,d(x)+e(x)-r(x)=(x-2)2(x-t-4)>0.
Soμ1(Δnm+1)<μ1(⋄nm+1)holds by Lemma 8.
Case
2. d=2m+2(m≥1).
LetΔnm+1and⋄nm+1be two graphs on the right of Figure 3. Ift=0, denoteΔnm+1and⋄nm+1byG1*and G2*, respectively. By similar computations as Case 1, we have
(51)Φ(Δnm+1)=(x-1)t-1[(x-1)Φ(G1*)-txΦ(Lvm+2(G1*))]=x(x-1)t-1{(x-1)2(x-3)(x-4-t)Φ2(Dm)-(x-1)[3x2-(3t+16)x+(6t+18)]×Φ(Dm)Φ(Dm-1)+[2x2-2(t+4)x+3(t+2)]Φ2(Dm-1)},(52)Φ(⋄nm+1)=(x-1)t-1[(x-1)Φ(G2*)-txΦ(Lvm+3(G2*))]=x(x-2)(x-1)t-1×{[x3-(t+7)x2+(4t+14)x-(2t+8)]Φ2(Dm)-[(t+4)x2-(6t+16)x+(4t+12)]×Φ(Dm)Φ(Dm-1)+2(t+2)(x-1)Φ2(Dm-1)}.
Hence, by Lemmas11(ii), 12(i), and 12(iii), whenx≥t+4,
(53)Φ(Δnm+1)-Φ(⋄nm+1)=x(x-1)t×{-[(t+1)x2-(3t+5)x+(t+4)]Φ2(Dm)+[(t+1)x3-(5t+5)x2+(7t+10)x-(2t+6)]×Φ(Dm)Φ(Dm-1)-[(2t+2)x2-(4t+4)x+(t+2)]Φ2(Dm-1)}=x(x-1)t×{[p(x)Φ(Dm-1)-q(x)Φ(Dm-2)]Φ(Dm-1)-w(x)},≥x(x-1)tΦ(Dm-1)×[(p(x)-w(x))Φ(Dm-1)-q(x)Φ(Dm-2)]>0,
where
(54)p(x)=2x3-(t+9)x2+(t+9)x-2>0,q(x)=2(x-1)2>0,w(x)=(t+1)x2-(3t+5)x+(t+4)>0,p(x)-w(x)-q(x)=2x3-(2t+12)x2+(4t+18)x-(t+8)>0.
Soμ1(Δnm+1)<μ1(⋄nm+1)follows from Lemma 8.(a)
(b)
(c)
(d)
(e)
(f)Let∇nkbe a graph of ordernobtained from a triangle by attachingn-d-3pendant edges, a path of lengthk-1and a path of lengthd-k+1at one vertex of the triangle, where1≤k-1≤d-k+1.Lemma 25.
μ
1
(
∇
n
⌊
d
/
2
⌋
+
1
)
<
μ
1
(
Δ
n
⌈
d
/
2
⌉
).Proof.
Suppose thatn-d-3=t; by Lemma 7(i),μ1(∇n⌊d/2⌋+1),μ1(Δn⌈d/2⌉)>t+5holds. We distinguish the following two cases.
Case
1. d=2m+1(m≥1).
Let∇nm+1be a graph on the left of Figure 3. Ift=0, denote∇nm+1byG3. LetH3=G3-v1-⋯-vm. By Lemma 9,
(55)Φ(G3)=[Φ(Pm)-Φ(Lvm(Pm))]Φ(H3)-Φ(Pm)Φ(Lvm+1(H3)),
where
(56)Φ(H3)=x(x-3)×[(x-1)(x-4)Φ(Dm)-(x-3)Φ(Dm-1)],Φ(Lvm+1(H3))=(x-1)(x-3)×[(x-1)Φ(Dm)-Φ(Dm-1)].
By Lemma 10, we get
(57)Φ(∇nm+1)=(x-1)t-1[(x-1)Φ(G3)-txΦ(Lvm+1(G3))]=x(x-3)(x-1)t×{(x-1)(x-t-4)Φ2(Dm)-[(t+4)x-(2t+6)]×Φ(Dm)Φ(Dm-1)+(t+2)Φ2(Dm-1)}.
By (47), we have
(58)Φ(Δnm+1)=x(x-1)t×{(x-1)(x-3)(x-t-4)Φ2(Dm)-[(t+5)x2-(6t+22)x+(6t+18)]×Φ(Dm)Φ(Dm-1)+[(2t+5)x-3(t+2)]Φ2(Dm-1)}.
Hence,
(59)Φ(∇nm+1)-Φ(Δnm+1)=x2(x-1)tΦ(Dm-1)×[(x-t-4)Φ(Dm)-(t+3)Φ(Dm-1)].
Whenm=1, (59)=x2(x-1)t+1(x-t-5)>0holds forx>t+5. Soμ1(∇nm+1)<μ1(Δnm+1)follows from Lemma 8.
Whenm≥2,μ1(∇nm+1)<μ1(Δnm+1)also holds (the proof will be given in Case 2 of the lemma).
Case
2.
d
=
2
m
+
2(m≥1).
Let∇nm+2be a graph on the right of Figure 3. By similar computations as in Case1, we have
(60)Φ(∇nm+2)=x(x-3)(x-1)t×{(x-1)2(x-t-5)Φ2(Dm)-2(x-1)(x-t-4)Φ(Dm)Φ(Dm-1)+(x-t-3)Φ2(Dm-1)}.
By (51), we get
(61)Φ(Δnm+1)=x(x-1)t-1{(x-1)2(x-3)(x-t-5)Φ2(Dm)-(x-1)[3x2-(3t+19)x+(6t+24)]×Φ(Dm)Φ(Dm-1)+[2x2-2(t+5)x+(3t+9)]Φ2(Dm-1)}.
Hence,
(62)Φ(∇nm+2)-Φ(Δnm+1)=x2(x-1)tΦ(Dm-1)×[(x-t-4)Φ(Dm+1)-(t+3)Φ(Dm)].
Lettk(x)=(x-t-4)Φ(Dk)-(t+3)Φ(Dk-1)and the largest root oftk(x)=0is denoted byμ1(tk(x)), wherek≥0.
We first show thatμ1(tk(x))is strictly increasing.
We use the induction onk. Clearly, μ1(t0(x))=t+4<μ1(t1(x))=t+5 holds. Generally, assume thatμ1(tk-1(x))<μ1(tk(x)), then by Lemmas 11(ii) and 12(iii),
(63)tk+1(x)=(x-2)tk(x)-tk-1(x),(64)tk2(x)-tk+1(x)tk-1(x)=-[(t+2)x2-(t+2)(t+5)x-1]=-v(x).
Putx=μ1(tk(x))into (63), whose right side is less than 0. Soμ1(tk(x))<μ1(tk+1(x)).
Furthermore,μ1(tk(x))has the upper bound.
Denote that the largest root ofv(x)=0isμ1(v(x)). If there exists somemsuch that μ1(tm(x))≥μ1(v(x)), we substitutekwithmand put x=μ1(tm(x)) into (64). So, the right side of it is less than and equal to0and the left side is greater than0, a contradiction.
LetG3′=∇nm+2-v1-⋯-vm-1-vm+5-⋯-v2m+3and G1′=Δnm+1-v1 -⋯- vm-1-vm+5 -⋯- v2m+3.
By (60) and (62),
(65)Φ(G3′)=x(x-1)t(x-3)(x2-3x+1)r(x),Φ(G3′)-Φ(G1′)=x2(x-1)t[x3-(t+8)x2+(3t+16)x-(t+6)]=x2(x-1)t(r(x)+1),
wherer(x)=x3-(t+8)x2+(3t+16)x-(t+7).
By Lemma7(i), μ1(G3′) is the largest root of r(x)=0. If μ1(G3′)≥μ1(G1′), then [Φ(G3′)-Φ(G1′)]|x=μ1(G3′)≤0 and r(x)+1|x=μ1(G3′)>0, a contradiction. So μ1(G3′)<μ1(G1′).
By derivative, whenx>t+5,
(66)xv(x)-(t+2)r(x)=3(t+2)x2-(3t2+22t+33)x+(t+2)(t+7)>0.
From Lemma 8,μ1(v(x))<μ1(G3′)holds. Furthermore, μ1(G3′)≤μ1(∇nm+2) and μ1(G1′)≤μ1(Δnm+1) hold by Lemma 5. Hence, (62) is greater than 0 forx≥μ1(Δnm+1). From Lemma 8, we getμ1(∇nm+2)<μ1(Δnm+1)as desired.Let□d+3kbe the unicyclic graph of orderd+3shown in Figure 2.Lemma 26.
μ
1
(
□
d
+
3
⌈
d
/
2
⌉
)
<
μ
1
(
Δ
d
+
3
⌈
d
/
2
⌉
).Proof.
Note that by Lemma7(i),μ1(Δd+3⌈d/2⌉)>5.
Case
1. d=2m+1(m≥1).
By Lemma9, we have
(67)Φ(□2m+4m+1)=[Φ(Pm)-Φ(Lvm(Pm))]×Φ(H4)-Φ(Pm)Φ(Lvm+1(H4))=x[(x-2)2(x-4)Φ2(Dm)-4(x-2)(x-3)×Φ(Dm)Φ(Dm-1)+(3x-8)Φ2(Dm-1)],
whereH4=□2m+4m+1-v1-⋯-vm.
By (47), we get
(68)Φ(Δ2m+4m+1)=x[(x-1)(x-3)(x-4)Φ2(Dm)-(5x2-22x+18)×Φ(Dm)Φ(Dm-1)+(5x-6)Φ2(Dm-1)].
Hence, by Lemmas 11(ii), 12(ii), and 12(iii), whenx≥5,
(69)Φ(□2m+4m+1)-Φ(Δ2m+4m+1)=x[(x-4)Φ2(Dm)+(x2-2x-6)Φ(Dm)Φ(Dm-1)-2(x+1)Φ2(Dm-1)]=xΦ(Dm-1)[2(x2-4x+1)Φ(Dm)-(3x-2)Φ(Dm-1)]+x(x-4)>xΦ2(Dm-1)(4x2-19x+6)+x(x-4)>0.
So μ1(□2m+4m+1)<μ1(Δ2m+4m+1) follows from Lemma 8.
Case
2. d=2m+2 (m≥1).
By a similar proof as of Case 1,μ1(□2m+5m+1)<μ1(Δ2m+5m+1)holds.Next we give the proof of Theorem1, which is the most important result.Proof of Theorem1.
LetG∈𝒞ndandX=(x1,x2,…,xn)Tbe a unit eigenvector ofμ1(G), wherexicorresponds to the vertexvi(1≤i≤n).
ChooseG∈𝒞ndsuch that the Laplacian spectral radius ofGis as large as possible. Then, by Lemma 6, we can assume thatG≠Cn. LetPd+1=v1v2,…,vd+1be the induced path of lengthdand letCqbe the only cycle inG. SinceG≠Cn, we havemin{d(v1),d(vd+1)}=1, sayd(v1)=1. We first show some claims.
Claim
1.
V
(
C
q
)
⋂
‍
V
(
P
d
+
1
)
≠
∅.
Proof of Claim
1. Otherwise, sinceGis connected, there exists an only pathP=vivkvk+1,…,vl-1vlconnectingCqandPd+1, wherevi∈V(Cq),vl∈V(Pd+1),andvk,…,vl-1∈V(G)∖(V(Cq)⋃‍V(Pd+1)).
For eachj, letTjbe a rooted tree (withrjas its root) attached atvj(k≤j≤l-1), where the order ofTjisnj. We assume that all trees, butTi, are kept fixed, whileTi(along with its root) can be changed. Suppose thatTi≠Sni. Letvbe a vertex belonging toTichosen so thatd(v)>2and thatd(v,ri)(the distance betweenvandri) is the largest. By Lemma 4 (applied in the reverse direction), the Laplacian spectral radius is increased when any hanging path atvis replaced by a hanging star (namely, edges of a hanging path now become the hanging edges atv). If the same is repeated for other hanging paths atv, we get one star attached atv(its central vertex is identified withv) whose size is equal to the sum of the lengths of the aforementioned paths. Letwbe a vertex inTi, adjacent tov, and belonging to the (unique) path betweenriandv. By Lemma 3, the Laplacian spectral radius is increased when all hanging edges atvbecome the hanging edges atw. Note also thatd(w,ri)=d(v,ri)-1. By repeating the same procedure (for any other vertex asv), we arrive atG~1, where the rooted treeTibecomes a starSni, so thatμ1(G~1)≥μ1(G).
By the same way to other rooted trees, we arrive atG~2, where every rooted treeTj≅Snj(k≤j≤l-1), andμ1(G~2)≥μ1(G~1). FromG~2, applying Lemma 2, we arrive atG~3, where only a rooted treeSnk+⋯+nl-1is attached at some vertexvm∈{vk,…,vl-1}. Soμ1(G~3)≥μ1(G~2).
FromG~3, by Lemma 3, the Laplacian spectral radius increased when all vertices adjacent tovlbecome adjacent vertices tovl-1. By repeating the same procedure (for any other vertex ofP-viasvl), we arrive atG~4, whereV(Cq)⋂‍V(Pd+1)≠∅, andμ1(G~4)≥μ1(G~3).
Hence, we haveμ1(G~4)≥μ1(G), a contradiction.
By Claim 1,V(Cq)⋂‍V(Pd+1)≠∅. Denote that Cq=vkvk+1,…,vl-1vlvd+2vd+3,…,vsvk(s≥d+2), where {vk,vk+1,…,vl-1,vl}=V(Cq)⋂‍V(Pd+1) and {vd+2,vd+3,…,vs}=V(Cq)∖V(Pd+1).
Claim
2. d(v)=1forv∈V(G)∖(V(Cq)⋃‍V(Pd+1)).
Proof of Claim
2. Consider other rooted trees attached atV(Cq)andV(Pd+1), respectively. By a similar proof as Claim 1 (the procedure untilG~3), we can getH~iandμ1(H~i)≥μ1(G), where only a rooted tree is attached atvi(vi∈{V(Cq)⋃‍V(Pd+1)}∖{v1,vd+1}), a contradiction.
Claim
3. l=k+1ands=d+2.
Proof of Claim
3. Denote that A={v∣v∈V(G)∖(V(Cq)⋃‍V(Pd+1)}={vs+1,…,vn} and |A|=n-s=t≥0.
Case
1. l=k. By Lemma 7,
(70)μ1(H~i)≤max{max{dvi+mvi∣vi∈V(H~i)}∣i≠k}=t+2+2+4+tt+2≤t+5=Δ(H~k)+1<μ1(H~k)<max{dvi+mvi∣vi∈V(H~k)}=t+4+2+2+2+2+tt+4≤t+6≤n-d+2=Δ(∇nk)+1<μ1(∇nk)
fors≥d+4(|Cq|≥4).
Whens=d+3(|Cq|=3),H~i≅W0(pi). By Lemma 23,μ1(H~i)<μ1(∇nk)for anyi≠k, where H~k≅∇nk.
Hence, by Lemma4,∇n⌊d/2⌋+1has the larger Laplacian spectral radius. Furthermore, from Lemmas 24 and 25, μ1(⋄n⌊d/2⌋)>μ1(∇n⌊d/2⌋+1) holds.
Case
2. l=k+1.
Subcase
2.1. t≥1. By Lemma 7,
(71)μ1(H~i)≤max{max{dvi+mvi∣vi∈V(H~i)},i≠k,k+1}=t+2+2+3+tt+2≤t+4=Δ(H~k)+1(Δ(H~k+1)+1)<μ1(H~k)(μ1(H~k+1))<max{dvi+mvi∣vi∈V(H~k)}≤t+3+2+3+tt+3<t+5≤n-d+2=Δ(Δnk)+1<μ1(Δnk)
fors≥d+3(|Cq|≥4).
Whens=d+2(|Cq|=3),H~i≅H0(pi), By Lemma 15,μ1(H~i)<μ1(Δnk)for anyi≠k+1, whereH~k+1≅Δnk.
Subcase
2.2.
t
=
0. By Lemma 7,
(72)μ1(H~i)≤max{max{dvi+mvi∣vi∈V(H~i)}i≠1,d+1}=3+2+3+23<6<n-d+2=Δ(Δnk)+1<μ1(Δnk)
fors≥d+4(|Cq|≥5).
Whens=d+3(|Cq|=4), by Lemma 13,μ1(□d+3k)<μ1(□d+3⌈d/2⌉). Furthermore, from Lemma 26,μ1(Δd+3⌈d/2⌉)>μ1(□d+3⌈d/2⌉).
Whens=d+2(|Cq|=3),H~i≅H0(pi)≅Δnk.
Hence, in view of Subcases 2.1 and 2.2, by Corollary17 and Lemma 24, μ1(⋄n⌊d/2⌋)>μ1(Δn⌈d/2⌉) holds.
Case
3. l≥k+2. By Lemma 7,
(73)μ1(H~i)≤max{max{dvi+mvi∣vi∈V(H~i)}i≠1,d+1}=t+3+2+2+2+tt+3≤t+5≤n-d+2=Δ(⋄nk)+1<μ1(⋄nk)
fors≥d+3(|Cq|≥5).
Whens=d+2(|Cq|=4), H~i≅U0(pi), by Lemma 19,μ1(H~i)<μ1(⋄nk)for anyi≠k+2, whereH~k+2≅⋄nk.
Hence, in view of Cases 1, 2, and 3 and Corollary21, ifdis odd,⋄n⌊d/2⌋has the largest Laplacian spectral radius; ifdis even andn-d-2=0,1,⋄n⌊d/2⌋has the largest Laplacian spectral radius; If d is even andn-d-2≥2,⋄n⌊d/2⌋-1has the largest Laplacian spectral radius, a contradiction.
By Claims 1, 2, and 3, Theorem1 follows immediately.



---

*Source: 563067-2013-12-23.xml*