Graph energy and nullity

1. Introduction

The concept of graph energy was introduced in 1978 [1], as a kind of generalization of the HMO total \(\pi\)-electron energy [2]. After a twenty-years period of silence, graph energy became a popular topic of research in chemical graph theory [3], with over than hundred papers published each year [4, 5 ]. Of the numerous properties established for graph energy, one remains a long-time open problem. Namely, already in the early days of the study of graph energy and its predecessor total \(\pi\)-electron energy, it was observed that it somehow decreases with the increasing number of zero eigenvalues in the graph spectrum [2, 6].

Let \(G\) be a (molecular) graph, possessing \(n\) vertices. Let \(\lambda_1,\lambda_2\ldots,\lambda_n\) be the eigenvalues of the \((0,1)\)-adjacency matrix of \(G\), forming the spectrum of \(G\). Then the energy of \(G\) is defined as [1, 3]: \[ E = E(G) = \sum_{i=1}^n |\lambda_i|, \] whereas its nullity, denoted by \(\eta=\eta(G)\), is equal to the number of zero eigenvalues (= the algebraic multiplicity of the number zero in the graph spectrum). Then the above mentioned regularity can be formally stated as follows.

Conjecture 1. Let \(G\) and \(G^\prime\) be two structurally similar graphs. Let \(\eta(G) < \eta(G^\prime)\). Then \(E(G) > E(G^\prime)\).

The problem with this conjecture is that the meaning of ``structurally similar graphs'' is not clear and cannot be rigorously defined. Earlier attempts to justify its validity were based on designing approximate expression for \(E(G)\), containing the term \(\eta(G)\) [6, 7, 8, 9], or by constructing a suitably chosen example for the graphs \(G,G^\prime\) [10].

It this paper we elaborate a general method for quantifying the dependence of graph energy on nullity, in which the usage of the ``structurally similar graph'' \(G^\prime\) is avoided.

2. Effect of nullity on the energy of a non-singular graph

Let \(G\) be a (molecular) graph as defined above, and assume that it is non-singular, i.e., that it has no zero eigenvalues, \(\eta(G)=0\). Let its characteristic polynomial be \[ \phi(G,\lambda) = \sum_{k=0}^n c_k\,\lambda^{n-k} = \prod_{i=1}^n (\lambda-\lambda_i), \] and recall that and for \(k=2,...,n\). In particular, \[ c_n = \prod_{i=1}^n \lambda_i \neq 0. \] Throughout this paper, since we are mainly interested in molecular graphs, it will be assumed that \(n\) is even, and that \[ \lambda_1 \geq \lambda_2 \geq \cdots \lambda_{n/2} > 0 > \lambda_{n/2+1} \geq \lambda_{n/2+2} \geq \cdots \geq \lambda_n\,. \] If so, then \(c_2<0\), \(c_4>0\), \(c_6<0\), \(c_8>0\), \ldots, i.e., and The coefficients \(c_k\) are the structural parameters of the graph \(G\) on which its energy depends. It is known that [11, 12, 13, 14]: where \(i=\sqrt{-1}\) and \(Re\) indicates the real part of a complex number. Recall that for any complex number \(z\), \ \(|z| \geq Re(z)\). Our approach is based on the following. Instead of looking for a graph \(G^\prime\) that would be ``structurally similar'' to \(G\), we construct a quasi-spectrum, consisting of the numbers \(\lambda^\prime_1,\lambda^\prime_2,\ldots,\lambda^\prime_n\), that would be as similar as possible to the true spectrum of \(G\), but that would contain a single zero element. Let \(\lambda^\prime_k \neq 0\) for \(k=1,2,\ldots,n-1\) and \(\lambda^\prime_n=0\), which is equivalent to the condition \(\eta(G^\prime) = 1\). Then, in analogy to Eqs. (1) and (2), we define \[ c^\prime_0 = 1 \ \ , \ \ c^\prime_1 = \sum_{i=1}^n \lambda^\prime_i = 0, \] and \[ c^\prime_k = \sum_{1 \leq i_1 < i_2 < \cdots < i_k \leq n} \lambda^\prime_{i_1}\,\lambda^\prime_{i_2}\cdots \lambda^\prime_{i_k}, \] for \(k=2,...,n\), implying that \[ c^\prime_n = \prod_{i=1}^n \lambda^\prime_i = 0\,. \] Bearing in mind Equation (5), we now construct an auxiliary quantity [15, 16]: \[ E^\prime(G) = \frac{2}{\pi} \int\limits_0^\infty \ln \left| \sum_{k=0}^n c^\prime_k\,(ix)^{-k} \right| dx\,. \] By requiring that \(c^\prime_k = c_k\) for \(k=1,2,\ldots,n-1\), it immediately follows that \[ E^\prime(G) = \frac{2}{\pi} \int\limits_0^\infty \ln \left| \sum_{k=0}^{n-1} c_k\,(ix)^{-k} \right| dx\,. \] Thus, the quantity \(E^\prime(G)\) can be calculated from the coefficients of the characteristic polynomial of the graph \(G\). The difference \(E(G)-E^\prime(G)\) can be understood as the effect of a single zero eigenvalue, i.e., nullity \(\eta=1\), on the energy of a non-singular graph \(G\). Using the Coulson--Jacobs formula [11, 12], we get \[ E(G)-E^\prime(G) = Re \left[ \frac{2}{\pi}\,\int\limits_0^\infty \ln \frac{ \sum\limits_{k=0}^n c_k\,(ix)^{n-k}} { \sum\limits_{k=0}^{n-1} c_k\,(ix)^{n-k}}\,dx \right] = \frac{2}{\pi}\,\int\limits_0^\infty \ln \left| \frac{ \sum\limits_{k=0}^n c_k\,(ix)^{n-k}} { \sum\limits_{k=0}^{n-1} c_k\,(ix)^{n-k}} \right| dx, \] i.e., From Equation (6) it follows that \(E(G)-E^\prime(G)>0\), in agreement with Conjecture 1. In order to see this, note that \[ \frac{ \sum\limits_{k=0}^n c_k\,(ix)^{n-k}}{\sum\limits_{k=0}^{n-1} c_k\,(ix)^{n-k}} = \frac{A(x)-i\,B(x) + (-1)^{n/2}\,c_n}{A(x)-i\,B(x)}, \] where \( A(x) = \sum\limits_{k=0}^{n/2-1} (-1)^k\,c_{2k}\,x^{n-2k}\) and \(B(x) = \sum\limits_{k=0}^{n/2-1} (-1)^k\,c_{2k+1}\,x^{n-2k+1}\,. \) Then \[ Re \left[ \frac{ \sum\limits_{k=0}^n c_k\,(ix)^{n-k}}{\sum\limits_{k=0}^{n-1} c_k\,(ix)^{n-k}} \right] = \frac{A(x)^2+B(x)^2 + (-1)^{n/2}\,c)n}{A(x)^2+B(x)^2} = 1 + \frac{(-1)^{n/2}\,c_n\,A(x)}{A(x)^2+B(x)^2}, \] which by relations (3) and (4) is greater than unity for all values of \(x \in [0,+\infty)\). Therefore, \begin{eqnarray*} E(G)-E^\prime(G) & = & \frac{2}{\pi}\,\int\limits_0^\infty \ln \left| \frac{ \sum\limits_{k=0}^n c_k\,(ix)^{n-k}} { \sum\limits_{k=0}^{n-1} c_k\,(ix)^{n-k}} \right| dx \geq \frac{2}{\pi}\,\int\limits_0^\infty \ln Re \left[ \frac{ \sum\limits_{k=0}^n c_k\,(ix)^{n-k}} { \sum\limits_{k=0}^{n-1} c_k\,(ix)^{n-k}} \right] dx \\[5mm] & = & \frac{2}{\pi}\,\int\limits_0^\infty \ln \left[ 1 + \frac{(-1)^{n/2}\,c_n\,A(x)}{A(x)^2+B(x)^2} \right] dx > 0\,. \end{eqnarray*} Formula (6) makes it possible to directly compute the effect of nullity in the special case of \(\eta(G)=0\) and \(\eta(G^\prime)=1\), using only the spectrum of the graph \(G\). Numerical examples will be communicated at some later moment. A same kind of consideration for the case \(\eta(G)=0\) and \(\eta(G^\prime)=2\), leads to \[ E(G)-E^\prime(G) = \frac{2}{\pi}\,\int\limits_0^\infty \ln \left| \frac{ \sum\limits_{k=0}^n c_k\,(ix)^{n-k}} { \sum\limits_{k=0}^{n-2} c_k\,(ix)^{n-k}}\right| dx, \] i.e., \[ E(G)-E^\prime(G) = \frac{2}{\pi}\,\int\limits_0^\infty \ln \left| \frac{\phi(G,ix)}{\phi(G,ix)-c_n-c_{n-1}\,ix}\right| dx\,. \] Other, more complicated cases can be treated in an analogous manner.

Conflicts of Interest

The author declares no conflict of interest.