# On the Laplacian Coefficients and Laplacian-Like Energy of Unicyclic Graphs withn Vertices and m Pendent Vertices

Authors: Xinying Pai; Sanyang Liu
Journal: Journal of Applied Mathematics
 (2012)

---

## Abstract

LetΦ(G,λ)=det(λIn-L(G))=∑k=0n(-1)kck(G)λn-k be the characteristic polynomial of the Laplacian matrix of a graph G of order n. In this paper, we give four transforms on graphs that decrease all Laplacian coefficients ck(G) and investigate a conjecture A. Ilić and M. Ilić (2009) about the Laplacian coefficients of unicyclic graphs with n vertices and m pendent vertices. Finally, we determine the graph with the smallest Laplacian-like energy among all the unicyclic graphs with n vertices and m pendent vertices.


---

## Body

## 1. Introduction

LetG=(V,E) be a simple undirected graph with n vertices and |E| edges and, let L(G)=D(G)-A(G) be its Laplacian matrix. The Laplacian polynomial of G is the characteristic polynomial of its Laplacian matrix. That is
(1.1)Φ(G,λ)=det(λIn-L(G))=∑k=0n‍(-1)kck(G)λn-k.The Laplacian matrixL(G) has nonnegative eigenvalues μ1≥μ2≥⋯≥μn-1≥μn=0 [1]. From Viette’s formulas,
(1.2)ck(G)=σk(μ1,μ2,…,μn-1)=∑I⊆{1,2,…,n-1},|I|=k‍∏i∈I‍μi
is a symmetric polynomial of order n-1. In particular, we have c0(G)=1,c1(G)=2|E(G)|,cn(G)=0 and cn-1(G)=nτ(G), where τ(G) is the number of spanning trees of G. If G is a tree, coefficient cn-2(G) is equal to its Wiener index, which is a sum of distance between all pairs of vertices:
(1.3)cn-2(G)=W(G)=∑u,v∈V‍d(u,v).
The Wiener index is considered as one of the most used topological indices with high correlation with many physical and chemical properties of molecular compounds.A unicyclic graph is a connected graph in which the number of vertices equals the number of edges. Recently, the study on the Laplacian coefficients attracts much attention.Mohar [2] proved that among all trees of order n, the kth Laplacian coefficients ck(G) are largest when the tree is a path and are smallest for stars. Stevanović and Ilić [3] showed that among all connected unicyclic graphs of order n, the kth Laplacian coefficients ck(G) are largest when the graph is a cycle Cn and smallest when the graph is an Sn with an additional edge between two of its pendent vertices, where Sn is a star of order n. He and Shan [4] proved that among all bicyclic graphs of order n, the kth Laplacian coefficients ck(G) is smallest when the graph is obtained from C4 by adding one edge connecting two non-adjacent vertices and adding n-4 pendent vertices attached to the vertex of degree 3. A. Ilić and M. Ilić [5] verified that among trees on n vertices and m leaves, the balanced starlike tree S(n,m) (see Definition 2.2) has minimal Laplacian coefficients. Some other works on Laplacian coefficients can be found in [6–8].In this paper, we determine the smallestkth Laplacian coefficients ck(G) among all unicyclic graphs with n vertices and m pendent vertices. Thus we completely solve a conjecture on the minimal Laplacian coefficients of unicyclic graphs with n vertices and m pendent vertices (see [5]).Motivated by the results in [3, 4, 9–12] concerning the minimal Laplacian coefficients and Laplacian-like energy of some graphs and the minimal molecular graph energy of unicyclic graphs with n vertices and m pendent vertices, this paper will characterize the unicyclic graphs with n vertices and m pendent vertices, which minimize Laplacian-like energy.


## 2. Transformations and Lemmas

In this section, we introduce some graphic transformations and lemmas, which can be used to prove our main results. The Laplacian coefficientsck(G) of a graph G can be expressed in terms of subtree structures of G by the following result of Kelmans and Chelnokov [13]. Let F be a spanning forest of G with components Ti, i=1,2,…,k having ni vertices each, and let γ(F)=∏i=1k‍ni.Lemma 2.1 (see [13]).
The Laplacian coefficientcn-k(G) of a graph G is given by
(2.1)cn-k(G)=∑F∈ℱk‍γ(F),
where ℱk is the set of all spanning forests of G with exactly k components.For a real numberx, we use ⌊x⌋ to represent the largest integer not greater than x and ⌈x⌉ to represent the smallest integer not less than x.Definition 2.2 (see [5]).
The balanced starlike treeS(n,m), 3≤m≤n-1, is a tree of order n with just one center vertex v, and each of the m branches of T at v is a path of length ⌊(n-1)/m⌋ or ⌈(n-1)/m⌉.LetPn be the path with n vertices. A path P:vv1v2⋯vk in G is called a pendent path if d(v1)=d(v2)=⋯=d(vk-1)=2 and d(vk)=1. If k=1, then we say vv1 is a pendent edge of the graph G. A leaf or pendent vertex is a vertex of degree one. A branching vertex is a vertex of degree greater than two. The k paths Pl1,Pl2,…,Plk are said to have almost equal lengths if l1,l2,…,lk satisfy |li-lj|≤1 for 1≤i,j≤k.Definition 2.3 (see [5]).
The dumbbellD(n,a,b) consists of the path Pn-a-b together with a independent vertices adjacent to one leaf of Pn-a-b and b independent vertices adjacent to the other leaf.The unionG=G1⋃‍G2 of graph G1 and G2 with disjoint vertex sets V1 and V2 and edge sets E1 and E2 is the graph G=(V,E) with V=V1⋃‍V2 and E=E1⋃‍E2. If G is a union of two paths of lengths a and b, then G is disconnected and has a+b vertices and a+b-2 edges. Let mk(G) be the number of matchings of G containing exactly k independent edges. Especially, let mk(a,b) be the number of k matchings in G=Pa⋃‍Pb.Lemma 2.4 (see [5]).
Letv be a vertex of nontrivial connected graph G, and let G(p,q) denote the graph obtained from G by adding pendent paths P=vv1v2⋯vp and Q=vu1u2⋯uq, at vertex v. Assume that both numbers p and q are even. If p-2≥q+2≥4, then for every k we have
(2.2)mk(G(p,q))≤mk(G(p-2,q+2)).Lemma 2.5 (see [12]).
Letmk(a,b) be the number of k-matchings in G=Pa⋃‍Pb and n=4s+r with 0≤r≤3. Then the following inequality holds:
(2.3)mk(n,0)≥mk(n-2,2)≥mk(n-4,4)≥⋯≥mk(2s+r,2s).Lemma 2.6 (see [5]).
Among trees onn vertices and 2≤m≤n-2 leaves, the balanced starlike tree S(n,m) has minimal Laplacian coefficient ck(G), for every k=0,1,…,n.Definition 2.7 (see [5]).
Letv be a vertex of a tree T of degree m+1. Suppose that P1,P2,…,Pm are pendent paths incident with v, with lengths ni≥1,i=1,2,…,m. Let w be the neighbor of v distinct from the starting vertices of paths v1,v2,…,vm, respectively. We form a tree T′=δ(T,v) by removing the edges vv1,vv2,…,vvm-1 from T and adding m-1 new edges wv1,wv2,…,wvm-1 incident with w. We say that T′ is a δ-transform of T.Lemma 2.8 (see [5]).
LetT be an arbitrary tree, rooted at the center vertex. Let vertex v be on the deepest level of tree T among all branching vertices with degree at least three. Then for the δ-transformation tree T′=δ(T,v) and 0≤k≤n holds:
(2.4)ck(T)≥ck(T′).Lemma 2.9 (see [14]).
For every acyclic graphT with n vertices,
(2.5)ck(T)=mk(S(T)),0≤k≤n,
where S(T) means the subdivision graph of T.


## 3. Main Results

In this section, we present four new graphic transformations that decrease the Laplacian coefficients.Definition 3.1.
Letu be a vertex in the cycle C of a unicyclic graph G, such that u has degree p+2 and p pendent paths named Pl1,Pl2,…,Plp, where Pli:ui,1,ui,2,…,ui,li,  1≤i≤p. If li≥lj+2, and let
(3.1)G1=G-ui,li-1ui,li+uj,ljui,li≜π1(G).
We say that G1 is a π1-transformation of G.It is easy to see thatπ1-transformation preserves the size of a cycle of G and the number of pendent vertices.Theorem 3.2.
LetG be a connected unicyclic graph with n vertices and m pendent vertices, G1=π1(G). Then for every k=0,1,…,n,
(3.2)ck(G)≥ck(G1),
with equality if and only if k∈{0,1,n-1,n}.Proof.
It is easy to see thatc0(G1)=c0(G)=1, c1(G1)=2|E(G1)|=2|E(G)|=c1(G),cn(G1)=cn(G)=0, cn-1(G1)=nτ(G1)=n|E(C)|=nτ(G)=cn-1(G).
Now, consider the coefficientscn-k (k≠0,1,n-1,n). Let ℱk and ℱk1 be the sets of spanning forests of G and G1 with exactly k components, respectively.
Without loss of generality, we assume thatl1≥l2+2. Let G1=π1(G)=G-u1,l1-1u1,l1+u2,l2u1,l1 (see Figure 1).
Obviously, by the definition of the spanning forest, the cycleC in the unicyclic graph satisfies that C∉F∈ℱk and C∉F1∈ℱk1, where F and F1 are the arbitrary forests in ℱk and ℱk1, respectively. Without loss of generality, we remove one of the edges in the cycle C, say uv, so we get T and T′, respectively. By Lemmas 2.4 and 2.9, we have that for every k=0,1,…,n,
(3.3)ck(T)≥ck(T′),
with equality if and only if k∈{0,1,n-1,n}. If we remove the other edge, say xy, we get S and S′, respectively. By Lemmas 2.4 and 2.9, we have that for every k=0,1,…,n,
(3.4)ck(S)≥ck(S′),
with equality if and only if k∈{0,1,n-1,n}.
It is easy to see thatT-xy=S-uv and T′-xy=S′-uv. We know that the numbers of the same tree of spanning forests of T-xy and T′-xy with exactly k components are equal to the numbers of the same tree of spanning forests of S-uv and S′-uv with exactly k components, respectively.
Applying to Definition3.1 and Lemma 2.1, we can show that for every k=0,1,…,n,
(3.5)ck(G)≥ck(G1),
with equality if and only if k∈{0,1,n-1,n}.Figure 1
Example ofπ1-transformation.Definition 3.3.
Letv be a vertex in a cycle C of a connected unicyclic graph G, where d(v)≥3. Suppose that u is one of two neighbors adjacent to v in C, such that u has degree p+2 and p pendent paths incident with u and v has degree q+2 and q pendent paths incident with v. Let
(3.6)G2=G-vvq+1+uvq+1≜π2(G),
where vq+1 is one of the other neighbors adjacent to v in C. We say that G2 is a π2-transformation of G (see Figure 2).Figure 2
Example ofπ2-transformation.Obviously,π2-transformation decreases the size of a cycle of G and preserves the number of pendent vertices.Theorem 3.4.
LetG be a connected unicyclic graph with n vertices and m pendent vertices, G2=π2(G). Then for every k=0,1,…,n,
(3.7)ck(G)≥ck(G2),
with equality if and only if k∈{0,1,n}.Proof.
Obviously,c0(G2)=c0(G)=1,c1(G2)=2|E(G2)|=2|E(G)|=c1(G),cn(G2)=cn(G)=0. For k=n-1, the length of a cycle in G is greater than the length of a cycle in G2. Therefore, cn-1(G)>cn-1(G2).
Now, consider the coefficientscn-k (k≠0,1,n-1,n). Let ℱk and ℱk2 be the sets of spanning forests of G and G2 with exactly k components, respectively. Let F2∈ℱk2 and T′ be the component of F2 and u∈V(T′). If vq+1∈V(T′), we define F with V(F)=V(G) and
(3.8)E(F)=E(F2)-uvq+1+vvq+1.
Now, we distinguish F2 as the following two cases.
Case  1 (v∈V(T′)). We have trees of equal sizes in both spanning forests thus γ(F)=γ(F2).
Case  2 (v∉V(T′)). Let vertex v be in the tree S′, that is, v∈V(S′).
Note the fact thatuv is a cut edge of G2. It is easy to see that F is a spanning forest of G, and the number of components of F is k-1 or k. We claim that F∈ℱk. Otherwise, u,v belong to one tree of F; then there exists a path P joining vq+1 to u in F; then uPvq+1u is a cycle of F2, which contradicts the fact that F2 is a forest.
Suppose thatT′-vq+1 contains a≥1 vertices in the cycle C (including u) and b≥0 vertices in the paths P1,…,Pp, and T′-u contains c≥1 vertices in the cycle C. Let S′ contain d≥1 in the paths Pp+1,…,Pp+q. Assume the orders of the components of F2 different from T′ and S′ are n1,n2,…nk-2. We have
(3.9)γ(F)-γ(F2)=[(a+b)(c+d)-(a+b+c)d]∏i=1k-2‍ni=c(a+b-d)∏i=1k-2‍ni=c(a+b-d)N,
where N=∏i=1k-2‍ni.
If we sum all differences for such forest, having fixed valuesa,c and b+d=M, we get
(3.10)∑F∈ℱ*‍γ(F)-γ(F2)=∑F∈ℱ*‍c(a+b-d)N=cN∑b=0M-1‍(a+2b-M)=(a-1)cNM.
It is easy to see thata≥1 and c≥1, so (a-1)cNM≥0. Since at least one vertex is in C-u-vq+1, there exists one forest F2 such that a>1 and c≥1, and then (a-1)cNM>0.
Ifvq+1∉V(T′), thus γ(F)=γ(F2).
Therefore, by using Lemma2.1, we get
(3.11)ck(G)=∑F∈ℱk‍γ(F)>∑F2∈ℱk2‍γ(F2)=ck(G2).
This completes the proof of Theorem 3.4.Definition 3.5.
Letv (not in the cycle C) be a vertex of degree q+1 in a connected unicyclic graph G. Suppose that Pp+1,…,Pp+q are pendent paths incident with v. Let u be the neighbor of v distinct from the starting vertices of paths v1,v2,…,vq, respectively. Let
(3.12)G3=π3(G)=G-vv2-vv3-⋯-vvq+uv2+uv3+⋯+uvq.
We say that G3 is a π3-transformation of G (see Figure 3).Figure 3
Example ofπ3-transformation.It is not difficult to see thatπ3-transformation preserves the size of a cycle of G and the number of pendent vertices.Theorem 3.6.
LetG be a connected unicyclic graph with n vertices and m pendent vertices, G3=π3(G). Then for every k=0,1,…,n,
(3.13)ck(G)≥ck(G3),
with equality if and only if k∈{0,1,n-1,n}.Proof.
Obviously,c0(G3)=c0(G)=1,c1(G3)=2|E(G3)|=2|E(G)|=c1(G),cn(G3)=cn(G)=0, cn-1(G3)=nτ(G3)=n|E(C)|=nτ(G)=cn-1(G).
Now, consider the coefficientscn-k (k≠0,1,n-1,n). Let ℱk and ℱk3 be the sets of spanning forests of G and G3 with exactly k components, respectively. Obviously, by the definition of the spanning forest, the cycle C in the unicyclic graph satisfies that C∉F∈ℱk and C∉F3∈ℱk3, where F and F3 are the arbitrary forests in ℱk and ℱk3, respectively. Without loss of generality, we remove one of the edges on the cycle, say wu, so we get two trees T and T′, respectively. Applying to Definition 2.7, we know that T′=δ(T). Then using Lemma 2.8, we can get that for every k=0,1,…,n,
(3.14)ck(T)≥ck(T′),
with equality if and only if k∈{0,1,n-1,n}. If we remove another edge, say xy, we get S and S′, respectively. By Definition 2.7, we know that S′=δ(S). Then applying to Lemma 2.8, we get that for every k=0,1,…,n,
(3.15)ck(S)≥ck(S′),
with equality if and only if k∈{0,1,n-1,n}.
It is easy to see thatT-xy=S-uv and T′-xy=S′-uv. We know that the numbers of the same tree of spanning forests of T-xy and T′-xy with exactly k components are equal to the numbers of the same tree of spanning forests of S-uv and S′-uv with exactly k components, respectively.
By Definition3.5 and Lemma 2.1, we have that for every k=0,1,…,n,
(3.16)ck(G)≥ck(G3),
with equality if and only if k∈{0,1,n-1,n}.Definition 3.7.
Letu, v, and w be three vertices on the triangle in a unicyclic graph G. Suppose that P1,…,Pp are pendent paths incident with u, Pp+1,…,Pp+q are pendent paths incident with v, and Pp+q+1,…,Pp+q+l are pendent paths incident with w(p+q+l=m). Let
(3.17)G4=G-vv1-⋯-vvq+uv1+⋯+uvq≜π4(G).
We say that G4 is a π4-transformation of G (see Figure 4).Figure 4
Example ofπ4-transformation.Theorem 3.8.
Letu, v, and w be three vertices on the triangle in a unicyclic graph G, G4=π4(G). Then for every k=0,1,…,n,
(3.18)ck(G)≥ck(G4),
with equality if and only if k∈{0,1,n-1,n}.Proof.
It is obvious to see thatc0(G4)=c0(G)=1,c1(G4)=2|E(G4)|=2|E(G)|=c1(G),cn(G4)=cn(G)=0. For k=n-1, the length of a cycle in G4 is equal to the length of a cycle in G. Therefore, cn-1(G)=cn-1(G4).
Now, consider the coefficientcn-k (k≠0,1,n-1,n). Let ℱk and ℱk4 be the sets of spanning forests of G and G4 with exactly k components, respectively.
Similarly to the proof of Theorem3.2, we can get 6 trees as shown in Figure 5. Obviously, by Definition 2.7, we know that Ti′=δ(Ti) (i=1,2,3). And according to Lemma 2.8, we can verify that
(3.19)ck(T1)≥ck(T1′),ck(T2)≥ck(T2′),ck(T3)≥ck(T3′).
By , Definition 3.7, and Lemma 2.1, it is easy to see that for every k=0,1,…,n,
(3.20)ck(G)≥ck(G4),
with equality if and only if k∈{0,1,n-1,n}. This completes the proof of Theorem 3.8.Figure 5
Obtained trees from Figure4.Theorem 3.9.
LetG be a connected unicyclic graph with n vertices and m pendent vertices. Then for 0≤k≤n,
(3.21)ck(G)≥ck(S′(n,m)),
with equality if and only if k∈{0,1,n}, where S′(n,m) is as shown in Figure 6, and each of the m branches at v is a path of length ⌊(n-3)/m⌋ or ⌈(n-3)/m⌉.Figure 6
S
′
(
n
,
m
).Proof.
LetC=w1w2⋯wtw1 be a cycle of connected unicyclic graph G, and let Ti be a tree attached at wi, i=1,2,…,t. We can apply π3-transformation to Ti, such that the tree contains one branch vertex wi with pendent path attached to it. Next, we can apply π2-transformation to decrease the size of the cycle C as long as the length of C is not 3. Then we can apply π1-transformation at the longest and the shortest path repeatedly, the Laplacian coefficients do not increase while the attached paths become more balanced. Finally, we can apply π4-transformation as long as it is not S′(n,m).
According to Theorems3.2, 3.4, 3.6, and 3.8, we know that πi-transformation (i=1,2,3,4) cannot increase the Laplacian coefficients. So, for an arbitrary unicyclic graph G with n vertices and m pendent vertices, we verify that
(3.22)ck(G)≥ck(S′(n,m)),
where 0≤k≤n and with equality if and only if k=0,1,n. This completes the proof of Theorem 3.9.


## 4. Laplacian-Like Energy of Unicyclic Graphs withm Pendent Vertices

LetG be a graph. The Laplacian-like energy of graph G, LEL for short, is defined as follows:
(4.1)LEL(G)=∑k=1n-1‍μk,
where μ1≥μ2≥⋯≥μn=0 are the Laplacian eigenvalues of G. This concept was introduced by J. Liu and B. Liu [9], where it was demonstrated it has similar feature as molecular graph energy (for more details see [15]). Stevanović in [10] presented a connection between LEL and Laplacian coefficients.Theorem 4.1.
LetG and H be two graphs with n vertices. If ck(G)≤ck(H) for k=1,2,…,n-1, then LEL(G)≤LEL(H). Furthermore, if a strict inequality ck(G)<ck(H) holds for some 1≤k≤n-1, then LEL(G)<LEL(H).Using this result, we can conclude the following.Corollary 4.2.
LetG be a connected unicyclic graph with n vertices and m pendent vertices. Then if G≇S′(n,m)(4.2)LEL(S′(n,m))<LEL(G),
where S′(n,m) is shown in Figure 6, and each of the m branches at v is a path of length ⌊(n-3)/m⌋ or ⌈(n-3)/m⌉.



---

*Source: 404067-2012-10-09.xml*