Energy And Harary Estrada Index

(1)

2

A Note On Strongly Quotient Graphs With Harary

3

Energy And Harary Estrada Index

4

Rajagopal Binthiya

^y

, Balakrishnan Sarasija

^z

5

Received 18 February 2014

6

Abstract

7

The main purpose of this paper is to investigate the upper and lower bounds

8

on Harary energy and Harary Estrada index on Strongly Quotient Graphs (SQG).

9

The notion of SQG was introduced by Adiga et al. in 2007. In addition, we have

10

established some relations between the Harary Estrada index and the Harary

11

energy of SQG.

12

1 Introduction

13

LetG(V; E)be a …nite undirected simple connected(n; m)graph with vertex setV =

14

V(G), edge set E = E(G), n = jVj and m = jEj. The vertices ofG are labeled by

15

v1; v2; :::; vn: The Harary matrixH(G) of a graph G is de…ned as a square matrix of

16

order n such asH(G) =H = h 1

dij

i

, where dij is the distance (i.e. the length of the

17

shortest path) between the vertices v_i and v_j in G in [4, 13]. The eigenvalues of the

18

Harary matrixH(G)are denoted as ₁; ₂; : : : ; _nand are said to be the H-eigenvalues

19

of G. For more details on H-eigenvalues, especially on the maximum eigenvalue of

20

Harary matrix of a graph Gand spectral properties of Grefer to [7, 8, 15]. It can be

21

noted that the H-eigenvalues ofGare real since the Harary matrix is symmetric. The

22

Harary energy of the graphG, denoted byHE(G), is de…ned as

23

HE(G) = Xn i=1

j ij:

24

Recently, there has been tremendous research activity in graph energy, as Harary

25

energy inevitably arouses the interest of chemists. Some lower and upper bounds for

26

Harary energy of connected (n; m)-graphs were obtained in [12]. The diameter of the

27

graphGis the maximum distance between any two vertices ofG, denoted bydiam(G).

28

The name Estrada index of the graph G was introduced in [9] which has an im-

29

portant role in Chemistry and Physics and there exists a vast literature that studies

30

Mathematics Sub ject Classi…cations: 58C40.

yDepartment of Mathematics, Noorul Islam Centre for Higher Education, Kumaracoil, Tamil Nadu 629180, India

zDepartment of Mathematics, Noorul Islam Centre for Higher Education, Kumaracoil, Tamil Nadu 629180, India

97

(2)

this special index. Recently, the bounds of distance Estrada index and Harary Estrada

31

index of a graphGare concerned in [11, 12]. The Harary Estrada index is de…ned as

32

HEE(G) = Xn i=1

e ⁱ:

33

During the past forty years or so, an enormous amount of research work has been done

34

on graph labeling, where the vertices are assigned values subject to certain conditions.

35

These interesting problems have been motivated by practical problems. Recently, Adiga

36

et al., have introduced the notion of strongly quotient graphs and studied these type

37

of graphs [2]. They derived an explicit formula for the maximum number of edges in

38

a strongly quotient graph of order n. In [1], Adiga and Zaferani have established that

39

the clique number and chromatic number are both equal to1 + (n), where (n)is the

40

number of primes not exceedingn. Throughout this paper by a labeling f of a graph

41

Gof ordern, we mean an injective mapping

42

f :V(G)! f1;2; : : : ; ng:

43

We de…ne the quotient functionfq :E(G)!Qby

44

fq(e) =min f(v) f(w);f(w)

f(v) ifejoins v andw:

45

Note that for anye2E(G); 0< fq(e)<1:

46

A graph with n vertices is called a strongly quotient graph if its vertices can be

47

labeled by1;2; : : : ; nsuch that the quotient functionfq is injective i.e., the valuesfq(e)

48

on the edges are all distinct. For survey and detailed information of graph labeling,

49

strongly quotient graphs, properties of strongly quotient graphs refer to [1, 2, 3, 5, 6,

50

10, 14]. Throughout this paper, SQG stands for strongly quotient graph of order n

51

with maximum number of edges.

52

We have organized this paper in the following way. In section 2, two eigen values

53

for Harary matrix of SQG are obtained. In Section 3, a lower bound and two upper

54

bounds are derived for the Harary energy of SQG. In Section 4, the Harary Estrada

55

index of SQG and some better lower and upper bounds are obtained for SQG involving

56

Harary energy and several other graph invariants.

57

2 Preliminaries

58

In this section, we have given some lemmas which will be used in our main results and

59

we have obtained two eigen values of SQG with respect to Harary matrix.

60

LEMMA 2.1 ([12]). LetGbe a connected(n; m)graph and let ₁; ₂; : : : ; _n be its

61

H-eigenvalues. Then

62

Xn i=1

i= 0and Xn i=1

2

i = 2 X

1 i<j n

1 d_ij

2

:

63

(3)

LEMMA 2.2 ([12]). LetGbe a connected(n; m)graph with diameter less than or

64

equal to2and let ₁; ₂; : : : ; _n be its H-eigenvalues. Then

65

Xn i=1

2 i =3m

2 +n

4(n 1):

66

LEMMA 2.3 ([16]). Letx1; x2; : : : ; xn be nonnegative numbers. Then

67

N n

Xn i=1

xi

Xn i=1

pxi

!2

(n 1)N;

68

where

69

N =n 2 41

n Xn i=1

xi

Yn i=1

xi

!1=n3 5:

70

The distance matrix D(G) = [d_ij] of a graph G is a square matrix of ordern in

71

whichd_ij =d(v_i; v_j). In [14], R. K. Zaferani obtained two eigen values for the distance

72

matrix of SQG. We recall that the SQG is a strongly quotient graph with the maximum

73

number of edges for a …xed order. From Theorems 3.2 and 3.3 in [14], we have obtained

74

the following results for Harary matrix H(G)of SQG. The notation bacdenotes the

75

‡ooring value ofa.

76

RESULT 2.4. If G is a SQG then 1 is the H-eigenvalue of G with multiplicity

77

greater than or equal to =jPjwhere

78

P = n

p:pis prime and n

2 < p n o

: (1)

79

RESULT 2.5. IfG is a SQG then ¹₂ is the H-eigenvalue of G with multiplicity

80

greater than or equal to where

81

= X

p-prim e p bⁿ²c

log_pn 1 :

82

3 Bounds on Harary Energy of SQG

83

In this section, we have presented some upper and lower bounds for Harary Energy

84

HE(G), whereGis SQG, with eigen values ₁; ₂; : : : ; _n. For our convenience we have

85

renamed the eigen values as

86

n +1= _n ₊₂=: : := _n = 1

87

and

88

n +1= _n ₊₂=: : := _n= 1 2;

89

(4)

where and are as de…ned in results 2.4 and 2.5.

90

THEOREM 3.1. LetGbe a Strongly Quotient Graph (SQG) with n >3 vertices

91

and maximum edgesm. LetP be de…ned by (1) and =jPj. Then

92

HE(G) +

2 +p

(n ) ; (2)

93

where

94

= X

p-prim e p bⁿ²c

(blogpnc 1) and = 2 X

1 i<j n

1 dij

2

4:

95

PROOF. By Cauchy Schwarz inequality

96

Xn i=1

x_iy_i

!2 Xn i=1

x²_i

! _n X

i=1

y²_i

! :

97

where x1; x2; : : : ; xn andy1; y2; : : : ; yn are real numbers. Settingxi= 1, yi=j ijand

98

replacingnbyn ; we have obtained

99

nX

i=1

j ij

!²

(n )

nX

i=1

j ij²:

100

By results 2.4 and 2.5, we know that 1 and ¹₂ are the H-eigenvalues of SQG with

101

multiplicity greater than or equal to and respectively and considering Lemma 2.1,

102

we have

103

HE(G)

2

(n )

0

@2 X

1 i<j n

1 d_ij

2

4 1 A:

104

or equivalently

105

HE(G) +

2 +p

(n ) ;

106

where

107

= 2 X

1 i<j n

1 dij

2

4:

108

Hence we get the result.

109

THEOREM 3.2. LetGbe a Strongly Quotient Graph (SQG) with n >3 vertices

110

and maximum edgesm. LetP be de…ned by (1) and =jPj. Then

111

HE(G) +

2 +p

+ (n )(n 1)

112

(5)

and

113

HE(G) +

2 +p

(n 1) + (n ) ; (3)

114

where

115

= X

p-prim e p bⁿ²c

(blog_pnc 1); = 2 X

1 i<j n

1 d_ij

2

116 4

and

117

= 2 jdetH(G)j ²⁼ⁿ :

118

PROOF. Setting xi = ²_i and replacing n byn in Lemma 2.3 we obtain

119

that

120

N (n )

nX

i=1 2 i

nX

i=1

j ij

!²

(n 1)N;

121

where

122

N= (n )

2 4 1

n

nX

i=1 2 i

nY

i=1 2 i

!1=n 3 5:

123

By results 2.4 and 2.5, we know that 1 and ¹₂ are the H-eigenvalues of SQG with

124

multiplicity greater than or equal to and respectively. Therefore we have obtained

125

that

126

N (n ) HE(G)

2

(n 1)N;

127

where

128

= 2 X

1 i<j n

1 d_ij

2

4:

129

We observe that

130

N = (n )

2 4 1

n

nX

i=1 2 i

nY

i=1 2 i

!¹⁼ⁿ 3 5

131

= (n ) 2

Yn i=1

j ij

!2=n

132

= (n ) 2 jdetH(G)j ²⁼ⁿ

133

= (n ) ;

134

where = 2 jdetH(G)j ²⁼ⁿ . Hence we get the result.

135

REMARK 3.3. The upper bound (3) is sharper than the upper bound (2). Using

136

Arithmetic–Geometric mean inequality, we have obtained that

137

nX

i=1 2

i (n )

nY

i=1 2 i

!¹⁼ⁿ :

138

(6)

Equivalent to

139

(n )

140

and considering the upper bound (3) we arrive at

141

HE(G) +

2 +p

(n 1) + :

142

Thus we have that

143

HE(G) +

2 +p

(n ) :

144

Which is the upperbound (2). Using Theorem 3.2 and Lemma 2.2, we can give the

145

following corollary.

146

COROLLARY 3.4. LetGbe a Strongly Quotient graph(SQG) with n >3 vertices

147

and maximum edgesm. LetPbe de…ned by (1) and =jPj:Assume that the diameter

148

ofGless than or equal to 2. Then

149

HE(G) +

2 +p

+ (n )(n 1)

150

and

151

HE(G) +

2 +p

(n 1) + (n ) ;

152

where

153

= X

p-prim e p bⁿ²c

log_pn 1 ; =1

4[6m+n(n 1) 4 ]

154

and = 2 jdetH(G)j ²⁼ⁿ .

155

4 Bounds on Harary Estrada Index of SQG

156

First we recall that the Harary Estrada index [12] of the graphGis equal to Pn i=1

e ⁱ and

157

letn₊ be the number of positive H-eigenvalues ofG. In this section we have obtained

158

some upper bound, lower bound for Harary Estrada index HE(G) and the relation

159

between the Harary Estrada index and Harary Energy of SQG withn >3;maximum

160

edgesm.

161

THEOREM 4.1. Let G be a Strongly Quotient graph(SQG) with n > 3 vertices

162

and maximum edgesm. LetP be de…ned by (1) and =jPj:Then

163

HEE(G)

e +p

e+ (n )e^{2 +} ⁼²⁽ⁿ ⁾; (4)

164

where

165

= X

p-prim e p bⁿ²c

log_pn 1 :

166

(7)

PROOF. From Lemma 2.1, Results 2.4 and 2.5, we have

n P

i=1 i= +₂. Using

167

Arithmetic -Geometric Mean Inequality, we get

168

HEE(G) =

nX

i=1

e ⁱ+ e ¹+ e ¹²

169

e ¹+ e ¹² + (n )

nY

i=1

e ⁱ

!¹⁼ⁿ

170

= e +p

e+ (n )

0

@e

nP

i=1 i

1 A

1=n

171

= e +pe+ (n ) e ⁺² ¹⁼ⁿ

172

= e +p

e+ (n )e^{2 +} ⁼²⁽ⁿ ⁾:

173

This completes the proof.

174

THEOREM 4.2. LetP be de…ned by (1) and jPj= :The Harary Estrada index

175

HEE(G)and the Harary energyHE(G)of SQGGwithn >3vertices and maximum

176

edgesmsatisfy the following inequalities

177

HEE(G)

e +pe+(e 1)HE(G)

2 +n n₊

2 (5)

178

and

179

HEE(G)

e +p

e +n 1 +e^HE(G)=2; (6)

180

where = P

p-prim e p bⁿ²c

log_pn 1 .

181

PROOF.Lower bound: Using inequalitiese^x xeande^x 1 +x;we can obtain

182

that

183

HEE(G) =

nX

i=1

e ⁱ+ e ¹+ e ¹²

184

= e ¹+ e ¹² +X

i>0

e ⁱ+ X

i 0

e ⁱ

185

e +p

e+eX

i>0 i+

nX

i=1

i 0

(1 + _i)

186

= e +p

e+eHE(G)

2 +n n++ +

2

HE(G)

187 2

(8)

= e +p

e+(e 1)HE(G)

2 +n n₊

2:

188

Upper bound: Considering f(x) = e^x which is monotonically increases in the

189

interval( 1;1), we obtain

190

HEE(G) =

nX

i=1

e ⁱ+ e ¹+ e ¹²

191

= e ¹+ e ¹² + X

i<0

e ⁱ+X

i 0

e ⁱ

192

e +pe+n n++

n+

X

i=1

e ⁱ

193

= e +p

e+n n₊+

n+

X

i=1

X

k 0 ki

194 k!

= e +p

e+n +X

k 1

1 k!

n+

X

i=1 i

!k

195

= e +p

e+n +X

k 1

(HE(G)=2)^k

196 k!

= e +p

e+n 1 +e^HE(G)=2: (7)

197

This completes the proof.

198

We conclude that the upper bound (5) is better than the upper bound (4) for Harary

199

estrada index of SQG with n >3vertices and maximum edgesm.

200

THEOREM 4.3. Let P be de…ned by (1) and jPj= :The Harary Estrada index

201

and Harary energy of SQG with n > 3 vertices and maximum edges m satisfy the

202

following inequality

203

HEE(G) HE(G)<

e +p

e+n 1 p +e^p ; (8)

204

where

205

= 2 X

1 i<j n

1 dij

2

4 and = X

p-prim e p bⁿ²c

log_pn 1 :

206

PROOF. By results 2.4 and 2.5, we know that 1 and ¹₂ are the H-eigenvalues

207

of SQG with multiplicity greater than or equal to and respectively. From Lemma

208

2.1, Results 2.4 and 2.5, we have Pn i=n++1

2i + ₄. From (6),

209

HEE(G)

e +pe+n +

n+

X

i=1

X

k 1 ki

210 k!

(9)

= e +p

e+n +

n+

X

i=1

i+X

k 2

1 k!

n+

X

i=1 2 i

!k=2

211

< e +p

e+n +HE(G) +X

k 2

1 k!

2 42X

i<j

1 d²_ij

Xn i=n++1

2i

3 5

k=2

212

and

213

HEE(G) HE(G) <

e +p

e+n +X

k 2

1 k!

2 42X

i<j

1

d²_ij 4 3 5

k=2

214

= e +p

e+n 1 p +e^p ;

215

where = 2 P

1 i<j n 1 dij

2

4: This completes the proof.

216

From Theorem 4.3 and Lemma 2.2 we can give the following result.

217

COROLLARY 4.4. Let P be de…ned by (1) and jPj = : The Harary Estrada

218

index and Harary energy of SQG with n >3 vertices, maximum edgesm and let the

219

diameter of Gless than or equal to 2satisfy the following inequality

220

HEE(G) HE(G)<

e +p

e+n 1 p

+e^p ;

221

where

222

=1

4[6m+n(n 1) 4 ] and = X

p-prim e p bⁿ²c

log_pn 1 :

223

REMARK 4.5. [12] LetGbe a connected(n; m)-graph with diameter less than or

224

equal to2. Then

225

HEE(G) HE(G) n 1

r3m

2 +n(n 1) 4 +e

q

3m

2 +ⁿ⁽ⁿ₄¹⁾: (9)

226

Since the functionsf(t) =e^t and f(t) = e^t t are monotonically increase in the

227

intervals ( 1;1) and (0;1) respectively, we conclude that the upper bound (8) is

228

better than the upperbound (9) for SQG withn >3vertices and maximum edgesm.

229

Acknowledgement. The authors are thankful to the reviewers for their valuable

230

comments and kind suggestions.

231

References

232

[1] C. Adiga and R. K. Zaferani, On coloring of strongly multiplicative and strongly

233

quotient graphs, Adv. Stud. Contemp. Math., 13(2006), 171–182.

234

(10)

[2] C. Adiga, R. K. Zaferani and M. Smitha, Strongly quotient graphs, South East

235

Asian J. Math. and Math. Sc., 15(2007), 119–127.

236

[3] C. Adiga and R. K. Zaferani, Upper bounds for energy of a graph, Adv. Stud.

237

Cont. Math., 16(2008), 279–285.

238

[4] F. Buckley and F. Harary, Distance in graphs. Addison-Wesley Publishing Com-

239

pany, Advanced Book Program, Redwood City, CA, 1990. xiv+335 pp.

240

[5] S. B. Bozkurt, C.Adiga and D. Bozkurt, On the energy and estrada index of

241

strongly quotient graphs, Indian J. Pure and Appl. Math., 43(2012), 25–36.

242

[6] S. B. Bozkurt, C.Adiga and D. Bozkurt, Bounds on the Distance Energy and the

243

Distance Estrada Index of Strongly Quotient Graphs,Journal of Applied Mathe-

244

matics,2013, Article ID 681019, 6 pages, http://dx.doi.org/10.1155/2013/681019.

245

[7] D. Cvetkovic, M. Doob, and H. Sachs, Spectra of Graphs: Theory and Application,

246

Spectra of graphs. Theory and applications. Third edition. Johann Ambrosius

247

Barth, Heidelberg, 1995.

248

[8] K. C. Das, Maximum eigenvalue of the reciprocal distance matrix, J. Math. Chem.,

249

47(2010), 21–28.

250

[9] J. A. De la Pena, I. Gutman and J. Rada, Estimating the Estada index, Linear

251

Algebra Appl., 427(2007), 70–76.

252

[10] J. A. Gallian, A dynamic survey of graph labeling, Electron. J. Combin., 5(1998),

253

Dynamic Survey 6, 43 pp.

254

[11] A. D. Gungor and S. B. Bozkurt, On the distance Estrada index of graphs, Hacet.

255

J. Math. Stat., 38(2009), 277–283.

256

[12] A. D. Gungor and A. S Cevik, On the Harary energy and Harary Estrada index

257

of a graph, MATCH Commun. Math. Comput. Chem., 64(2010), 281–296.

258

[13] D. Janeµziµc, A. Miliµcević, S. Nikolić, and N. Trinajstić, Graph-theoretical matrices

259

in chemistry, Mathematical Chemistry Monographs, 3. University of Kragujevac,

260

Faculty of Science, Kragujevac, 2007.

261

[14] R. K. Zaferani, A note on strongly quotient graphs, Bull. Iranian Math. Soc.,

262

34(2008), 97–114,

263

[15] B. Zhou and N. Trinajstic, Maximum eigenvalues of the reciprocal distance matrix

264

and the reverse Wiener matrix, Int. J. Quant. Chem., 108(2008), 858–864.

265

[16] B. Zhou, I. Gutman and T. Aleksic, A note on Laplacian energy of graphs, MATCH

266

Commun. Math. Comput. Chem., 60(2008), 441–446.

267