# Bounds on the Distance Energy and the Distance Estrada Index of Strongly Quotient Graphs

Authors: Ş. Burcu Bozkurt; Chandrashekara Adiga; Durmuş Bozkurt
Journal: Journal of Applied Mathematics
 (2013)

---

## Abstract

The notion of strongly quotient graph (SQG) was introduced by Adiga et al. (2007). In this paper, we obtain some better results for the distance energy and the distance Estrada index of any connected strongly quotient graph (CSQG) as well as some relations between the distance Estrada index and the distance energy. We also present some bounds for the distance energy and the distance Estrada index of CSQG whose diameter does not exceed two. Additionally, we show that our results improve most of the results obtained by Güngör and Bozkurt (2009) and Zaferani (2008).


---

## Body

## 1. Introduction

Since the distance matrix and related matrices based on graph-theoretical distances are efficient sources of many topological indices that are widely used in theoretical chemistry [1, 2], it is of interest to study spectrum and spectrum-based invariants of these matrices.LetG be a connected graph with n vertices and m edges and let the vertices of G be labeled as v1,v2,…,vn. Such a graph will be referred to as connected (n,m)-graph. Let D=D(G) be the distance matrix of the graph G, where dij denotes the distance (i.e., the length of the shortest path [3]) between the vertices vi and vj of G. The diameter of the graph G, denoted by diam(G), is the maximum distance between any two vertices of G. The eigenvalues of D(G) are said to be the D-eigenvalues of G. Since D(G) is a real symmetric matrix, its eigenvalues are real numbers. So, we can order them so that μ1≥μ2≥⋯≥μn. For more details on D-eigenvalues, especially on μ1, see [3–12].The distance energy of the graphG is defined as [13]
(1)ED=ED(G)=∑i=1n|μi|.
This concept was motivated by the ordinary graph energy which is defined as the sum of absolute values of ordinary graph eigenvalues [14–16]. It was also studied intensely in the literature. For instance, Indulal et al. [13] reported lower and upper bounds for the distance energy of graphs whose diameter does not exceed two. In [17] Ramane et al. generalized the results obtained in [13]. Zhou and Ilić [10] established lower bounds for the distance energy of graphs and characterized the extremal graphs. They also discussed upper bounds for the distance energy. Ilić [18] calculated the distance energy of unitary Cayley graphs and presented two families of integral circulant graphs with equal distance energy. Zaferani [19] established an upper bound for the distance energy of strongly quotient graphs. For more results on distance energy, see also the recent papers [6, 20].Recently, another graph invariant based on graph eigenvalues was put forward in [21]. It was eventually studied under the name Estrada index in [22]. For more details on Estrada index, see [21–27]. Motivating the ideas in [21, 22] and considering the distance matrix of the graph G, the authors defined the distance Estrada index of G as the following [28]:
(2)DEE=DEE(G)=∑i=1neμi.
In [28], they also established some lower and upper bounds for this index.During the past forty years or so enormous amount of research work has been done on graph labeling, where the vertices are assigned values subject to certain conditions. These interesting problems have been motivated by practical problems. Recently, Adiga et al. [29] introduced the notion of strongly quotient graphs and studied these types of graphs. Throughout this paper by a labeling f of a graph G of order n we mean an injective mapping
(3)f:V(G)⟶{1,2,…,n}.
We define the quotient function
(4)fq:E(G)⟶Q
by
(5)fq(e)=min{f(v)f(w),f(w)f(v)}
if e joins v and w. Note that for any e∈E(G),  0<fq(e)<1.A graph withn vertices is called a strongly quotient graph if its vertices can be labeled 1,2,…,n such that the quotient function fq is injective, that is, the values fq(e) on the edges are all distinct. For detailed information on graph labeling and strongly quotient graphs, see [19, 23, 29, 30]. Throughout this paper SQG and CSQG stand for strongly quotient graph and connected strongly quotient graph of order n with maximum number of edges, respectively.In this paper, we obtain some bounds for the distance energyED(G) and the distance Estrada index DEE(G) as well as some relations between DEE(G) and ED(G) where G is CSQG. We present some bounds for ED(G) and DEE(G) of CSQG whose diameter does not exceed two. We also show that our results improve most of the results obtained in [19, 28] for CSQG.


## 2. Preliminaries

In this section, we give some lemmas which will be used in our main results.Lemma 1 (see [31]).
Leta1,a2,…,an be nonnegative numbers. Then
(6)n[1n∑i=1nai-(∏i=1nai)1/n]≤n∑i=1nai-(∑i=1nai)2≤n(n-1)[1n∑i=1nai-(∏i=1nai)1/n].Lemma 2 (see [17]).
LetG be a connected (n,m)-graph and μ1,μ2,…,μn its D-eigenvalues. Then
(7)∑i=1nμi=0,(8)∑i=1nμi2=2∑i<j(dij)2.Lemma 3 (see [13]).
LetG be a connected (n,m)-graph and let diam(G)≤2, where diam(G) denotes the diameter of the graph G. Then
(9)∑i=1nμi2=2(2n2-2n-3m).Lemma 4 (see [28]).
LetG be a connected (n,m)-graph and diam(G) be the diameter of G. Then
(10)∑i<j(dij)2≤n(n-1)2diam2(G).
The equality holds in (10) if and only if G≅Kn.Lemma 5 (see [19]).
IfG is a SQG, then -1 is a D-eigenvalue of G with multiplicity greater than or equal to |P|=l, where
(11)P={p:pisprimeandn2<p≤n}.Lemma 6 (see [19]).
IfG is a SQG, then -2 is a D-eigenvalue of G with multiplicity greater than or equal to s where
(12)s=∑p-primep≤[n/2]([logpn]-1).


## 3. Bounds on Distance Energy of CSQG

In this section, we will present a better upper bound and a new lower bound forED(G) where G is CSQG with D-eigenvalues μ1,μ2,…,μn. Let n+ be the number of positive D-eigenvalues of G and l and s are as defined in Lemmas 5 and 6, respectively. For our convenience, we rename the D-eigenvalues such that μn-l-s+1=μn-l-s+2=⋯=μn-s=-1 and μn-s+1=μn-s+2=⋯=μn=-2.Theorem 7.
LetG be a connected strongly quotient graph (CSQG) with n>3 vertices and maximum edges m. Let P={p:pisprimeand(n/2)<p≤n} and |P|=l. Then
(13)ED(G)≥l+2s+W+(n-l-s)(n-l-s-1)ϕ2/n-l-s,(14)ED(G)≤l+2s+(n-l-s-1)W+(n-l-s)ϕ2/n-l-s,
where
(15)ϕ=∏i=1n-l-s|μi|=|detD|2s,s=∑p-primep≤[n/2]([logpn]-1),W=2∑i<j(dij)2-l-4s.Proof.
Takingai=μi2 and replacing n by n-l-s in Lemma 1, we obtain
(16)K≤(n-l-s)∑i=1n-l-sμi2-(∑i=1n-l-s|μi|)2≤(n-l-s-1)K,
where
(17)K=(n-l-s)[1n-l-s∑i=1n-l-sμi2-(∏i=1n-l-sμi2)1/n-l-s].
By Lemmas 5 and 6, we know that -1 and -2 are the D-eigenvalues of the strongly quotient graph G with multiplicity greater than or equal to l and s, respectively. Therefore, considering (8) we obtain
(18)K≤(n-l-s)(2∑i<j(dij)2-l-4s)-(ED(G)-l-2s)2≤(n-l-s-1)K.
Observe that
(19)K=(n-l-s)[1n-l-s∑i=1n-l-sμi2-(∏i=1n-l-sμi2)1/n-l-s]=(n-l-s)[1n-l-s(2∑i<j(dij)2-l-4s)(n-l-s)-(∑i=1n-l-s|μi|)2/n-l-s]=W-(n-l-s)ϕ2/n-l-s.
Hence we get the result.Remark 8.
In [19] Zaferani obtained the following upper bound for the distance energy of CSQG:
(20)ED(G)≤l+2s+(n-l-s)(2∑i<j(dij)2-l-4s).
The upper bound (14) is better than the upper bound (20). Using the Arithmetic-Geometric Mean Inequality, we can easily see that
(21)W=2∑i<j(dij)2-l-4s≥(n-l-s)ϕ2/n-l-s.
Considering this and the upper bound (14), we arrive at
(22)ED(G)≤l+2s+(n-l-s-1)W+(n-l-s)ϕ2/n-l-s≤l+2s+(n-l-s)W-(n-l-s)ϕ2/n-l-s+(n-l-s)ϕ2/n-l-s=l+2s+(n-l-s)(2∑i<j(dij)2-l-4s)
which is the upper bound (20).Using Theorem7 and Lemma 3, we can give the following result.Corollary 9.
LetG be a connected strongly quotient graph (CSQG) with n>3 vertices and maximum edges m and let diam(G)≤2, where diam(G) denotes the diameter of G. Then
(23)ED(G)≥l+2s+R+(n-l-s)(n-l-s-1)ϕ2/n-l-s,ED(G)≤l+2s+(n-l-s-1)R+(n-l-s)ϕ2/n-l-s,
where R=2(2n2-2n-3m)-l-4s.


## 4. Bounds on Distance Estrada Index of CSQG

In this section, we will use similar ideas as in [22, 24–27] to obtain some bounds for DEE(G), where G is CSQG. These bounds are based on the distance energy ED(G) and several other graph invariants.Theorem 10.
LetG be a connected strongly quotient graph (CSQG) with n>3 vertices and maximum edges m. Then
(24)DEE(G)≥se-2+le-1+(n-l-s)e(l+2s)/(n-l-s).Proof.
Using the Arithmetic-Geometric Mean Inequality, we get(25)DEE(G)=se-2+le-1+∑i=1n-l-seμi≥se-2+le-1+(n-l-s)(∏i=1n-l-seμi)1/(n-l-s)=se-2+le-1+(n-l-s)(e∑i=1n-l-sμi)1/(n-l-s).
From (7) and Lemmas 5 and 6, we have
(26)∑i=1n-l-sμi+s(-2)+l(-1)=0thatis,∑i=1n-l-sμi=l+2s.
Employing (25) and (26), we conclude that
(27)DEE(G)≥se-2+le-1+(n-l-s)e(l+2s)/(n-l-s).
This completes the proof.Theorem 11.
The distance Estrada indexDEE(G) and the distance energy ED(G) of CSQG with n>3 vertices and maximum edges m satisfy the following inequalities:
(28)DEE(G)≥se-2+le-1+12ED(G)(e-1)+(n+s-n+),(29)DEE(G)≤se-2+le-1+(n-l-s-1)+eED(G)/2.Proof.
Lower bound: Using Lemmas 5 and 6 and the inequalities ex≥xe and ex≥1+x, we obtain
(30)DEE(G)=∑i=1neμi=se-2+le-1+∑i=1n-l-seμi≥se-2+le-1+∑μi>0eμi+∑i=1μi≤0n-l-s(1+μi).
From (26), we get
(31)DEE(G)≥se-2+le-1+(e-1)(μ1+μ2+⋯+μn+)+(n-l-s-n+)+l+2s=se-2+le-1+12ED(G)(e-1)+(n+s-n+).
Hence the lower bound (28).
Upper bound: Considering f(x)=ex which monotonically increases in the interval (-∞,+∞), we obtain
(32)DEE=∑i=1neμi=se-2+le-1+∑i=1n-l-seμi≤se-2+le-1+(n-l-s-n+)+∑i=1n+eμi=se-2+le-1+(n-l-s-n+)+∑i=1n+∑k≥0(μi)kk!=se-2+le-1+(n-l-s)+∑k≥11k!∑i=1n+(μi)k≤se-2+le-1+(n-l-s)+∑k≥11k![∑i=1n+(μi)]k=se-2+le-1+(n-l-s-1)+eED(G)/2.
This completes the proof.Remark 12.
In [28] the following result was obtained for connected (n,m)-graphs
(33)DEE(G)≤n-1+eED(G).
Since the function f(x)=ex monotonically increases in the interval (-∞,+∞), we conclude that the upper bound (29) is better than the upper bound (33) for DEE(G) of CSQG with n>3 vertices and maximum edges m.Theorem 13.
The distance Estrada indexDEE(G) and the distance energy ED(G) of CSQG with n>3 vertices and maximum edges m satisfy the following inequality:
(34)DEE(G)-ED(G)<se-2+le-1+(n-l-s-1)-T+eT,
where T=n(n-1)diam2(G)-l-4s and diam(G) is the diameter of G.Proof.
From (32) and Lemma 2, we get
(35)DEE(G)≤se-2+le-1+(n-l-s)+∑k≥11k!∑i=1n+(μi)k=se-2+le-1+(n-l-s)+ED(G)2+∑k≥21k!∑i=1n+(μi)k<se-2+le-1+(n-l-s)+ED(G)+∑k≥21k!∑i=1n+(μi)k≤se-2+le-1+(n-l-s)+ED(G)+∑k≥21k![∑i=1n+(μi)2]k/2≤se-2+le-1+(n-l-s)+ED(G)(36)+∑k≥21k![2∑i<j(dij)2-∑i=n++1n(μi)2]k/2.
By Lemmas 5 and 6, we know that -1 and -2 are the D-eigenvalues of the strongly quotient graph G with multiplicity greater than or equal to l and s, respectively. These imply that
(37)∑i=n++1n(μi)2≥l+4s.
Therefore,
(38)DEE(G)-ED(G)<se-2+le-1+(n-l-s-1)-2∑i<j(dij)2-l-4s+e2∑i<j(dij)2-l-4s.
It is easy to see that the function f(x)=ex-x monotonically increases in the interval (0,+∞). Then by Lemma 4, we obtain
(39)DEE(G)-ED(G)<se-2+le-1+(n-l-s-1)-T+eT.
From (36) and Lemma 4, we also have
(40)DEE(G)-ED(G)2≤se-2+le-1+(n-l-s-1)-T+eT
that is better than the upper bound (34).From Theorem13 and Lemma 3, we can give the following result.Corollary 14.
LetG be a connected strongly quotient graph (CSQG) with n>3 vertices and maximum edges m and let diam(G)≤2, where diam(G) denotes the diameter of G. Then
(41)DEE(G)-ED(G)<se-2+le-1+(n-l-s-1)-R+eR,
where R=2(2n2-2n-3m)-l-4s.Remark 15.
In [28] the following result was obtained for a connected (n,m)-graph G(42)DEE(G)-ED(G)≤n-1-diam(G)n(n-1)+ediam(G)n(n-1).
Since the functions f(x)=ex and f(x)=ex-x monotonically increase in the intervals (-∞,+∞) and (0,+∞), respectively, we conclude that the upper bound (34) is better than the upper bound (42) for CSQG with n>3 vertices and maximum edges m.



---

*Source: 681019-2013-05-13.xml*