# Bounds for Incidence Energy of Some Graphs

Authors: Weizhong Wang; Dong Yang
Journal: Journal of Applied Mathematics
 (2013)

---

## Abstract

LetG be a simple graph. The incidence energy (IE for short) of G is defined as the sum of the singular values of the incidence matrix. In this paper, a new upper bound for IE of graphs in terms of the maximum degree is given. Meanwhile, bounds for IE of the line graph of a semiregular graph and the paraline graph of a regular graph are obtained.


---

## Body

## 1. Introduction

LetG be a finite, simple, and undirected graph with n vertices. The matrix L(G)=D(G)-A(G) (resp., L+(G)=D(G)+A(G)) is called the Laplacian matrix (resp., signless Laplacian matrix [1–4]) of G, where A(G) is the adjacency matrix and D(G) is the diagonal matrix of the vertex degrees. (For details on Laplacian matrix, see [5, 6].) Since A(G), L(G) and L+(G) are all real symmetric matrices, their eigenvalues are real numbers. So, we can assume that λ1(G)≥λ2(G)≥⋯≥λn(G) (resp., μ1(G)≥μ2(G)≥⋯≥μn(G), μ1+(G)≥μ2+(G)≥⋯≥μn+(G)) are the adjacency (resp., Laplacian, signless Laplacian) eigenvalues of G. It follows from the Geršgorin disc theorem that L(G) and L+(G) are semidefinite. Therefore, all Laplacian (resp., signless Laplacian) eigenvalues of G are nonnegative. If the graph G is connected, then μi(G)>0 for i=1,2,…,n-1 and μn(G)=0 [6]. If G is a connected nonbipartite graph, then μi+(G)>0 for i=1,2,…,n [1].One of the most remarkable chemical applications of graph theory is based on the close correspondence between the graph eigenvalues and the molecular orbital energy levels ofπ-electrons in conjugated hydrocarbons. For the Hüchkel molecular orbital approximation, the total π-electron energy in conjugated hydrocarbons is given by the sum of absolute values of the eigenvalues corresponding to the molecular graph G in which the maximum degree is not more than four in general. The energy of G was defined by Gutman in [7] as
(1)E(G)=∑i=1n‍|λi(G)|.
Research on graph energy is nowadays very active, as seen from the recent papers [8–15], monograph [16], and the references quoted therein.The singular values of a real matrix (not necessarily square)M are the square roots of the eigenvalues of the matrix MMt, where Mt denotes the transpose of M. Recently, Nikiforov [17] extended the concept of graph energy to any matrix M by defining the energy E(M) to be the sum of singular values of M. Obviously, E(G)=E(A(G)).LetI(G) be the (vertex-edge) incidence matrix of the graph G. For a graph G with vertex set {v1,v2,…,vn} and edge set {e1,e2,…,em}, the (i,j)-entry of I(G) is 0 if vi is not incident with ej and 1 if vi is incident with ej. Jooyandeh et al. [18] introduced the incidence energy IE of G, which is defined as the sum of the singular values of the incidence matrix of G. Gutman et al. [19] showed that
(2)IE=IE(G)=∑i=1n‍μi+(G).
Some basic properties of IE may be found in [18–20].A line graph is a classical unary operation of graphs with finite number and infinite number of vertices. Its basic properties can be found in any text book on graph theory (see, e.g., [21–23]). Recently, several papers on line graph have been published [20, 24–27]. For example, Gao et al. [24] established a formula and lower bounds for the Kirchhoff index of the line graph of a regular graph. Bounds for Laplacian-energy-like invariant (LEL for short) of the line graph of a regular graph G are obtained in [26]. For details on LEL, see the comprehensive survey [28].From (2), one can immediately get the incidence energy of a graph by computing the signless Laplacian eigenvalues of the graph. However, even for special graphs, it is still complicated to find the signless Laplacian eigenvalues of them. Hence, it makes sense to establish lower and upper bounds to estimate the invariant for some classes of graphs. Zhou [29] obtained the upper bounds for the incidence energy using the first Zagreb index. Gutman et al. [20] gave several lower and upper bounds for IE. In particular, an upper bound for IE of the line graph of a regular graph was established in [20].In this paper, we continue to study the bounds forIE of graphs. In Section 2, we give a new upper bound for IE of graphs in terms of the maximum degree. Bounds for IE of the line graph of a semiregular graph and the paraline graph of a regular graph are obtained in Section 3.


## 2. A New Upper Bound forIE

In this section, we will give a new upper bound forIE of a nonempty graph. The following fundamental properties of the IE were established in [18].Lemma 1 (see [18]).
LetG be a graph with n vertices and m edges. Then(i)
IE(G)≥0, and equality holds if and only if m=0;(ii)
ifG1,…,Gp are all components of G, then IE(G)=∑ip‍IE(Gi).From Lemma1(ii), when we study the incidence energy of a graph G, we may assume that G is connected.The following lemma will be used later.Lemma 2 (see [3]).
LetG be a connected graph without vertices of degree 1 and the maximum degree Δ. Then, μ1+≥1+Δ+(1/(Δ-1)); the equality holds if and only if G is a cycle.Denote byCn the cycle with n vertices.Theorem 3.
LetG be a connected graph without vertices of degree 1 and the maximum degree Δ. Then
(3)IE(G)≤1+Δ+1Δ-1IE(G)≤+(n-1)(2m-1-Δ-1Δ-1);
the equality holds if and only if G≅C3.Proof.
Note that∑i=2n‍μi+=2m-μ1+. By the Cauchy-Schwarz inequality
(4)IE(G)≤μ1++(n-1)(2m-μ1+).
The equality holds if and only if μ2+=⋯=μn+.
We consider the function(5)f(x)=x+(n-1)(2m-x),x>0.
Then
(6)f′(x)=12x+-n+12(n-1)(2m-x).
It is easily seen that the function f(x) is decreasing for x>2m/n. By Lemma 2,
(7)2mn≤Δ<1+Δ<1+Δ+1Δ-1≤μ1+.
Inequality (3) follows now from the monotonicity of f(x) and (4).
Equality in (3) holds if and only if G is a cycle. It is well-known [4] that the signless Laplacian eigenvalues of Cn are
(8)2+2cos2πnj(j=0,1,…,n-1).
If G≅C3, then we may verify directly that the equality in (3) holds.
Conversely, if the equality in (3) holds, then
(9)μ1+=1+Δ+1Δ-1,μ2+=⋯=μn+.
It follows from Lemma 2 that G is a cycle. Note that G has at most two distinct signless Laplacian eigenvalues. By virtue of (8), we now conclude that G is a triangle.Recall from [20] that an upper bound for IE was given as follows.Lemma 4 (see [20]).
LetG be a connected graph with n≥3 vertices and m edges. Then
(10)IE(G)<1+Δ+(n-1)(2m-1-Δ).Remark 5.
It should be pointed out that, for a connected graph without vertices of degree 1, the bound in (3) is better than the bound in (10). Indeed, it is easily seen that the bound in (3) is f(1+Δ+(1/(Δ-1))), but the bound in (10) is f(1+Δ). Note that
(11)2mn≤Δ<1+Δ<1+Δ+1Δ-1≤μ1+.
It follows from the monotonicity of f(t) that
(12)f(1+Δ+1Δ-1)<f(1+Δ).
That is,
(13)1+Δ+1Δ-1+(n-1)(2m-1-Δ-1Δ-1)<1+Δ+(n-1)(2m-1-Δ).


## 3. Bounds forIE of Line Graphs of Semiregular Graphs

In this section, we will investigate theIE of the line graph of an (r,s)-semiregular graph and the paraline graph of an r-regular graph.We first consider the case for line graph. The line graphℒ(G) of a graph G is the graph whose vertex set is in one-to-one correspondence with the set of edges of G where two vertices of ℒ(G) are adjacent if and only if the corresponding edges in G have a vertex in common. For instance, the line graph of a star Sn on n vertices is a complete graph Kn-1 on n-1 vertices.The following result is well known [30].Lemma 6 (see [30]).
LetA be a matrix. Then, the matrices AAT and ATA have the same nonzero eigenvalues.A bipartite graphG with a bipartition V(G)=U∪W is called an (r,s)-semiregular graph if all vertices in U have degree r and all vertices in W have degree s. Denote by μG+(x) the signless Laplacian polynomial det(xI-L+(G)) of G. For an (r,s)-semiregular graph G, we can establish the following relationship between μG+(x) and μℒ(G)+(x).Lemma 7.
LetG be an (r,s)-semiregular graph with n vertices. Then
(14)μℒ(G)+(μ)=(μ-(r+s-4))m-nμG+(μ-(r+s-4)),
where ℒ(G) is the line graph of G and m is the number of edges of G.Proof.
LetI(G) be the (vertex-edge) incidence matrix of a graph G. Then
(15)I(G)I(G)T=L+(G),I(G)TI(G)=2Im+A(ℒ(G)),
where Im stands for the unit matrix of order m.
Note that ifG is an (r,s)-semiregular graph, then the line graph of G is (r+s-2)-regular graph. Thus
(16)L+(ℒ(G))=(r+s-2)Im+A(ℒ(G)).
Combine (15) with (16), we have
(17)L+(ℒ(G))-(r+s-4)Im=I(G)TI(G).
It follows from Lemma 6, (15), and (17) that L+(G) and L+(ℒ(G))-(r+s-4)Im have the same nonzero eigenvalues. Note that the difference between the dimensions of L+(ℒ(G)) and L+(G) is  m-n. The proof is finished by the fact that the leading coefficient of the characteristic polynomial is equal to one.By Lemma7, the signless Laplacian eigenvalues of ℒ(G) are
(18)(r+s-4r+s-4+μ1+r+s-4+μ2+⋯r+s-4+μn+m-n11⋯1),
where μ1+≥μ2+≥⋯≥μn+ are the signless Laplacian eigenvalues of G.Theorem 8.
LetG be an (r,s)-semiregular graph with n vertices. Then
(19)IE(ℒ(G))≤(nrsr+s-n+1)r+s-4+2(r+s)-4IE(ℒ(G))≤+(n-2)[(n-3)(r+s)-4(n-2)+2nrsr+s],
the equality holds if and only if G≅K1,n-1, or n is even and G≅K(n/2),(n/2) with n≥4.Proof.
Letm be the number of edges of G. Then, m=nrs/(r+s). Note that μ1+(G)=r+s. It follows from (2) and (18) that
(20)IE(ℒ(G))=(m-n)r+s-4+∑i=1n‍r+s-4+μi+IE(ℒ(G))=(m-n)r+s-4+2(r+s)-4IE(ℒ(G))=+∑i=2n‍r+s-4+μi+.
Note also that μn+=0, ∑i=1n‍μi+=2m. By the Cauchy-Schwarz inequality, we have
(21)∑i=2n‍r+s-4+μi+=r+s-4+∑i=2n-1‍r+s-4+μi+≤r+s-4+(n-2)∑i=2n-1‍(r+s-4+μi+)=r+s-4+(n-2)[(n-2)(r+s)-4(n-2)+(2m-μ1+)]=r+s-4+(n-2)[(n-3)(r+s)-4(n-2)+2nrsr+s].
Inequality (19) follows now from (20) and (21).
Clearly, equality in (19) holds if and only if μ2+=⋯=μn-1+. Suppose that μ2+=⋯=μn-1+. Then, the number of distinct signless Laplacian eigenvalues of G is at most 3. From the result, “the number of distinct signless Laplacian eigenvalues of a connected graphs with diameter d is at least d+1 [1],” we know that the diameter of G is at most 2. Note that G is bipartite graph. If the diameter of G is 1, then G must be K2. If the diameter of G is 2, then G is a complete bipartite graph Kp,q with exactly 3 distinct signless Laplacian eigenvalues. It is well known that the signless Laplacian eigenvalues of Kp,q are p+q, pq-1, qp-1, and 0. Thus, G≅K1,n-1, or n is even and G≅K(n/2),(n/2) with n≥4.
Conversely, ifG≅K1,n-1, then ℒ(G)≅Kn-1. Note that the signless Laplacian spectrum of complete graph Kt [4] is
(22)(t-22t-2t-11).
It follows from (2) and (22) that
(23)IE(ℒ(G))=IE(Kn-1)=2n-4+(n-2)n-3.
That is, the left-hand side of (19) is equal to 2n-4+(n-2)n-3. In this case, r=n-1 and s=1. It is easy to check that the right-hand side of (19) is also equal to 2n-4+(n-2)n-3. If G≅K(n/2),(n/2), then ℒ(G)≅L2(n/2), where n≥4 is even. Note also that the signless Laplacian spectrum of lattice graph L2(p) [31] is
(24)(2p-44p-43p-4(p-1)212p-2).
Similarly, it follows from (2) and (24) that the left-hand side of (19) is equal to (n/2-1)2n-4+2n-4+(n-2)3n/2-4. Note that K(n/2),(n/2) is an (n/2,n/2)-semiregular graph. Substituting r=s=n/2 into (19), we get the right-hand side of (19) is still equal to (n/2-1)2n-4+2n-4+(n-2)3n/2-4.
Hence, we complete the proof of Theorem8.Now, we consider the case for paraline graph. LetG be a simple graph. A paraline graph, denoted by C(G), is defined as a line graph of the subdivision graph s(G) (the subdivision graph s(G) of a graph G is the graph obtained from G by inserting a vertex to every edge of G) of G (e.g., see Figure 1). The concept of the paraline graph (or clique-inserted graph [32]) of a graph was first introduced in [25], where the author obtained the spectrum of the paraline graph of a regular graph G with infinite number of vertices in terms of the spectrum of G.(a) The graphG. (b) The graph s(G). (c) The graph C(G).
(a)
(b)
(c)Remark 9.
The subdivision graph of anr-regular graph is (r,2)-semiregular. Hence, the paraline graph of an r-regular graph is the line graph of an (r,2)-semiregular graph.The following result is well known [5, 6].Lemma 10.
The spectra ofL(G) and L+(G) coincide if and only if the graph G is bipartite.LetμG(x) be the Laplacian polynomial det(xI-L(G)) of G.Corollary 11.
LetG be an r-regular graph with n vertices. Then
(25)μC(G)+(μ)=(-1)nr((r-μ)(μ-r+2))nr/2-n×μG((2r-μ)(μ-r+2)).Proof.
Note thats(G) is a (2,r)-semiregular graph with n+nr/2 vertices and nr edges. By Lemma 7, we obtain
(26)μC(G)+(μ)=(μ-r+2)m-nμs(G)+(μ-r+2).
It is shown in [33] that
(27)μs(G)(μ)=(-1)m(2-μ)m-nμG(μ(r+2-μ)).
It follows from (27) and Lemma 10 that
(28)μs(G)+(μ)=(-1)m(2-μ)m-nμG(μ(r+2-μ)).
Combining (26) with (28), we have
(29)μC(G)+(μ)=(-1)nr((r-μ)(μ-r+2))nr/2-n×μG((2r-μ)(μ-r+2)).It follows from Corollary11 that the signless Laplacian spectrum of C(G) is(30)(rr-2μ1+(C(G))μ1′+(C(G))⋯μn+(C(G))μn′+(C(G))n(r-2)2n(r-2)211⋯11),where
(31)μi+(C(G))=3r-2+(r+2)2-4μi2,μi′+(C(G))=3r-2-(r+2)2-4μi2,
and μi, i=1,2,…,n are the Laplacian eigenvalues of G.Theorem 12.
LetG be a connected r-regular graph with n vertices. Then
(32)IE(C(G))≤(nr2+2-1)r+2(n-1)r-1IE(C(G))≤+(nr2-n+1)r-2;
the equality holds if and only if G≅K2.Proof.
Ifr=1, then G≅K2. Note that C(K2)≅K2. It is easily seen that
(33)IE(C(K2))=2.
In this case, r=1 and n=2. Hence
(34)(nr2+2-1)r+2(n-1)r-1+(nr2-n+1)r-2=2.
Suppose now thatr≥2. For convenience, let m=nr/2 be the edges of G. Note that G is an r-regular graph. It follows from the definition of paraline graph that C(G) is still an r-regular graph. Note also that μi(G)=r-λn-i+1(G),i=1,2,…,n and λ1(G)=r. Then by (2) and (30), we have
(35)IE(C(G))=(m-n)r+(m-n)r-2+∑i=1n‍3r-2+r2+4(λi+1)2+∑i=1n‍3r-2-r2+4(λi+1)2=(m-n+2)r+(m-n+1)r-2+∑i=2n‍(3r-2+r2+4(λi+1)2+3r-2-r2+4(λi+1)2).
Note that  -r≤λi(G)<r,i=2,3,…,n, by the Perron-Frobenius theorem. Consider the function
(36)g(t)=3r-2+r2+4t+42g(t)=+3r-2-r2+4t+42,-r≤t<r.
The derivative function of g(t) is
(37)g′(t)=(3r-2-r2+4t+42g′(t)=-3r-2+r2+4t+42)g′(t)=×(2(2r2-(3r+t))(r2+4t+4))-1,-r≤t<r.
It is clear that g(t) is decreasing for -r≤t<r. Therefore
(38)IE(C(G))≤(m-n+2)rIE(C(G))≤+(m-n+1)r-2+∑i=2n‍g(-r)IE(C(G))=(nr2+2-1)r+2(n-1)r-1IE(C(G))≤+(nr2-n+1)r-2.
That is,IE(C(G))=(m-n+2)r+(m-n+1)r-2+∑i=2n‍g(-r) if and only if G is regular graph and λ1(G)=r,λ2(G)=⋯=λn(G)=-r. It follows that G is a regular graph with two distinct adjacency eigenvalues r and -r with multiplicities 1 and n-1, respectively. Then by Proposition 1.3.3 [31], G must be a complete graph. Note that the sum of the adjacency eigenvalues of G is equal to zero; that is, r+(n-1)(-r)=0. It follows that G is a complete graph with two vertices; that is, G≅K2. This is impossible since r≥2.
Summing up, we complete the proof.Theorem 13.
LetG be an r-regular graph with n vertices, r≥2. Then
(39)IE(C(G))>n(r+22-2)2r+nr2r-2.Proof.
From the proof of Theorem12, we know that the function g(t) is decreasing for -r≤t<r. Therefore
(40)IE(C(G))>(m-n+2)rIE(C(G))>+(m-n+1)r-2+∑i=2n‍g(r)IE(C(G))=n(r+22-2)2r+nr2r-2.



---

*Source: 757542-2013-07-28.xml*