Appl. Math. J. Chinese Univ. 2010, 25(3): 325-330

Bounds of the Estrada index of graphs

LIU Jian-ping ^l LIU Bo-lian²

Abstract. Let G be a graph of order n and let Al, A2, ... , An be its eigenvalues. The Estrada index[2] of G is defined as EE = EE(G) = E e *i . In this paper, new bounds for EE are established, as well as some relations between EE and graph energy E.

51 Introduction

Let G be an undirected simple graph. Let n and m be the number of vertices and edges of G, respectively. Such a graph will be referred to as an (n, m)-graph.

The eigenvalues of the adjacency matrix A(G) are called the eigenvalues of G and form the spectrum [1] of G. Let the spectrum of G be Al, ... , An. Since A(G) is a real symmetric matrix, its eigenvalues are real numbers. We order the eigenvalues of G as Al 2 . . . gt; The basic properties of graph eigenvalues can be found in [1].

The Estrada index of the graph G is defined by Estrada [2-7] as

EE = EE(G) = (1) i=l

Although invented in the year 2000, the Estrada index has already found numerous applications in Physics, Chemistry and complex networks, for details see [2-7]. For the recent work of the mathematical properties on Estrada index, see [9].

In [9], J. A. de la Pena et al. established some lower and upper bounds for EE in terms of the number of vertices and the number of edges. They give some inequalities between EE and the energy of G. In this paper, we establish some new bounds for EE involving graph energy and several other graph invariants. Most of our bounds improve the results in [9]. Furthermore, we point out that one of the lower bounds in [9] is not correct.

Received: 2009-04-01.

MR Subject Classification: 05C90.

Keywords: Graph spectrum, Estrada index, bound, energy (of graph).

Digital Object Identifier(D01): 10.1007/s11766-010-2237-6.

Supported by the National Natural Science Foundation of China (10771080), by the Fund of Fuzhou University (XRC-0956), and by the Natural Science Foundation of Fujian Province (2010J05005).

(n, m)-Type estimates of the Estrada index

For convenience, we give some notation and properties which will be used in the following proofs of our results.

n

Let Mk = Mk(G) = E be the kth spectral moment of a graph G. Bearing in mind the power-series expansion of e^c , we have

EE(G) = E Mk(G)k! (2)

As is well known [1], Mk(G) is the number of self-returning walks of length k of the graph G.

It is easy to see that any (n, m)-graph G has EE(G) n, and equality holds if and only if m = 0. From now on we assume that all (n, m)-graph considered in this paper are not edgeless, i.e., m # 0. We use ch@) to denote the hyperbolic cosine ch@) 2

Theorem 2.1. Let G be an (n, m)-graph with m 0. Then the Estrada index of G is bounded by

In view of the inequality between the arithmetic and geometric means,

(5)

By means of a power-series expansion, and the first few spectral moments of G, that is, MO = n, Ml = 0, 1112 = 2m, and 113 = 6t, we get

(2Auml;i)k (2Auml;i)k

= n 4m 8t

4

(2Aring;i)k n 4m 8t — 114

4! k!

kgt;5

Since M4 2 2m, equality holds if and only if C = aK2 — a)K1, i.e., the graph consists of a copies of and n — a isolated vertices, where a % is an integer, Noticing that when m 0, Mk 2 0, for k = 5,6..., we get

Combining with (4) and (5), we obtain the lower bound.

Upper bound. Let the number of positive eigenvalues of G be n . Since f (c) — e ^c mono-

(6)

(7)

Since every (n, m)-graph with m 0 has K2 as its induced subgraph, and the spectrum of

—1, it follows from the interlacing inequalities that lt; —1, which implies that (Ai)2 2 1. Consequently,

EE lt; n

Remark 2.1. In [9], it was proved that

(8) Obviously, our bounds in (3) are better than the bounds in (8).

Theorem 2.2. Let G be a bipartite (n, m) -graph with m 0. Then the Estrada indec of G is bounded by

(9)

Proof. Since G is a triangle-free graph, in view of Theorem 2.1 we only have to verify the upper bound. From (7),

, n, we get

Hence,

and equality holds if and only if m 1. Obviously, the bound in (10) is better than the upper bound in (9).

In [9], it was proved that n ² 4m EE(G)

Obviously, our lower bound in (9) is better than that in (11). Although the bound (10) and the upper bound in (9) are not better than the upper bound in (11), they are more simple and direct, and the difference in their values is very small (not exceeding 1).

If G is regular of degree r, then its greatest eigenvalue Al is equal to r. If in addition G is bipartite, then [1] its smallest eigenva]ue is equal to —r. Bearing these facts in mind, we have the results stated in the following two theorems.

Theorem 2.3. Let G be a regular graph of degree r 0 and of order n. Then its Estrada indec is bounded by e ^r (n - l)e ⁿ lt; EE(G)

Proof. The upper bound is obtained by estimating EE — e^r in the same way as in Theorem 2.1. In order to obtain the lower bound we consider EE — e^r By the inequality between the arithmetic and geometric means,

because the sum of the eigenvalues for i = 2, 3, . , n is equal to —r. Equality holds if and only if = ..3 i.e., if and only if r = n — 1.

Remark 2.3. In [9],

剩余内容已隐藏，支付完成后下载完整资料

英语译文共 7 页，剩余内容已隐藏，支付完成后下载完整资料

资料编号：[405946]，资料为PDF文档或Word文档，PDF文档可免费转换为Word