9_xxx_bozkurt.dvi


EUROPEAN JOURNAL OF PURE AND APPLIED MATHEMATICS

Vol. 5, No. 1, 2012, 88-96

ISSN 1307-5543 – www.ejpam.com

SPECIAL ISSUE FOR THE INTERNATIONAL CONFERENCE ON APPLIED ANALYSIS AND ALGEBRA

29 JUNE - 02 JULY 2011, ISTANBUL TURKEY

Randić Energy and Randić Estrada Index of a Graph

Ş. Burcu Bozkurt!, Durmuş Bozkurt

Department of Mathematics, Science Faculty, Selçuk University, 42075, Campus, Konya, Turkey

Abstract. Let G be a simple connected graph with n vertices and let di be the degree of its i-th vertex.
The Randić matrix of G is the square matrix of order n whose

!

i, j
"

-entry is equal to 1/
#

didj if the
i-th and j-th vertex of G are adjacent, and zero otherwise. The Randić eigenvalues are the eigenvalues
of the Randić matrix. The Randić energy is the sum of the absolute values of the Randić eigenvalues.
In this paper, we introduce a new index of the graph G which is called Randić Estrada index. In
addition, we obtain lower and upper bounds for the Randić energy and the Randić Estrada index of G.

2000 Mathematics Subject Classifications: 05C50,15A18

Key Words and Phrases: Randić Matrix, Randić Eigenvalue, Randić Energy, Randić Estrada Index

1. Introduction

Let G be a simple connected graph with n vertices and m edges. Throughout this paper,

such a graph will be refered to as connected (n, m)-graph. Let V (G) =
$

v1, v2, . . . , vn

%

be

the vertex set of G. If any two vetices vi and vj of G are adjacent, then we use the notation
vi " vj . For vi # V (G) , the degree of the vertex vi, denoted by di, is the number of the vertices

adjacent to vi.

Let A(G) be the (0,1)-adjacency matrix of G and !1,!2, . . . ,!n be its eigenvalues. These

are said to be eigenvalues of the graph G and to form its spectrum [3]. The Randić matrix of

G is the n$ n matrix R= R (G) =
&

Ri j

'

as the following

Ri j =

(

1%
di dj

, vi " vj

0, otherwise

!Corresponding author.

Email addresses: (Ş. Bozkurt), (D. Bozkurt)

http://www.ejpam.com 88 c& 2012 EJPAM All rights reserved.



Ş. Bozkurt and D. Bozkurt / Eur. J. Pure Appl. Math, 5 (2012), 88-96 89

The Randić eigenvalues "1,"2, . . . ,"n of the graph G are the eigenvalues of its Randić matrix.

Since A(G) and R (G) are real symmetric matrices, their eigenvalues are real numbers. So we
can order them so that !1 ' !2 ' . . . ' !n and "1 ' "2 ' . . . ' "n.

The energy of the graph G is defined in [11,12,13] as:

E = E (G) =

n
)

i=1

*

*!i

*

* . (1)

The Randić energy of the graph G is defined in [1,2] as:

RE = RE (G) =

n
)

i=1

*

*"i

*

* . (2)

The Estrada index of the graph G is defined in [7,8,9,10] as:

EE = EE (G) =

n
)

i=1

e!i (3)

Denoting by Mk = Mk (G) the k-th moment of the graph G

Mk = Mk (G) =

n
)

i=1

!

!i

"k
.

Recalling the power series expansion of ex , we have

EE =

(
)

k=0

Mk

k!
. (4)

It is well known that [3] Mk is equal to the number of closed walks of length k in the

graph G. Estrada index of graphs has an important role in Chemistry and Physics. For more

information we refer to the reader [7,8,9,10]. In addition, there exist a vast literature that

studies Estrada index and its bounds. For detailed information we may also refer to the reader

[4,5,6,14].
Now we introduce the Randić Estrada index of the graph G.

Definition 1. If G is a connected (n, m)-graph, then the Randíc Estrada index of G, denoted by

REE (G), is equal to

REE = REE (G) =

n
)

i=1

e"i . (5)

where "1,"2, . . . ,"n are the Randíc eigenvalues of G.

Let

Nk = Nk (G) =

n
)

i=1

!

"i

"k
.



Ş. Bozkurt and D. Bozkurt / Eur. J. Pure Appl. Math, 5 (2012), 88-96 90

Recalling the power series expansion of ex we have another expression of Randić Estrada

index as the following

REE (G) =

(
)

k=0

Nk

k!
. (6)

In this paper, we obtain lower and upper bounds for the Randić energy and the Randić

Estrada index of G. Firstly, we give some definitions and lemmas which will be needed then.

Definition 2. [2] Let G be a graph with vertex set V (G) =
$

v1, v2, . . . , vn

%

and Randíc matrix

R. Then the Randíc degree of vi, denoted by Ri is given by

Ri =

n
)

j=1

Ri j.

Definition 3. [2] Let G be a graph with vertex set V (G) =
$

v1, v2, . . . , vn

%

and Randíc matrix

R. Let the Randíc degree sequence be
$

R1,R2, . . . ,Rn

%

. Then for each i = 1,2, . . . , n the sequence

L
(1)
i , L

(2)
i , . . . , L

(p)
i , . . . is defined as follows: Fix # # !, let

L
(1)
i = R#i

and for each p ' 2, let

L
(p)
i =

)

i" j

1
#

didj

L
(p)1)
j .

Definition 4. [15] Let G be a graph with Randíc matrix R . Then the Randíc index of G, denoted

by R (G) is given by

R (G) =
1

2

n
)

i=1

Ri.

Lemma 1. [1] Let G be a graph with n vertices and Randíc matrix R. Then

tr (R) =
n
)

i=1

"i = 0

and

tr
+

R2
,

=

n
)

i=1

"2
i = 2

)

i" j

1

didj

.

Lemma 2. [2] Let G be a connected graph # be a real number and p be an integer. Then

"1 '
-

Sp+1

Sp

.

where Sp =
n
.

i=1

/

L
(p)
i

02
. Moreover, the equality holds for particular values of # and p if and only

if

L
(p+1)
1

L
(p)
1

=
L
(p+1)
2

L
(p)
2

= · · · = L
(p+1)
n

L
(p)
n

.



Ş. Bozkurt and D. Bozkurt / Eur. J. Pure Appl. Math, 5 (2012), 88-96 91

Lemma 3. [2] A simple connected graph G has two distinct Randíc eigenvalues if and only if G

is complete.

2. Bounds for the Randić Energy of a Graph

In this section, we obtain lower and upper bounds for the Randić energy of connected

(n, m)-graph G.

Let N and M be two positive integers. We first consider the following auxiliary quantity Q

as

Q = Q (G) =

N
)

i=1

qi (7)

where qi, i = 1,2, . . . , N are some numbers which some how can be computed from the graph

G. For which we only need to know that they satisfy the conditions

qi ' 0, for all i = 1,2, . . . , N

and
N
)

i=1

!

qi

"2
= 2M (8)

or, the conditions (7), (8) and

P = P (G) =

N
1

i=1

qi (9)

if all the conditions (7)-(9) are taken into account then [11]

#

2MN ) (N ) 1)D * Q *
#

2MN ) D (10)

where

D = 2M ) N P2/N . (11)

For the graph energy (namely by setting into (10) and (11) N = n, M = m and P = |det A|),
this yields [11]

2

2m+ n (n) 1) |det A|2/n * E (G)*
2

2m (n) 1) + n |det A|2/n.

The Randić energy-counterpart of the estimates (10) and (11) is obtained as the following

result.

Theorem 1. Let G be a connected (n, m)-graph and ! be the absolute value of the determinant

of the Randíc matrix R. Then

RE (G)'
3

2
)

i" j

1

didj

+ n (n) 1)!2/n (12)



Ş. Bozkurt and D. Bozkurt / Eur. J. Pure Appl. Math, 5 (2012), 88-96 92

and

RE (G)*
3

2 (n) 1)
)

i" j

1

didj

+ n!2/n. (13)

Proof. The result is easily obtained using the estimates (10), (11) and Lemma 1.

In [1] the following result for RE (G) was obtained

RE (G)*
3

2n
)

i" j

1

didj

(14)

Remark 1. The upper bound (13) is sharper than the upper bound (14). Using arithmetic-

geometric mean inequality, we obtain

2
)

i" j

1

didj

' n!2/n

and considering the upper bound (13) we arrive at

RE (G)*
3

2n
)

i" j

1

didj

which is the upper bound (14).

3. Bounds for the Randić Estrada Index of a Graph

In this section, we consider the Randić Estrada index of connected (n, m)-graph G. We
also adapt the some results in [4] and [14] on the Randić Estrada index to give lower and

upper bounds for it.

Theorem 2. Let G be a connected (n, m)-graph. Then

REE(G)' e

4

Sp+1

Sp +
n) 1

e
1

n)1

4

Sp+1

Sp

. (15)

where # is a real number, p is an integer and Sp =
n
.

i=1

/

L
(p)
i

02
. Moreover, the equality holds in

(15) if and only if G is the complete graph Kn.

Proof. Starting with the equation (5) and using arithmetic-geometric mean inequality, we

obtain

REE(G) = e"1 + e"2 + · · ·+ e"n



Ş. Bozkurt and D. Bozkurt / Eur. J. Pure Appl. Math, 5 (2012), 88-96 93

' e"1 + (n) 1)

5

n
1

i=2

e"i

6
1

n)1

(16)

= e"1 + (n) 1)
+

e)"1
,

1
n)1 , since

n
)

i=1

"i = 0. (17)

Now we consider the following function

f (x) = ex +
n) 1

e
x

n)1

for x > 0. We have

f (x) = ex ) e)
x

n)1 > 0

for x > 0. It is easy to see that f is an increasing function for x > 0. From the equation (17)

and Lemma 2, we obtain

REE(G)' e

4

Sp+1

Sp +
n) 1

e
1

n)1

7

Sp+1

Sp

. (18)

Now we assume that the equality holds in (15). Then all inequalities in the above argument

must be equalities. From (18) we have

"1 =

-

Sp+1

Sp

which implies
L
(p+1)
1

L
(p)
1

=
L
(p+1)
2

L
(p)
2

= · · · = L
(p+1)
n

L
(p)
n

. From (16) and arithmetic-geometric mean in-

equality we get "2 = "3 = · · ·= "n. Therefore G has exactly two distinct Randić eigenvalues,

by Lemma 3, G is the complete graph Kn.

Conversely, one can easily see that the equality holds in (15) for the complete graph Kn.

This completes the proof of theorem.

Now we give a result which states a lower bound for the Randić Estrada index involving

Randić index.

Corollary 1. Let G be a connected (n, m)-graph. Then

REE(G)' e
2R(G)

n +
n) 1

e
2R(G)

n(n)1)

(19)

where R (G) denotes the Randíc index of the graph G. Moreover the equality holds in (19) if and

only if G is the complete graph Kn.

Proof. In [2], the authors showed that the folllowing inequality (see Theorem 4)

"1 '
-

Sp+1

Sp

'

8

9

9

:

n
.

i=1

R2
i

n
' 2R (G)

n
(20)



Ş. Bozkurt and D. Bozkurt / Eur. J. Pure Appl. Math, 5 (2012), 88-96 94

where Sp=
n
.

i=1

/

L
(p)
i

02
. Combining Theorem 2 and (20) we get the inequality (19).

Also, the equality holds in (19) if and only if G is the complete graph Kn.

Theorem 3. Let G be a connected (n, m)-graph.Then the Randíc Estrada index REE (G) and the

Randíc energy RE (G) satisfy the following inequality

1

2
RE (G) (e) 1)+ n) n+ * REE (G)* n) 1+ e

RE(G)

2 . (21)

where n+ denotes the number of positive Randíc eigenvalues of G. Moreover, the equality holds

on both sides of (21) if and only if G = K1.

Proof. Lower bound: Since ex ' ex , equality holds if and only if x = 1 and ex ' 1+ x ,

equality holds if and only if x = 0, we get

REE (G) =

n
)

i=1

e"i =
)

"i>0

e"i +
)

"i*0

e"i

'
)

"i>0

e"i +
)

"i*0

!

1+"i

"

= e
+

"1+"2 + · · ·+"n+

,

+
!

n) n+
"

+
+

"n++1 + · · ·+"n

,

= (e) 1)
+

"1 +"2+ · · ·+"n+

,

+
!

n) n+
"

+

n
)

i=1

"i

=
1

2
RE (G) (e) 1) + n) n+.

Upper bound: Since f (x) = ex monotonically increases in the interval ()(,+(), we get

REE (G) =

n
)

i=1

e"i * n) n+ +

n+
)

i=1

e"i

Therefore

REE (G) = n) n+ +

n+
)

i=1

)

k'0

!

"i

"k

k!

= n+
)

k'1

1

k!

n+
)

i=1

!

"i

"k

* n+
)

k'1

1

k!

;

<

n+
)

i=1

"i

=

>

k

= n) 1+ e
RE(G)

2 .

It is easy to see that the equality holds on both sides of (21) if and only if RE (G) = 0. Since G

is a connected graph this only happens in the case of G = K1.



REFERENCES 95

4. Concluding Remarks

In this paper, the Randić Estrada index of a graph is introduced. Also the Randić energy

and the Randić Estrada index are studied. In section 2, a sharper upper bound and a new

lower bound for the Randić energy are obtained. In section 3, some bounds for the Randić

Estrada index involving Randić index, Randić energy and some other graph invariants are also

put forward.

ACKNOWLEDGEMENTS: The authors thank the referees for their helpful suggestions con-

cerning the presentation of this paper.

References

[1] Ş Bozkurt, A Güngör, I Gutman and A Çevik. Randić Matrix and Randić Energy. MATCH

Commun. Math. Comput. Chem. 64. 239-250. 2010.

[2] Ş Bozkurt, A Güngör, and I Gutman. Randić Spectral Radius and Randić Energy. MATCH

Commun. Math. Comput. Chem. 64. 321-334. 2010.

[3] D Cvetković, M Doob and H Sachs. Spectra of Graphs-Theory and Application (Third ed.

Johann Ambrosius Bart Verlag, Heidelberg, Leipzig). 1995.

[4] K Das and S Lee. On the Estrada index conjecture. Linear Algebra Appl. 431. 1351-1359.
2009.

[5] J De la Peña, I Gutman and J Rada. Estimating the Estrada index. Linear Algebra Appl.

427. 70-76. 2007.

[6] H Deng, S Radenković and I Gutman. The Estrada index in: D. Cvetkovic, I. Gutman

(Eds.) Applications of Graph Spectra (Math. Inst., Belgrade). 123-140. 2009.

[7] E Estrada. Characterization of 3D molecular structure. Chem. Phys. Lett. 319. 713-718.

2000.

[8] E Estrada. Characterization of the folding degree of proteins. Bioinformatics 18. 697-

704. 2002.

[9] E Estrada and J Rodríguez-Velázguez. Subgraph centrality in complex networks. Phys.

Rev. E 71. 056103-056103-9. 2005.

[10] E Estrada, J Rodríguez-Velázguez adn M Randić. Atomic Branching in molecules. Int.

J.Quantum Chem. 106. 823-832. 2006.

[11] I Gutman. Bounds for total $-electron energy. Chem. Phys. Lett. 24. 283-285. 1974.

[12] I Gutman. Total $-electron energy of benezoid hydrocarbons. Topics Curr. Chem. 162.

26-63. 1992.



REFERENCES 96

[13] I Gutman. The energy of a graph, old and new results, in: A. Betten, A. Kohnert,

R. Laue, A. Wassermann (Eds.), Algebraic Combinatorics and Applications (Springer-

Verlag, Berlin) 196-211. 2001.

[14] J Liu and B Liu. Bounds of the Estrada index of graphs. Appl. Math. J. Chinese Univ. 25

(3). 325-330. 2010.

[15] M Randić. On characterization of moleculer branching, J. A. Chem. Soc. 97. 6609-6615.

1975.