# The Laplacian Spectral Radius of a Class of Unicyclic Graphs

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

---

## Abstract

LetC(n,k) be the set of all unicyclic graphs with n vertices and cycle length k. For
any U∈C(n,k), U consists of the (unique) cycle (say Ck) of length k and a certain number of trees attached to the vertices of Ck having (in total) n-k edges. If there are at most two trees attached to the vertices of Ck, where k is even, we identify in the class of unicyclic graphs those graphs whose Laplacian spectral radii are minimal.


---

## Body

## 1. Introduction

Following [1], let G=(V,E) be a simple connected graph on n vertices and m edges (so n=|V(G)| is its order and m=|E(G)| is its size). For vi∈V, the degree of vi is denoted by dvi. Let Δ(G) be the maximum degree of G. For two vertices vi and vj  (i≠j) in G, the distance between vi and vj, denoted by d(vi,vj), is the number of edges in a shortest path joining vi and vj.LetC(n,k) be the set of all unicyclic graphs on n vertices and the cycle length k. So, if U∈C(n,k), then U consists of the (unique) cycle (say Ck) of length k and a certain number of trees attached to vertices of Ck having (in total) n-k edges. If the cycle length of a unicyclic graph is even (odd), we call it an even (odd) unicyclic graph. We may assume that vertices of Ck are c1,c2,…,ck or for short only 1,2,…,k (ordered in a natural way around Ck, say, in the clockwise direction). For each i, let Ti be a rooted tree (with ri as its root) attached to ci. Then, for each U∈C(n,k), we can write U=C(T1,T2,…,Tk). If Ti, for each i, is a path Pmi+1, whose root is a vertex of minimum degree, then we write U=P(m1,m2,…,mk).LetA(G) be the adjacency matrix of G and D(G)=diag(dv1,dv2,…,dvn) the diagonal matrix. Then the Laplacian matrix of G is L(G)=D(G)-A(G). Since L(G) is real symmetric and positive semidefinite, its eigenvalues are nonnegative real numbers. For a graph G, we denote by μ1(G) the largest eigenvalue of L(G) and call it the Laplacian spectral radius.The investigation on the Laplacian spectral radius of graphs is an important topic in the theory of graph spectra. Since 1980s, there are several monographs and a lot of research papers published continually (see [2–7]). Recently, the problem concerning graphs with maximal or minimal Laplacian spectral radius of a given class of graphs has been studied by many authors. Guo [8] determined the first four graphs with the largest Laplacian spectral radius among all unicyclic graphs on n vertices.In this paper, for anyU∈C(n,k), if there are at most two trees attached to vertices of Ck, where k is even, we characterize in the class of even unicyclic graphs those graphs whose Laplacian spectral radii are minimal.


## 2. Main Results and Proofs

LetLvi(G) be the principal submatrix obtained from L(G) by deleting the corresponding row and column of vi. Generally, let LS(G) be the principal submatrix obtained from L(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.Lemma 1 (see [9]).
LetG1 and G2 be two graphs. If Φ(G1)>Φ(G2) for x≥μ1(G2), then μ1(G1)<μ1(G2).Lemma 2 (see [4]).
LetG be a graph containing at least one edge. Then μ1(G)≥Δ(G)+1. Moreover, if G is connected on n>1 vertices, the equality holds if and only if Δ(G)=n-1.An internal path of a graphG is a sequence of vertices v1,v2,…,vk with k≥2 such that(1)
the vertices in the sequence are distinct (except possiblyv1=vk);(2)
vi is adjacent to vi+1, (i=1,2,…,k-1);(3)
the vertex degreesdvi satisfy dv1≥3, dv2=⋯=dvk-1=2 (unless k=2), and dvk≥3.Lemma 3 (see [10]).
LetG be a connected bipartite graph with vertex set V(G)={v1,v2,…,vn} and uv an edge on an internal path P:v1v2⋯vk (n>k≥2) of G. Let G2l+1 (l≥1) be the graph obtained from G by subdividing the edge uv into 2l+1 new edges. Then one has μ1(G)>μ1(G2l+1)>μ1(G2l+3).Letv be a vertex of a connected graph G with at least two vertices. Let Gk,l (l≥k≥1) be the graph obtained from G by 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]).
IfG is a connected bipartite graph on n≥2 vertices and v is a vertex of G, let Gk,l be the graph defined as above. If l≥k≥1, then μ1(Gk-1,l+1)<μ1(Gk,l).Lemma 5 (see [12]).
LetDn(n≥1) be the matrix obtained from L(Pn+2) by deleting the rows and columns corresponding to two end vertices of Pn+2, and 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 Lemma5(i), all eigenvalues of Dn are 2+2cos(iπ/(n+1)), where 1≤i≤n. Other characterizations of Φ(Dn) can be shown as follows.Lemma 6 (see [9]).
LetΦ(Dm)Φ(Dn)-Φ(Dm-1)Φ(Dn+1)=Φ(Dn-m), where 0≤m≤n.Lemma 7.
Forn,m≥1, Φ(Dn+m)=Φ(Dn)Φ(Dm)-Φ(Dn-1)Φ(Dm-1).Proof.
It is easily obtained from some properties of the determinantΦ(Dn).In the following, we give a transformation property of unicyclic graphs.Lemma 8.
Letu(=i) and v(=j) be two nonadjacent vertices of the cycle Ck, and suppose that d(u,v)=a+1; that is, a is the number of vertices in the shortest path Pa+2, not including u and v, where 1≤a≤⌊(k-2)/2⌋. Let Ga(m,n)=P(m1,m2,…,mk), where only mi=m and mj=n (1≤i,j≤k) are nonzero. If m,n≥1, then μ1(Ga(m,n))<μ1(Ga-1(m,n)).Proof.
Case
1 (n>2). Label vertices of Ga(m,n) properly; we have
(1)Φ(Ga(m,n))=|xI-Lv1(Ga(m,1))e1OOe1Tx-21OO1x-2f1TOOf1xI-Lv2(Pn-1)|,
where v1,v2∈V(Pn+1) and v1 and v2 are adjacent to v and v1, respectively. e1 is the (k+m)×1 column vector whose only nonzero entry is 1 in the (m+a+2)th position, and f1 is the (n-2)×1 column vector whose only nonzero entry is 1 in the first position.
By a direct computation, we can obtain(2)Φ(Ga(m,n))=det(A)det(B)-det(A′)det(B′),
where
(3)det(A)=|xI-Lv1(Ga(m,1))e1e1Tx-2|,det(A′)=det(xI-Lv1(Ga(m,1))),det(B)=|x-2f1Tf1xI-Lv2(Pn-1)|=Φ(Dn-1)+Φ(Dn-2),det(B′)=det(xI-Lv2(Pn-1))=Φ(Dn-2)+Φ(Dn-3).
Furthermore,
(4)det(A)=|xI-Lu1(Pm)g10g1Tx-2h1T0h1xI-Lu1,v2(Ga(1,2))|=det(D)det(C)-det(D′)det(C′),
where u1∈V(Pm+1) is adjacent to u. g1 is the (m-1)×1 column vector, whose only nonzero entry is 1 in the last position. h1 is the (k+1)×1 column vector, whose only nonzero entry is 1 in the first position.
Note that(5)det(D)=|xI-Lu1(Pm)g1g1Tx-2|=Φ(Dm)+Φ(Dm-1),det(D′)=det(xI-Lu1(Pm))=Φ(Dm-1)+Φ(Dm-2),det(C)=det(xI-Lu1,v2(Ga(1,2)))=(x-2)Φ(Ck)-(2x-3)Φ(Dk-1)+(x-1)Φ(Da)Φ(Dk-2-a),det(C′)=det(xI-Lu,u1,v2(Ga(1,2)))=(x-2)Φ(Dk-1)-(x-1)Φ(Da)Φ(Dk-2-a).
Similarly,
(6)det(A′)=det(D)[Φ(Ck)-2Φ(Dk-1)+Φ(Da)Φ(Dk-2-a)]-det(D′)[Φ(Dk-1)-Φ(Da)Φ(Dk-2-a)].
Combing the equations previous, we get(7)Φ(Ga(m,n))=h(x)det(D)det(B)-i(x)det(D′)det(B)-g(x)det(D)det(B′)+k(x)det(D′)det(B′),
where
(8)h(x)=det(C),i(x)=det(C′),k(x)=Φ(Dk-1)-Φ(Da)Φ(Dk-2-a),g(x)=Φ(Ck)-2Φ(Dk-1)+Φ(Da)Φ(Dk-2-a).
From Lemma 2, μ1(Ga-1(m,n))>4. By Lemmas 5(ii) and 6 and (7),
(9)Φ(Ga(m,n))-Φ(Ga-1(m,n))=Φ(Dk-2-2a)[(x-1)det(B)-det(B′)]×(det(D)+det(D′))=x2Φ(Dk-2-2a)Φ(Dn-1)Φ(Dm-1)>0,
for x≥μ1(Ga-1(m,n)).
Soμ1(Ga(m,n))<μ1(Ga-1(m,n)) holds from Lemma 1.
Whenn=1,2, we appropriately modify Φ(Ga(m,n)) and get the same result.Next we consider some special even unicyclic graphsGa(m,n).By Lemmas6 and 7, we have
(10)(i)Φ(Dk-1)=Φ(Dk/2)Φ(D(k-2)/2)-Φ(D(k-2)/2)×Φ(D(k-4)/2),(ii)Φ(Dk-2)=Φ2(D(k-2)/2)-Φ2(D(k-4)/2),(iii)Φ2(D(k-2)/2)-Φ(Dk/2)Φ(D(k-4)/2)=1.
From Lemmas 5(ii) and 5(iv) and (10), we get
(11)Φ(Ck)=Φ(Dk)-Φ(Dk-2)-2=(x-2)Φ(Dk-1)-2Φ(Dk-2)-2=x(x-4)Φ2(D(k-2)/2).
By (11) and (i) of (10),
(12)det(A)=Φ(D(k-2)/2)×{(D′)det(D)[(x3-8x2+16x-7)Φ(D(k-2)/2)+2(2x-3)Φ(D(k-4)/2)(x3-8x2+16x-7)]-det(D′)×[(x5-5x+5)Φ(D(k-2)/2)-2(x-2)Φ(D(k-4)/2)(x5-5x+5)](D′)},det(A′)=Φ(D(k-2)/2)×{(D′)det(D)[(x2-6x+5)Φ(D(k-2)/2)+4Φ(D(k-4)/2)(x2-6x+5)]-det(D′)×[(x-3)Φ(D(k-2)/2)-2Φ(D(k-4)/2)[(x2-6x+5)Φ(D(k-2)/2)](D′)}.Case 1.
The unicyclic graphG2n(n-1,n), where k=4n+2 (n≥2), is as follows.
Note that(13)det(D)det(B)=(x-1)2Φ2(Dn-2)-2(x-1)×Φ(Dn-2)Φ(Dn-3)+Φ2(Dn-3),det(D′)det(B)=(x-1)Φ2(Dn-2)+(x-2)Φ(Dn-2)×Φ(Dn-3)-Φ2(Dn-3),det(D)det(B′)=det(D′)det(B),det(D′)det(B′)=Φ2(Dn-2)+2Φ(Dn-2)Φ(Dn-3)+Φ2(Dn-3).
In view of (2) and (12)-(13), we have
(14)Φ(G2n(n-1,n))=xΦ(D2n){(x4-10x3+31x2-34x+10)Φ2(Dn-2)-(2x3-16x2+33x-16)Φ(Dn-2)×Φ(Dn-3)+(x2-6x+6)Φ2(Dn-3){(x4-10x3+31x2-34x+10)Φ2(Dn-2)}+2xΦ(D2n-1){(2x2-6x+3)Φ2(Dn-2)-(3x-4)×Φ(Dn-2)Φ(Dn-3)+Φ2(Dn-3)}=x(S1Φ(D2n)+2S2Φ(D2n-1)).
By Lemmas 5(ii) and 7,
(15)Φ(D2n)-2Φ(D2n-1)=Φ2(Dn)-Φ2(Dn-1)-2(Φ(Dn)Φ(Dn-1)-Φ(Dn-1)Φ(Dn-2))=(x4-10x3+33x2-40x+13)Φ2(Dn-2)-(2x3-16x2+36x-20)Φ(Dn-2)Φ(Dn-3)+(x2-6x+7)Φ2(Dn-3)=S1+S2.
So,
(16)Φ(G2n(n-1,n))=x[(Φ(D2n)-2Φ(D2n-1)-S2)×Φ(D2n)+2S2Φ(D2n-1)]=x(Φ(D2n)-2Φ(D2n-1))(Φ(D2n)-S2).
Letμ1(Φ(D2n)-2Φ(D2n-1)) and μ1(Φ(D2n)-S2) be the largest roots of Φ(D2n)-2Φ(D2n-1)=0 and Φ(D2n)-S2=0, respectively. In the proof of Theorem 2 (see [13]), we have shown that the sequence μ1(Φ(D2n)-2Φ(D2n-1)) is strictly increasing by the initial value μ1(Φ(D2)-2Φ(D1))=4.4150. For any fixed n, the second largest root Φ(D2n)-2Φ(D2n-1)=0 is less than 4.
By Lemmas5(ii) and 7, we get
(17)2Φ(D2n-1)-S2=(Φ(D2n)-S2)-(Φ(D2n)-2Φ(D2n-1))=P(x)Φ2(Dn-2)-Q(x)Φ(Dn-2)Φ(Dn-3)+W(x)Φ2(Dn-3),
where
(18)P(x)=2x3-14x2+26x-11>0,Q(x)=4x2-19x+16>0,W(x)=2x-5>0,4P(x)W(x)-Q2(x)=127x2-36>0,
for x≥4.3 by derivative.
Then whenn=2, 2Φ(D2n-1)-S2=P(x)Φ2(Dn-2)>0. When n≥3,
(19)2Φ(D2n-1)-S2≥(2P(x)W(x)-Q(x))Φ(Dn-2)Φ(Dn-3)>0.
If μ1(Φ(D2n)-2Φ(D2n-1))≤μ1(Φ(D2n)-S2), then we put x=μ1(Φ(D2n)-S2) in (17), whose left side is less than and equal to 0, a contradiction. So, μ1(Φ(D2n)-2Φ(D2n-1))>μ1(Φ(D2n)-S2).
Finally,μ1(Φ(G2n(n-1,n)))=μ1(Φ(D2n)-2Φ(D2n-1)) holds.Case 2.
The unicyclic graphG2n+1(n,n), where k=4n+4  (n≥2), is as follows.
Note that(20)det(D)det(B)=(x3-4x2+4x-1)Φ2(Dn-2)-2(x2-5x+2)Φ(Dn-2)Φ(Dn-3)+(x-1)Φ2(Dn-3),det(D′)det(B)=(x-1)2Φ2(Dn-2)-2(x-1)×Φ(Dn-2)Φ(Dn-3)+Φ2(Dn-3),det(D)det(B′)=(x2-3x+1)Φ2(Dn-2)+(x2-4x+2)Φ(Dn-2)Φ(Dn-3)-(x-1)Φ2(Dn-3),det(D′)det(B′)=(x-1)Φ2(Dn-2)+(x-2)Φ(Dn-2)×Φ(Dn-3)-Φ2(Dn-3).
By (2), (12), and (20), we have
(21)Φ(G2n+1(n,n))=xΦ(D2n+1)×{(x5-12x4+50x3-88x2+61x-12)Φ2(Dn-2)-(2x4-20x3+62x2-68x+20)Φ(Dn-2)×Φ(Dn-3)+(x3-8x2+16x-8)Φ2(Dn-3)}+2xΦ(D2n){(2x3-10x2+14x-4)Φ2(Dn-2)-(4x2-12x+6)Φ(Dn-2)Φ(Dn-3)+(2x-2)Φ2(Dn-3)}=x(U1Φ(D2n+1)+2U2Φ(D2n)).
From Lemmas 5(ii) and 7,
(22)Φ(D2n+1)-2Φ(D2n)=Φ(Dn+1)Φ(Dn)-Φ(Dn)Φ(Dn-1)-2(Φ2(Dn)-Φ2(Dn-1))=(x5-12x4+52x3-98x2+75x-16)Φ2(Dn-2)-(2x4-20x3+66x2-80x+26)×Φ(Dn-2)Φ(Dn-3)+(x3-8x2+18x-10)×Φ2(Dn-3)=U1+U2.
So,
(23)Φ(G2n+1(n,n))=x[(Φ(D2n+1)-2Φ(D2n)-U2)×Φ(D2n+1)+2U2Φ(D2n)]=x(Φ(D2n+1)-2Φ(D2n))(Φ(D2n+1)-U2).
By a similar discussion to that in Case 1, we have μ1(Φ(D2n+1)-2Φ(D2n))>μ1(Φ(D2n+1)-U2). Thus, μ1(Φ(G2n+1(n,n)))=μ1(Φ(D2n+1)-2Φ(D2n)).Lemma 9.
Give a sequence of Laplacian spectral radii of even unicyclic graphs as follows:(24)(S):μ1(G(k-2)/2(m,n)),μ1(G(k-2)/2(m-1,n+1)),…,μ1(G(k-2)/2(0,m+n)),
where n≥2, m=n-1, or m=n. Then(i)
ifm=n-1,whenk=4n+2, the items of the sequence (S) are equal to each other; that is,
(25)μ1(G2n(n-1,n))=μ1(G2n(n-2,n+1))=⋯=μ1(G2n(0,2n-1));
when k<4n+2, the sequence (S) is strictly decreasing; when k>4n+2, the sequence (S) is strictly increasing;(ii)
ifm=n,whenk=4n+4, the items of the sequence (S) are equal to each other; that is,
(26)μ1(G2n+1(n,n))=μ1(G2n+1(n-1,n+1))=⋯=μ1(G2n+1(0,2n));
when k<4n+4, the sequence (S) is strictly decreasing; when k>4n+4, the sequence (S) is strictly increasing.Proof.
For anyn≥m≥1, by (7), we have
(27)Φ(Ga(m,n))=h(x)(Φ(Dm)+Φ(Dm-1))(Φ(Dn-1)+Φ(Dn-2))-i(x)(Φ(Dm-1)+Φ(Dm-2))(Φ(Dn-1)+Φ(Dn-2))-g(x)(Φ(Dm)+Φ(Dm-1))(Φ(Dn-2)+Φ(Dn-3))+k(x)(Φ(Dm-1)+Φ(Dm-2))×(Φ(Dn-2)+Φ(Dn-3)).
From (10), and (27) and Lemma 6,
(28)Φ(G(k-2)/2(m,n))-Φ(G(k-2)/2(m-1,n+1))=x[(h(x)+k(x))Φ(Dn-m-1)-i(x)Φ(Dn-m)-g(x)Φ(Dn-m-2)[(h(x)+k(x))Φ(Dn-m-1)-i(x)Φ(Dn-m)]=-xΦ(Dn-m)[xΦ2(D(k-2)/2)]xΦ(Dk-1)-Φ(Ck)-xΦ2(D(k-2)/2)]=-xΦ(Dn-m)Φ(D(k-2)/2)×[Φ(D(k-2)/2)-2Φ(D(k-4)/2)].
Case
1 (m=n-1). If k=4n+2, we have μ1(Φ(G2n(n-1,n)))=μ1(Φ(D2n)-2Φ(D2n-1)) by the previous discussion. From (28), the items of the sequence (S) are equal to each other.
Ifk<4n+2, by Lemma 3, then μ1(G(k-2)/2(m-i,n+i))>μ1(G2n(m-i,n+i)), where 0≤i≤m. Note that μ1(Φ(D(k-2)/2)-2Φ(D(k-4)/2))<μ1(Φ(D2n)-2Φ(D2n-1)); by Lemma 1 and (28), we obtain that the sequence (S) is strictly decreasing.
Ifk>4n+2, by Lemma 3, then μ1(G(k-2)/2(m-i,n+i))<μ1(G2n(m-i,n+i)), where 0≤i≤m. Note that μ1(Φ(D(k-2)/2)-2Φ(D(k-4)/2))>μ1(Φ(D2n)-2Φ(D2n-1)); by Lemma 1 and (28), we obtain that the sequence (S) is strictly increasing.
Case
2 (m=n). By a similar discussion to that in Case 1, the results of (ii) hold.Theorem 10.
For anyU∈C(n,k), that is, U=C(T1,T2,…,Tk), if k is even and the number of Ti(1≤i≤k) is at most 2, supposing that c=⌈(n-k)/2⌉≥2, then(i)
ifn-k=2c-1,whenk=4c+2, μ1(G2c(c-1,c))=μ1(G2c(c-2,c+1))=⋯=μ1(G2c(0,n-k)) are minimal; when k<4c+2, μ1(G(k-2)/2(0,n-k)) is the smallest; when k>4c+2, μ1(G(k-2)/2(c-1,c)) is the smallest;(ii)
ifn-k=2c,whenk=4c+4, μ1(G2c+1(c,c))=μ1(G2c+1(c-1,c+1))=⋯=μ1(G2c+1(0,n-k)) are minimal; when k<4n+4, μ1(G(k-2)/2(0,n-k)) is the smallest; when k>4n+4, μ1(G(k-2)/2(c,c)) is the smallest.Proof.
Given anyU∈C(n,k), for each j, let Tj be a rooted tree (with rj as its root) attached to vj (1≤j≤k), where the order of Tj is mj+1. We assume that all trees but, say, Ti, are kept fixed, while Ti (along with its root) can be changed. Suppose that Ti≠Pmi+1. Let v be a vertex belonging to Ti chosen so that d(v)>2 and that d(v,ri) (the distance between v and ri) is the largest. By Lemma 4, the Laplacian spectral radius is strictly decreasing when two hanging paths at v are replaced by a new hanging path (i.e., the length of the new hanging path is the sum of the lengths of two hanging paths at v). If the same is repeated for other hanging paths to v, we get one path attached at v (its central vertex is identified with v) whose size is equal to the sum of the lengths of the aforementioned paths. Let w be a vertex in Ti, adjacent to v and belonging to the (unique) path between ri and v. Note also that d(w,ri)=d(v,ri)-1. By repeating the same procedure (for any other vertex as v), we arrive at G1, where the rooted tree Ti becomes a path Pmi+1, so that μ1(G1)<μ1(U).
By the same way as with other rooted trees, we arrive atG2, where every rooted tree Tj≅Pmj+1 (1≤j≤k); that is, G2≅P(m1,m2,…,mk). By Lemma 4, μ1(G2)<μ1(U) holds.
If there are at most two trees attached to the cycleCk, by the previous discussion, we get that P(m1,m2,…,mk) has small Laplacian spectral radius among C(n,k), where two mi (1≤i≤k) are nonzero at most. Applying Lemma 8 repeatedly, we know that G(k-2)/2(a,b) has the smaller Laplacian spectral radius, where a+b=n-k. From Lemma 9, the result holds.Remark 11.
Whenn-k=2, that is, c=1, from Theorem 2 and its proof (see [13]), we get the same result as Theorem 10.



---

*Source: 730396-2013-12-18.xml*