A Note on the Estrada Index of the A_α-Matrix

Abstract

Let G be a graph on n vertices. The Estrada index of G is an invariant that is calculated from the eigenvalues of the adjacency matrix of a graph. V. Nikiforov studied hybrids of $A\left(G\right)$ and $D\left(G\right)$ and defined the $A_{\alpha }$-matrix for every real $\alpha \in [0,1]$ as: $A_{\alpha }\left(G\right)=\alpha D\left(G\right)+(1-\alpha )A\left(G\right).$ In this paper, using a different demonstration technique, we present a way to compare the Estrada index of the $A_{\alpha }$-matrix with the Estrada index of the adjacency matrix of the graph G. Furthermore, lower bounds for the Estrada index are established.

1. Introduction

Throughout the paper, we consider G an arbitrary connected graph with the edge set denoted by $\mathcal{E}\left(G\right)$ and its vertex set $V\left(G\right)=\{1,\dots ,n\}$ with cardinality m and n (order of G), respectively. We say that G is an $(n,m)$-graph. If $e\in \mathcal{E}\left(G\right)$ has end vertices i and j, then we say that i and j are adjacent, and this edge is denoted by $ij$. For a finite set U, $\left|U\right|$ denotes its cardinality. Let $K_n$ be the complete graph with n vertices and $\overline{K_n}$ its complement.

The adjacency matrix $A\left(G\right)$ of the graph G is a symmetric matrix of order n with entries $a_{ij}$, such that $a_{ij}=1$ if $ij\in \mathcal{E}\left(G\right)$ and $a_{ij}=0$ otherwise. Denote by ${\lambda }_1\ge \dots \ge {\lambda }_n$ the eigenvalues of $A\left(G\right)$; see [1,2].

The matrix $L\left(G\right)=D\left(G\right)-A\left(G\right)$ is called the Laplacian matrix of G (see [3]), where $D\left(G\right)$ is the diagonal matrix of vertex degrees of G. We denote the eigenvalues of the Laplacian matrix by ${\mu }_1\ge {\mu }_2\ge \dots \ge {\mu }_{n-1}\ge {\mu }_n=0.$ A matrix is singular if it has zero as an eigenvalue; otherwise, it is called non-singular. A graph G is said to be non-singular if its adjacency matrix is non-singular.

The Estrada index of the graph G is defined as:

$$EE\left(G\right)=\sum _{i=1}^n{e}^{{\lambda }_i}.$$

This spectral quantity was put forward by E. Estrada [4] in the year 2000. Many chemical and physical applications have been found, including quantifying the degree of folding of long-chain proteins [5,6,7] and complex networks [8,9,10,11]. The mathematical properties of this invariant can be found in, e.g., [12,13,14,15,16].

De la Peña et al. in [17], with respect to Estrada index, showed the following.

Theorem 1

([17]). Let G be an $(n,m)$-graph. Then, the Estrada index of G is bounded as:

$$\sqrt{n^2+4m}\le EE\left(G\right)\le n-1+e^{\sqrt{2m}}.$$

(1)

Equality on both sides of (1) is attained if and only if G is isomorphic to $\overline{K_n}$.

In [18], Bamdad proved the following result.

Theorem 2

([18]). Let G be an $(n,m)$-graph with t triangles. Then:

$$EE\left(G\right)\ge \sqrt{n^2+2mn+2nt}.$$

(2)

Equality holds if and only if G is the empty graph $\overline{Kn}.$

Denote by $M_k=M_k\left(G\right)$ the k-th spectral moment of the graph G, i.e.,

$${\displaystyle M_k=\sum _{i=1}^n{\left({\lambda }_i\right)}^k,}$$

then, we can write the Estrada index as:

$$EE\left(G\right)=\sum _{k=0}^{\infty }\frac{M_k}{k!}.$$

(3)

In [1], for an $(n,m)$-graph G, the authors proved that:

$$M_0=n,M_1=0,M_2=2m,M_3=6t,$$

(4)

where t is the number of triangles in G.

Remark 1.

Notice that we can obtain a lower bound for the Estrada index considering (3) and (4) by:

$$\begin{array}{ccc}\hfill EE\left(G\right)& =& \sum _{k=0}^{\infty }\frac{M_k}{k!}\hfill \\ & =& M_0+M_1+\frac{M_2}{2!}+\frac{M_3}{3!}+\sum _{k=4}^{\infty }\frac{M_k}{k!}\hfill \\ & \ge & M_0+M_1+\frac{M_2}{2!}+\frac{M_3}{3!}\hfill \\ & =& n+m+t.\hfill \end{array}$$

Therefore, we demonstrate the following result.

Theorem 3.

Let G be an $(n,m)$-graph with t-triangles. Then:

$$EE\left(G\right)\ge n+m+t.$$

Equality holds if and only and G is isomorphic to $\overline{K_n}$.

Remark 2.

Here, we show that the bound in Theorem 3 improves the bounds in Theorems 1 and 2. Suffice it to show that:

$$\begin{array}{ccc}\hfill \sqrt{n^2+4m}\le n+m+t& \Rightarrow & 4m\le m^2+t^2+2(nm+nt+mt).\hfill \end{array}$$

and:

$$\begin{array}{ccc}\hfill \sqrt{n^2+2nm+2nt}\le n+m+t& \Rightarrow & 0\le m^2+t^2+2mn.\hfill \end{array}$$

In [19], V. Nikiforov studied hybrids of $A\left(G\right)$ and $D\left(G\right)$ and defined the $A_{\alpha }$-matrix for every real $\alpha \in \left[0,1\right]$ as:

$$A_{\alpha }\left(G\right)=\alpha D\left(G\right)+\left(1-\alpha \right)A\left(G\right),$$

with ${\rho }_1,{\rho }_2,\dots ,{\rho }_n$ the eigenvalues of $A_{\alpha }$.

The Estrada index of the $A_{\alpha }$-matrix of graph G is defined as

$$E{E}_{\alpha }\left(G\right)=\sum _{i=1}^n{e}^{{\rho }_i}.$$

Note that the $A_{\alpha }$-matrix can be written as follows:

$$A_{\alpha }\left(G\right)=\alpha \left(L\left(G\right)\right)+A\left(G\right).$$

(5)

Given a matrix $M,$ we denote by ${\partial }_i\left(M\right)$ the i-th eigenvalue in descending order of matrix M. The following result, due to Weyl, can be found in [20].

Theorem 4

([20]). Let A and B be two Hermitian matrices of order n, and let $1\le i,j\le n$. If $C=A+B$ is a matrix, then,

 (i)

${\partial }_i\left(A\right)+{\partial }_j\left(B\right)\le {\partial }_{i+j-n}\left(C\right)$, if $i+j\ge n+1$;

 (ii)

${\partial }_i\left(A\right)+{\partial }_j\left(B\right)\ge {\partial }_{i+j-1}\left(C\right)$, if $i+j\le n+1$.

Equality holds if and only if there exists a unit vector that is an eigenvector of each of the three eigenvalues involved.

Notice that if $j=n$ and $j=1$ in Weyl’s inequality; we can write:

$${\partial }_i\left(A\right)+{\partial }_n\left(B\right)\le {\partial }_i(A+B)\le {\partial }_i\left(A\right)+{\partial }_1\left(B\right).$$

(6)

Applying the inequality (6) to the matrix in (5), i.e., considering $A=A\left(G\right)$ and $B=\alpha L\left(G\right),$ we have the following inequalities.

$${\partial }_i\left(A\left(G\right)\right)+\alpha {\partial }_n\left(L\left(G\right)\right)\le {\partial }_i\left(A_{\alpha }\left(G\right)\right)\le {\partial }_i\left(A\left(G\right)\right)+\alpha {\partial }_1\left(L\left(G\right)\right).$$

(7)

In 1985, Anderson et al. [3] obtained the following upper bound for the Laplacian matrix.

Lemma 1.

[3] If G is a graph of order n, then:

$${\mu }_1\left(L\left(G\right)\right)\le n.$$

(8)

Equality holds if and only if $\overline{G}$ is disconnected.

Considering the above Lemma 1, the inequality (7), and ${\partial }_n\left(L\left(G\right)\right)={\mu }_n=0$, we have:

$${\partial }_i\left(A\left(G\right)\right)\le {\partial }_i\left(A_{\alpha }\left(G\right)\right)\le {\partial }_i\left(A\left(G\right)\right)+n\alpha .$$

(9)

Applying the exponent function and sum over $i=1,\dots ,n;$ we have:

$$\sum _{i=1}^n{e}^{{\partial }_i\left(A\left(G\right)\right)}\le \sum _{i=1}^n{e}^{{\partial }_i\left(A_{\alpha }\left(G\right)\right)}\le e^{n\alpha }\sum _{i=1}^n{e}^{{\partial }_i\left(A\left(G\right)\right)}.$$

Hence, we get the following results.

$$EE\left(G\right)\le EE\left(A_{\alpha }\left(G\right)\right)\le e^{n\alpha }EE\left(G\right).$$

(10)

As a consequence of the inequality (10), Lemma 3, and Theorem 1, we have the following result.

Theorem 5.

Let G be an $(n,m)$-graph. Then, the Estrada index of $A_{\alpha }$ is bounded as:

$$\sqrt{n^2+4m}\le EE\left(A_{\alpha }\left(G\right)\right)\le e^{n\alpha }(n-1+e^{\sqrt{2m}})$$

(11)

and:

$$EE\left(A_{\alpha }\left(G\right)\right)\ge n+m+t.$$

(12)

The equality case on both inequalities is attained if and only if $\alpha =0$ and G is isomorphic to $\overline{K_n}$.

In this paper, new lower bounds for the Estrada index are established. Considering Theorem 3 and the results previously shown, we allow obtaining new lower bounds for the Estrada index of the $A_{\alpha }$-matrix.

2. Estrada Index and Energy

In this section, in order to obtain new lower bounds to approximate the value of the Estrada index of the $A_{\alpha }$-matrix, new lower bounds are established for the Estrada index in relation to the energy of the G graph.

The energy of a graph G was defined by Ivan Gutman in 1978 [21] as:

$$E\left(G\right)=\sum _{i=1}^n\left|{\lambda }_i\right|.$$

The energy of a graph G is studied in mathematical chemistry and used to approximate the total $\pi$-electron energy of a molecule. Eventually, it was recognized that the interest in this graph invariant goes far beyond chemistry; see the recent papers [22,23,24,25,26] and the references cited therein.

In [27], Koolen and Moulton showed that the following relation holds for all graphs G

$$E\left(G\right)\le {\lambda }_1+\sqrt{(n-1)(2m-{\lambda }_1^2)}.$$

(13)

For all $(n,m)$-graphs G connected and nonsingular, Das et al. in [28] proved the following relation holds:

$$E\left(G\right)\ge {\lambda }_1+(n-1)+ln\left(detA\right)+ln\left({\lambda }_1\right),$$

(14)

then using the inequality $2m/n\le {\lambda }_1$ in (13) and (14), they obtained the following upper and lower bounds, respectively:

$$E\left(G\right)\le \frac{2m}{n}+\sqrt{(n-1)\left(2m-{\left(\frac{2m}{n}\right)}^2\right)}$$

and:

$$E\left(G\right)\ge \frac{2m}{n}+(n-1)+ln\left|det\left(A\right)\right|+ln\left(\frac{2m}{n}\right).$$

Theorem 6.

Let G be an $\left(n,m\right)$-graph with k non-negative eigenvalues. Then:

$$EE\left(G\right)\ge \frac{E\left(G\right)}{2}+e^{\left(\frac{2m}{n}\right)}+(k-1)-\frac{2m}{n}.$$

(15)

Equality holds in (15) if and only if G is isomorphic to $\overline{K_n}$.

Proof. 

Let $x\ge 0$, and consider the following function:

$$g\left(x\right)=-1-x+e^x;$$

(16)

the equality holds if and only if $x=0$. It is straightforward to show that function $g\left(x\right)$ is increasing in $[0,+\infty )$. Then, $g\left(x\right)\ge g\left(0\right)$, implying that:

$$x\le e^x-1,x\ge 0.$$

(17)

Note that, as $A\left(G\right)$ is a symmetric matrix with zero trace, these eigenvalues are real with the sum equal to zero, i.e.,

$${\lambda }_1\ge \cdots \ge {\lambda }_n$$

(18)

and:

$${\lambda }_1+\cdots +{\lambda }_n=0.$$

(19)

Then, by the definition of the energy join to (18) and (19), we have:

$$\frac{E\left(G\right)}{2}=\sum _{{\lambda }_i>0}{\lambda }_i^{+}=-\sum _{{\lambda }_i<0}{\lambda }_i^{-}.$$

(20)

Suppose that $A\left(G\right)$ have k non-negative eigenvalues, then using (20) and (17), we obtain:

$$\begin{array}{ccc}\hfill \frac{E\left(G\right)}{2}& =& \sum _{i=1,{\lambda }_i\ge 0}^k{\lambda }_i\hfill \\ & =& {\lambda }_1+\sum _{i=2,{\lambda }_i\ge 0}^k{\lambda }_i\hfill \\ & \le & {\lambda }_1+\sum _{i=2,{\lambda }_i\ge 0}^k\left(e^{{\lambda }_i}-1\right)\hfill \\ & =& {\lambda }_1-\left(k-1\right)+\sum _{i=1,{\lambda }_i\ge 0}^k{e}^{{\lambda }_i}-\left(e^{{\lambda }_1}\right)\hfill \\ & \le & {\lambda }_1-\left(k-1\right)+\sum _{i=1,{\lambda }_i\ge 0}^k{e}^{{\lambda }_i}+\sum _{i=k+1,{\lambda }_i<0}^n{e}^{{\lambda }_i}-e^{{\lambda }_1}\hfill \\ & =& {\lambda }_1-\left(k-1\right)+\sum _{i=1}^n{e}^{{\lambda }_i}-e^{{\lambda }_1}.\hfill \end{array}$$

Thereby, considering ${\lambda }_1\ge \frac{2m}{n},$ we obtain the first result.

Suppose now that the equality holds. From the equality in (16), we get ${\lambda }_1=\dots ={\lambda }_n=0.$ Then, $k=n$. Therefore, G is isomorphic to $\overline{K_n}$. Note that if G is equal to $\overline{K_n}$, it is easy to check that the equality in (15) holds. □

As a consequence of the above theorem and the lower bound due to Das et al. in (14), we obtain the following result.

Corollary 1.

Let G be a connected non-singular graph of order n with k strictly positive eigenvalues. Then:

$$\begin{array}{c}\hfill EE\left(G\right)\ge \frac{1}{2}\left(n-1+ln\left(det\left(A\left(G\right)\right)\right)+ln\left({\lambda }_1\right)\right)+e^{{\lambda }_1}+(k-1)-\frac{{\lambda }_1}{2}.\end{array}$$

3. Comparison and Conclusions

In this section, in order to show that our results improve the existing results in the literature, we present some computational experiments to compare our new lower bounds with the lower bounds existing in the literature for connected graphs. For comparison reasons, we consider the explicit values of the eigenvalues of the mentioned graphs. In the following table, the real value of the Estrada index of some graphs is compared with the approximate values obtained by applying Theorem 3 (Thm.3) and Theorem 6 (Thm.6) obtained in this paper together with some existing results in the literature, for example Theorem 1 (Thm.1) in [17], Theorem 13 in [23] (Thm.13), and Theorem 2 (Thm.2) in [18].

Graph	EE(G)	Thm 1	Thm 2	Thm 13	Thm 3	Thm 6
Herschel	45.195	22.738	13.892	26.5084	29.000	32.988
Heawood	46.176	28.000	16.733	30.1952	35.000	34.571
Petersen	34.218	20.000	12.649	21.2832	25.000	30.086
Grötzsch	55.619	23.685	14.177	29.0915	33.000	48.019
$K_4$	21.189	9.7980	6.3246	10.6829	14.000	20.086
$K_5$	56.070	15.000	8.0623	22.8344	25.000	54.598
$S_5$	10.524	8.0623	6.4031	8.0103	9.000	8.3530
$S_6$	13.463	9.7980	7.4833	9.7098	11.000	9.8639
$C_4$	9.5244	6.9282	5.6569	7.2896	8.000	9.3891
$C_5$	11.503	8.6603	6.7082	8.7768	10.000	10.625
$P_4$	7.6479	6.3246	5.2915	6.3059	7.000	6.2217
$P_5$	9.941	8.0620	6.4031	7.9106	9.000	8.083
$K_{2,3}$	14.669	9.2195	7.000	9.9628	11.000	14.073

Analyzing the above examples, we observe the following:

• In all our test cases, our lower bounds are better than existing bounds in the literature. Furthermore, we confirm Remark 2.
• Considering the results obtained in this paper, a possible way is to apply them to digraphs, which have seen relevant interest recently among researchers.