PUBLICATIONS DE L’INSTITUT MATHÉMATIQUE Nouvelle série, tome 83(97) (2008), 1–7 DOI: 10.2298/PIM0897001G

LOWER BOUNDS FOR ESTRADA INDEX

Ivan Gutman

Communicated by Slobodan Simić

Abstract. If G is an (n, m)-graph whose spectrum consists of the numbers λ_{1}, λ_{2}, …, λ_{n}, then its Estrada index is EE(G) = ∑_{i=1}^{n} e^{λ_{i}}. We establish lower bounds for EE(G) in terms of n and m.

Introduction

In this paper we are concerned with simple graphs, that have no loops and no multiple or directed edges. Let G be such a graph, and let n and m be the number of its vertices and edges. Then we say that G is an (n, m)-graph.

The spectrum of G is the spectrum of its adjacency matrix [1], and consists of the (real) numbers λ_{1}, λ_{2}, …, λ_{n}. The number n_{0} of zeros in the spectrum of the graph G is called its nullity.

A recently introduced [3, 5] spectrum-based graph invariant is

EE = EE(G) = ∑_{i=1}^{n} e^{λ_{i}}

which we proposed [2] to be called the Estrada index.

The Estrada index has found applications in biochemistry [3, 4, 7] and in the theory of complex networks [5, 6]. In the paper [2] lower and upper bounds for EE were deduced. We now obtain some further lower bounds for this graph-spectral invariant.

The eigenvalues of an (n, m)-graph satisfy the following elementary conditions [1]:

(1)  ∑_{i=1}^{n} λ_{i} = 0

(2)  ∑_{i=1}^{n}(λ_{i})^{2} = 2m.

2000 Mathematics Subject Classification: Primary 05C50, 05C35.

The left-hand sides of equations (1) and (2) are special cases (for k = 0 and k = 1) of the spectral moments M_{k} defined as

(3)  M_{k} = M_{k}(G) = ∑_{i=1}^{n}(λ_{i})^{k}.

As usual, the complete graph on n vertices will be denoted by K_{n}. Its complement, \overline{K}_{n} is the n-vertex graph without edges. Its spectrum consists solely of zeros, and therefore EE(\overline{K}_{n}) = n. In what follows we assume that the graphs considered contain at least one edge (m > 0). Such graphs have at least one positive and at least one negative eigenvalue [1].

At this point we remind the reader that the hyperbolic cosine and hyperbolic sine are defined as

cosh(x) = \frac{e^{x} + e^{−x}}{2}  and  sinh(x) = \frac{e^{x} − e^{−x}}{2}

respectively.

An auxiliary inequality

Define two auxiliary quantities EE^{−} and ee as

EE^{−} = EE^{−}(G) = ∑_{i=1}^{n} e^{−λ_{i}}

(4)  ee = ee(G) = ∑_{i=1}^{n} cosh(λ_{i}).

In view of the power-series expansion of e^{x} and e^{−x}, and bearing in mind the definition (3) of spectral moments, we have

EE = ∑_{k⩾0} \frac{M_{k}}{k!}  and  EE^{−} = ∑_{k⩾0}(−1)^{k} \frac{M_{k}}{k!}

from which

EE − EE^{−} = 2 ∑_{k⩾0} \frac{M_{2k+1}}{(2k + 1)!}.

It is known [1] that M_{k} is equal to the number of self-returning walks of length k. Consequently, M_{k} ⩾ 0 for all graphs and for all k ⩾ 0. If the graph G is bipartite, then it contains no odd-membered cycles and, consequently, it has no self-returning walks of odd length, i.e., M_{k}(G) = 0 for k = 1, 3, 5, 7, . . .. In view of this, we conclude that

(5)  EE(G) − EE^{−}(G) ⩾ 0

and that equality holds if and only if G is bipartite. From (5) follows that

EE(G) ⩾ \frac{1}{2} [EE(G) + EE^{−}(G)]

i.e.,

(6)  EE(G) ⩾ ee(G).

Equality in (6) holds if and only if the graph G is bipartite.

In what follows we obtain several lower bounds for ee. Because of (6) these will also be lower bounds for EE.

An (n, m)-type lower bound

A vertex of a graph, having degree zero is said to be isolated.

Theorem 1. If G is an (n, m)-graph without isolated vertices, then

(7)  EE(G) ⩾ n cosh (\sqrt{\frac{2m}{n}}) .

Equality holds if and only if G is regular of degree 1.

Proof. Because of (6), in order to obtain the inequality (7) it is sufficient to demonstrate the validity of

(8)  ee(G) ⩾ n cosh (\sqrt{\frac{2m}{n}}) .

First of all, note that 2m/n is the average vertex degree of the respective graph G. Therefore, if G has no isolated vertices, then 2m/n ⩾ 1.

We now use a Lagrange-multiplier technique to arrive at an extremal value of ee(G). That this is a minimum will be verified at a later moment.

Consider thus the expression

(9)  F = ee −\frac{1}{2}α (∑_{i=1}^{m}(λ_{i})^{2} − 2m)

by means of which we seek for an extremal value of ee under the condition that relation (2) is obeyed. The equations that need to be satisfied are:

\frac{∂F}{∂λ_{k}} = 0 for k = 1, 2, …, n

i.e.,

sinh(λ_{k}) − αλ_{k} = 0 for k = 1, 2, …, n.

It is easy to see that if α > 1, then the equation

(10)  sinh(x) − αx = 0

has three solutions: x_{0} > 0, 0, and −x_{0}. Thus, in order to obtain an extremal value ee^{∗} of ee we have to substitute into the right-hand side of (4) the numbers x_{0}, 0, and −x_{0} instead of the eigenvalues λ_{i}. Let the number of eigenvalues that are replaced by 0 be p. Then the remaining n − p eigenvalues are replaced by x_{0} and/or −x_{0}, resulting in

ee^{∗} = p + (n − p) cosh(x_{0}).

In order that relation (2) be obeyed, it must be (n − p)(x_{0})^{2} = 2m, from which x_{0} = \sqrt{2m/(n − p)} and

(11)  ee^{∗} = p + (n − p) cosh (\sqrt{\frac{2m}{n − p}}) .

Because 2m/n ⩾ 1, for any value of p it will be x_{0} ⩾ 1 and therefore cosh(x_{0}) ⩾ cosh(1) = 1.543080 . . .. Thus the right-hand side of (11) may be viewed as consisting of p summands equal to 1, and n − p summands greater than 1.54. Evidently, this expression will attain its greatest possible value for p = 0.

Therefore, if ee^{∗} is a lower bound for ee (which still needs to be verified), then the best such lower bound is for p = 0, which is just the right-hand side expression in (7).

What remains to be proven is that the Lagrange multiplier α is indeed greater than unity, and that ee^{∗} for p = 0 is a minimum.

From (10) we obtain that

α = \frac{sinh(x_{0})}{x_{0}}.

and we recall that x_{0} ⩾ 1. Because

(\frac{sinh(x)}{x})′ = \frac{(x − 1)e^{x} + (x + 1)e^{−x}}{2x}

it is evident that for x ⩾ 1 the function sinh(x)/x is monotonically increasing. Since for x = 1, sinh(x)/x = 1.175201 …, it must be α > 1.

In order to show that the right-hand side of Eq. (8) is a minimum, we have to examine the Hessian matrix of the function F, Eq. (9). Direct calculation yields:

\frac{∂^{2}F}{∂λ_{k}^{2}} = cosh(λ_{k}) − α
\frac{∂^{2}F}{∂λ_{k}∂λ_{k′}} = 0  for k ≠ k′.

Thus, the Hessian matrix is diagonal and all its diagonal elements are equal to

cosh(λ_{k}) − α = cosh(x_{0}) − \frac{sinh(x_{0})}{x_{0}} = \frac{(x_{0} − 1)e^{x_{0}} + (x_{0} + 1)e^{−x_{0}}}{2x_{0}}

which for x_{0} ⩾ 1 is evidently positive-valued. Therefore ee^{∗} is a minimum, and inequality (8) is obeyed. Then also inequality (7) holds.

Equality in (7) will be attained if the underlying graph is bipartite and if all its eigenvalues are equal by absolute value. This latter condition is satisfied only the regular graph of degree one, i. e., by the graph consisting of n/2 copies of K_{2}. For this graph 2m/n = 1 and therefore EE = n cosh(1).

This completes the proof of Theorem 1. □

Remark 2. It is interesting to note that in the proof of Theorem 1, the condition (1) has not been taken into account. Taking into account condition (1), or any other condition that the graph eigenvalues satisfy, was possible, but not necessary.

It was our (successful) choice to pursue a Lagrange-multiplier approach based solely on condition (2). If condition (1) would be included into the test-function (9), a better bound for EE could be expected, but then a much more complicated situation would occur: the equation analogous to (10) would have either two positive and one negative solution, or one positive and two negative solutions. Finding the respective expression for ee^{∗} would become a difficult and infeasible task.

Theorem 1 can be somewhat strengthened. Namely, in its proof not the absence of isolated vertices, but the condition 2m/n ⩾ 1 was used. In view of this we have:

Theorem 3. If G is an (n, m)-graph for which 2m/n ⩾ 1, then

EE(G) ⩾ n cosh (\sqrt{\frac{2m}{n}}) .

Equality holds if and only if G is regular of degree 1.

If the number of isolated vertices in the (n, m)-graph G is known, and is, say, equal to q, then G = G^{∗} ∪ \overline{K_{q}}, where G^{∗} is an (n − q, m)-graph to which Theorem 1 is applicable. Because EE(G) = q + EE(G^{∗}), we immediately arrive at:

Corollary 4. If G is an (n, m)-graph with exactly q isolated vertices (q < n), then

EE(G) ⩾ q + (n − q) cosh (\sqrt{\frac{2m}{n − q}} ) .

Equality holds if and only if G consists of a regular graph of degree 1 and q isolated vertices.

The case 2m/n < 1

If the average vertex degree 2m/n is less than unity, then the graph G necessarily possesses isolated vertices. If the number of isolated vertices is known, then Corollary 3 is applicable. Otherwise we may proceed as follows.

If 2m/n < 1, then the number of isolated vertices in G is at least n − 2m, so that G can be written as G = G^{†} ∪ \overline{K}_{n−2m}. The graph G^{†} may still possess isolated vertices. However, G^{†} possesses exactly 2m vertices, and therefore its average vertex degree is unity. Consequently, by Theorem 2,

EE(G^{†}) ⩾ 2m cosh(1)

and we arrive at:

Theorem 5. If G is an (n, m)-graph for which 2m/n < 1, then

EE(G) ⩾ n − 2m + 2m cosh(1).

Equality is attained if and only if G consists of n − 2m isolated vertices and a regular graph of degree 1 on 2m vertices.

An (n, m, n_{0})-type lower bound

Suppose that in addition to the parameters n and m we know also the nullity n_{0} of the graph G. If n_{0} = 0, then G does not possess isolated vertices, and Theorem 1 is applicable. We therefore assume that n_{0} > 0. Then we have:

Theorem 6. If G is an (n, m)-graph with at least one edge and nullity n_{0} > 0, then

(12)  EE(G) ⩾ n_{0} + (n − n_{0}) cosh (\sqrt{\frac{2m}{n − n_{0}}} ) .

Equality holds if and only if G consists either of isolated vertices and copies of K_{2}, or of isolated vertices and copies of various complete bipartite graphs K_{a,b}, such that the product a · b is constant.

Remark 7. An example of a graph for which equality in (12) holds is the graph consisting of a copy of K_{1,12}, two copies of K_{2,6}, three copies of K_{3,4}, and four isolated vertices. Its spectrum consists of the numbers \sqrt{12} (with multiplicity 6), 0 (with multiplicity 42), and −\sqrt{12} (with multiplicity 6). Therefore

EE = 42 + 6e^{\sqrt{12}} + 6^{−\sqrt{12}}

which coincides with the right-hand side of (12) for n = 54, m = 72, and n_{0} = 42.

Proof. The proof of Theorem 5 is analogous to the proof of Theorem 1 and we point out only the main differences. Label the eigenvalues of G so that λ_{i} = 0 for n − n_{0} + 1 ⩽ i ⩽ n. Then

EE(G) ⩽ n_{0} + ee_{0}(G)

and the auxiliary quantity to be minimized is

ee_{0}(G) = ∑_{i=1}^{n−n_{0}} cosh(λ_{i}).

At a pertinent point of the proof one needs to show that for any graph G with at least one edge, 2m/(n − n_{0}) ⩾ 1. To see this, suppose that the graph G has exactly q isolated vertices. Then G = G^{∗} ∪ \overline{K}_{q} and

m(G) = m(G^{∗})
n(G) = n(G^{∗}) + q
n_{0}(G) = n_{0}(G^{∗}) + q.

Bearing in mind that G^{∗} possesses at least one edge and therefore at least one positive eigenvalue, we have

\frac{2m(G)}{n(G) − n_{0}(G)} = \frac{2m(G^{∗})}{n(G^{∗}) − n_{0}(G^{∗})} > \frac{2m(G^{∗})}{n(G^{∗})} ⩾ 1.

The rest of the proof is same as in Theorem 1. □

References

[1] D. Cvetković, M. Doob, H. Sachs, Spectra of Graphs – Theory and Application, third ed., Johann Ambrosius Barth Verlag, Heidelberg, 1995.

[2] J. A. de la Peña, I. Gutman, J. Rada, Estimating the Estrada index, Lin. Algebra Appl. 56 (2008), 507–509.

[3] E. Estrada, Characterization of 3D molecular structure, Chem. Phys. Lett. 319 (2000), 713– 718.

[4] E. Estrada, Characterization of the folding degree of proteins, Bioinformatics 18 (2002), 697– 704.

[5] E. Estrada, J. A. Rodríguez-Velázquez, Subgraph centrality in complex networks, Phys. Rev. E71 (2005), 056103–1–9.

[6] E. Estrada, J. A. Rodríguez-Velázquez, Spectral measures of bipartivity in complex networks, Phys. Rev. E72 (2005), 046105–1–6.

[7] E. Estrada, J. A. Rodríguez-Velázquez, M. Randić, Atomic branching in molecules, Int. J. Quantum Chem. 106 (2006), 823–832.

Faculty of Science (Received 11 01 2007) University of Kragujevac P.O. Box 60 34000 Kragujevac Serbia

    gutman@kg.ac.yu