Energy of Nonsingular Graphs: Improving Lower Bounds

Abstract

Let $G$ be a simple graph of order $n$ and $A$ be its adjacency matrix. Let ${\lambda }_1\ge {\lambda }_2\ge \dots \ge {\lambda }_n$ be eigenvalues of matrix $A$. Then, the energy of a graph $G$ is defined as $\epsilon G={\displaystyle {\sum }_{i=1}^n{\lambda }_i}$. In this paper, we will discuss the new lower bounds for the energy of nonsingular graphs in terms of degree sequence, 2-sequence, the first Zagreb index, and chromatic number. Moreover, we improve some previous well-known bounds for connected nonsingular graphs.

This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.

1. Introduction

In this paper, we assume that $G$ is a simple graph and that $VG$ and $EG$ are the vertex set and the edge set so that $VG=n$ and $EG=m$. Let $d_i$ be the degree of vertex $v_i$. For convenience, we assume here that $K_n$ and $K_{a,b}$ are the complete graph and the complete bipartite graph, respectively.

Graph coloring is a way of coloring the vertices of a graph such that no two adjacent vertices are of the same color; this is called vertex coloring. The smallest number of colors needed to color a graph $G$ is called its chromatic number of $G$, denoted by $\chi G$.

The sum of the degrees of the vertices adjacent to $v_i$ is call the 2-degree of $v_i$ and denoted by $h_i$. The average degree is 2 degree, and we denote by $h_i/d_i$ the average degree of $v_i$. The first Zagreb of G, introduced in [1], is defined as follows:$$\begin{array}{}\text{(1)}& M_{1}G={\displaystyle \sum _{v_i\in V}{d}_{v_i}^2}.\end{array}$$

Assuming that ${\lambda }_1\ge {\lambda }_2\ge \dots \ge {\lambda }_n$ is eigenvalues of adjacency matrix $A$, we know that$$\begin{array}{}\text{(2)}& \det A={\displaystyle \prod _{i=1}^n{\lambda }_i}.\end{array}$$

If $\det A=0$, we call G singular, otherwise we call it nonsingular.

According to the eigenvalues of the adjacency matrix, the energy of a graph is defined as follows:$$\begin{array}{}\text{(3)}& \epsilon G={\displaystyle \sum _{i=1}^n{\lambda }_i}.\end{array}$$

Graph energy was first used in chemistry to approximate the energy of $\pi$-electron of a molecule [2, 3].

Liu et al. [4] derived some new bounds for the energy. Filipovski and Jajcay [5], derived some of the bounds for the energy. Das and Gutman [6] discussed bounds for the energy and improved some of the bounds. In 2017, Jahanbani [7] obtained some of the lower bounds for the energy. In 2018, Jahanbani [8] obtained some of the upper bounds for the energy and improved well-known bounds. In 2020, Filipovski and Jajcay [5] derived some of lower bounds for the energy. In 2021, Filipovski and Jajcay [5] obtained new bounds for the energy. In this paper, we continue this discussion by obtaining new bounds for the energy of nonsingular connected graph and improving some important bounds.

The oldest bounds are discovered by McClelland [9–12]. Bounds have been favored by researchers in the mathematical sciences, see [5, 6, 8, 13–17].

McClelland, in [12], obtained the next result:$$\begin{array}{}\text{(4)}& \epsilon G\ge {2m+nn-1{\det A}^{2/n}}^{1/2}.\end{array}$$

The proof of the following bound can be found in [18]:$$\begin{array}{}\text{(5)}& \epsilon G\ge 2\sqrt{m}.\end{array}$$

The next result is obtained by Das et al. in [19]:$$\begin{array}{}\text{(6)}& \epsilon G\ge \frac{2m}{n}+n-1+\ln \det A-\ln \frac{2m}{n}.\end{array}$$

2. Preliminaries

In this section, we recall some of the results that we will need to prove the main results.

It is straightforward to demonstrate the following two results.

Lemma 1.

Consider function $f_1$ as follows:$$\begin{array}{}\text{(7)}& f_{1}y=y-1-\ln y.\end{array}$$

Then, functions $f_{1}y$ are increasing for $y\ge 1$ and decreasing for $0<y\le 1$.

Lemma 2.

Function $gy=y+n-1+\ln \det A-\ln y$ is an increasing function on $1,n$.

Lemma 3 (see [20]).

For a connected graph $G$ with $n$ vertices and $m$ edges, we have$$\begin{array}{}\text{(8)}& {\lambda }_1\ge \frac{2m}{n}.\end{array}$$

Lemma 4 (see [21]).

For a nonempty graph, we have$$\begin{array}{}\text{(9)}& {\lambda }_1\ge \sqrt{\frac{{\displaystyle {\sum }_{i=1}^n{h}_i^2}}{{\displaystyle {\sum }_{i=1}^n{d}_i^2}}}.\end{array}$$

Lemma 5 (see [22, 23]).

For a connected graph with $n$ vertices, we have$$\begin{array}{}\text{(10)}& {\lambda }_1\ge \sqrt{\frac{M_{1}G}{n}}.\end{array}$$

Lemma 6 (see [20]).

For a connected graph with chromatic number $\chi$, we have$$\begin{array}{}\text{(11)}& {\lambda }_1\ge \chi -1.\end{array}$$

Lemma 7 (see [24]).

Suppose $G$ be a graph with $n\ge 2$ vertices; then,$$\begin{array}{}\text{(12)}& {\lambda }_1\ge \frac{1}{2}{\max }_{j<i}\sqrt{d_i+d_j+\sqrt{{d_i-d_j}^2+4c_{ij}^2}},\end{array}$$where $c_{ij}$ is the number of common neighbours of $i$ and $j$.

Lemma 8 (see [24]).

Suppose $G$ be a graph with $n$ vertices; then,$$\begin{array}{}\text{(13)}& {\lambda }_1\ge \sqrt[4]{\frac{1}{n}{\displaystyle \sum _{i=1}^n{d_i+2{\displaystyle \sum _{i>j}{c}_{ij}}}^2}},\end{array}$$where $c_{ij}$ is the number of common neighbours of $i$ and $j$.

Lemma 9 (see [25]).

Let $G$ be a graph; then, it has only one distinct eigenvalue if and only if $G$ is an empty graph and $G$ has 2 distinct eigenvalues ${\lambda }_1>{\lambda }_2$ with multiplicities $s_1$ and $s_2$ if and only if $G$ is the direct sum of $m_1$ complete graphs of order ${\lambda }_1+1$. Also, ${\lambda }_2=-1$ and $s_2=s_1{\lambda }_1$.

3. Lower Bounds for the Energy of Nonsingular Graphs

In this section, we present new lower bounds for energy of a nonsingular graph $G$.

Theorem 1.

Let $G$ be a nonempty and nonsingular graph with $n$ vertices and $m$ edges. Then,$$\begin{array}{}\text{(14)}& \epsilon G\ge \sqrt{\frac{M_{1}G}{n}}+n-1+\ln \det A-\ln \sqrt{\frac{M_{1}G}{n}}.\end{array}$$

Equality holds if and only if $G\cong K_n$.

Proof.

Note that $G$ is nonsingular; hence, we have ${\lambda }_i>0$, for $i=\mathrm{1,2},\dots ,n$. From Lemma 1, we have $f_{1}y\ge f_{1}1=0$; therefore,$$\begin{array}{}\text{(15)}& y\ge 1+\ln y,\end{array}$$where $y>0$, and the equality holds if and only if $y=1$. By applying the definition of energy, we can write$$\begin{array}{c}\text{(16)}& \epsilon G={\lambda }_1+{\displaystyle \sum _{i=2}^n{\lambda }_i}\ge {\lambda }_1+n-1+{\displaystyle \sum _{i=2}^n\ln {\lambda }_i}\\ ={\lambda }_1+n-1+\ln {\displaystyle \prod _{i=2}^n{\lambda }_i}\\ ={\lambda }_1+n-1+\ln \det A-\ln {\lambda }_1.\end{array}$$

By Lemma 5, we have ${\lambda }_1\ge \sqrt{M_{1}G/n}$. From Lemma 2, we obtain$$\begin{array}{}\text{(17)}& g{\lambda }_1\ge g\sqrt{\frac{M_{1}G}{n}}=\sqrt{\frac{M_{1}G}{n}}+n-1+\ln \det A-\ln \sqrt{\frac{M_{1}G}{n}}.\end{array}$$

From the above result and equality (16), we get our result.

Now, to prove the second part of the theorem, if $G\cong K_n$, it can be easily seen that the equality in Theorem 1 holds. Conversely, if the equality in Theorem 1 holds, then, by Lemma 5, we obtain$$\begin{array}{}\text{(18)}& {\lambda }_1=\sqrt{\frac{M_{1}G}{n}}.\end{array}$$

Note that $G$ is a nonempty graph; by using Lemma 9, we know that the graph $G$ has at least two distinct eigenvalues. Hence, we continue the proof with the following two cases.

Case 1.

Let ${\lambda }_1={\lambda }_2=\dots ={\lambda }_n$.

Note that ${\displaystyle {\sum }_{i=1}^n{\lambda }_i^2}=2m$ holds directly for any graph with m edges. Hence, we have ${{\displaystyle {\sum }_{i=2}^n{\lambda }_i}}^2=2m-{\lambda }_1^2$. So, we have ${\lambda }_1={\lambda }_i=\sqrt{2m-{\lambda }_1^2/n-1}$, since $G$ has at least two distinct eigenvalues for $2\le i\le n$. By inequality (15), we have $y\ge 1+\ln y$, and since the equality holds for $y=1$, we directly have that the absolute values of ${\lambda }_2,\dots {\lambda }_n$ is 1. Hence, $2m=n$ and also ${\lambda }_1={\lambda }_2=\dots ={\lambda }_n=1$. By applying Lemma 9, we obtain that $s_2=s_1{\lambda }_1,{\lambda }_1=1$; then, $s_1=s_2$. Thereby, we obtain that ${\lambda }_1=1$ has multiplicity $n/2$, and ${\lambda }_i=-1$ has multiplicity $n/2$ for $2\le i\le n$. Therefore, $G$ is the direct sum of $s_1=n/2$ complete graphs of order ${\lambda }_1+1=2$. Therefore, $G\cong n/2K_2$, which we see is in contradiction with the nonsingular graph.

Case 2.

The absolute value of all eigenvalues of $G$ is not equal. Then, $G$ has 2 distinct eigenvalues with different absolute values. Similar to Case 1, we have that the absolute values of ${\lambda }_2,\dots {\lambda }_n$ is 1. Since, ${\displaystyle {\sum }_{i=1}^n{\lambda }_i}=0$ and ${\lambda }_i=-1$ for $2\le i\le n$, then we have ${\lambda }_1=n-1$. Hence, ${\lambda }_1$ has multiplicity 1 and ${\lambda }_i=-1$ has multiplicity $n-1$. By Lemma 9, $G$ is the direct sum of a complete graph of order ${\lambda }_1+1=n$. In other words, $G\cong K_n$.

Using the technique to demonstrate Theorem 1, we get the next result.

Theorem 2.

For any nonempty and nonsingular connected graph $G$ with $n$ vertices and chromatic number $\chi$, we have$$\begin{array}{}\text{(19)}& \epsilon G\ge \chi -1+n-1+\ln \det A-\ln \chi -1.\end{array}$$

Equality in (19) holds if and only if $G\cong K_n$.

Theorem 3.

For any nonempty and nonsingular graph $G$ with $n$ vertices, we have$$\begin{array}{}\text{(20)}& \epsilon G\ge \sqrt{\frac{{\displaystyle {\sum }_{i=1}^n{h}_i^2}}{{\displaystyle {\sum }_{i=1}^n{d}_i^2}}}+n-1+\ln \det A-\ln \sqrt{\frac{{\displaystyle {\sum }_{i=1}^n{h}_i^2}}{{\displaystyle {\sum }_{i=1}^n{d}_i^2}}}.\end{array}$$

Proof.

Note that $G$ is nonsingular; hence, we have ${\lambda }_i>0$, for $i=\mathrm{1,2},\dots ,n$. Thus,$$\begin{array}{}\text{(21)}& \det A={\displaystyle \prod _{i=1}^n{\lambda }_i}>0.\end{array}$$

By equality (16), we can write$$\begin{array}{c}\text{(22)}& \epsilon G={\lambda }_1+{\displaystyle \sum _{i=2}^n{\lambda }_i}\ge {\lambda }_1+n-1+{\displaystyle \sum _{i=2}^n\ln {\lambda }_i}\\ ={\lambda }_1+n-1+\ln {\displaystyle \prod _{i=2}^n{\lambda }_i}\\ ={\lambda }_1+n-1+\ln \det A-\ln {\lambda }_1.\end{array}$$

From Lemma 4, we have ${\lambda }_1\ge \sqrt{{\displaystyle {\sum }_{i=1}^n{h}_i^2}/{\displaystyle {\sum }_{i=1}^n{d}_i^2}}$. By Lemma 2, we can write$$\begin{array}{}\text{(23)}& g{\lambda }_1\ge g\sqrt{\frac{{\displaystyle {\sum }_{i=1}^n{h}_i^2}}{{\displaystyle {\sum }_{i=1}^n{d}_i^2}}}=\sqrt{\frac{{\displaystyle {\sum }_{i=1}^n{h}_i^2}}{{\displaystyle {\sum }_{i=1}^n{d}_i^2}}}+n-1+\ln \det A-\ln \sqrt{\frac{{\displaystyle {\sum }_{i=1}^n{h}_i^2}}{{\displaystyle {\sum }_{i=1}^n{d}_i^2}}}.\end{array}$$

By inequality (23) and equality (22), we get our result.

Theorem 4.

For any nonempty and nonsingular graph with $n$ vertices, we have$$\begin{array}{}\text{(24)}& \mathcal{E}G\ge \frac{1}{2}{\max }_{j<i}\sqrt{d_i+d_j+\sqrt{{d_i-d_j}^2+4c_{ij}^2}}+n-1+\ln \det A-\ln \frac{1}{2}{\max }_{j<i}\sqrt{d_i+d_j+\sqrt{{d_i-d_j}^2+4c_{ij}^2}}.\end{array}$$

Proof.

With the same argument as before, we can write$$\begin{array}{}\text{(25)}& \epsilon G={\lambda }_1+{\displaystyle \sum _{i=2}^n{\lambda }_i}\ge {\lambda }_1+n-1+\ln \det A-\ln {\lambda }_1.\end{array}$$

From Lemma 7, we obtain$$\begin{array}{}\text{(26)}& {\lambda }_1\ge \frac{1}{2}\underset{j<i}{\max }\sqrt{d_i+d_j+\sqrt{{d_i-d_j}^2+4c_{ij}^2}}.\end{array}$$

According to the properties of function $g$, we have that$$\begin{array}{c}\text{(27)}& g{\lambda }_1\ge g\frac{1}{2}\underset{j<i}{\max }\sqrt{d_i+d_j+\sqrt{{d_i-d_j}^2+4c_{ij}^2}}=\frac{1}{2}\underset{j<i}{\max }\sqrt{d_i+d_j+\sqrt{{d_i-d_j}^2+4c_{ij}^2}}+n-1\\ +\ln \det A-\ln \frac{1}{2}\underset{j<i}{\max }\sqrt{d_i+d_j+\sqrt{{d_i-d_j}^2+4c_{ij}^2}}.\end{array}$$

From the above inequality and equality (25), we obtain our result.

Similarly to Theorem 4 and by using Lemma 8, we can reach the following result.

Theorem 5.

Let $G$ be a nonempty and nonsingular graph with $n$ vertices. Then,$$\begin{array}{c}\text{(28)}& \epsilon G\ge \sqrt[4]{\frac{1}{n}{\displaystyle \sum _{i=1}^n{d_i+2{\displaystyle \sum _{i>j}{c}_{ij}}}^2}}+n-1+\ln \det A-\ln \sqrt[4]{\frac{1}{n}{\displaystyle \sum _{i=1}^n{d_i+2{\displaystyle \sum _{i>j}{c}_{ij}}}^2}}.\end{array}$$

4. Improving Some of Bounds for the Energy of Connected Nonsingular Graphs

In this section, we show that the lower bounds in (14) and (20) are better than the classical bound [19] given by$$\begin{array}{}\text{(29)}& \epsilon G\ge \frac{2m}{n}+n-1+\ln \det A-\ln \frac{2m}{n},\end{array}$$for nonsingular connected graphs. Moreover, we show that inequality (20) is better than inequality (14).

Theorem 6.

The bound in (14) improves the well-known bound in (6) for all connected nonsingular graphs.

Proof.

Since $gx$ is increasing on $1,n$ and since $\sqrt{M_{1}G/n}\ge 2m/n\ge 1$ (note that $M_{1}G\ge 4m^2/n$), hence, we have $g\sqrt{M_{1}G/n}\ge g2m/n$, that is, the bound in (14) is better than the bound in (6).

Corollary 1.

The bound in (14) improves the well-known bound in (4) for all connected nonsingular graphs.

Theorem 7.

The bound in (20) improves the well-known bound in (6) for all connected nonsingular graphs.

Proof.

Since the bound in (19) is always better the bound in (6), the proof relies on the same facts as in Theorem 6. Use the relation $\sqrt{{\displaystyle {\sum }_{i=1}^n{h}_i^2}/{\displaystyle {\sum }_{i=1}^n{d}_i^2}}\ge 2m/n$ and $g\sqrt{{\displaystyle {\sum }_{i=1}^n{h}_i^2}/{\displaystyle {\sum }_{i=1}^n{d}_i^2}}\ge g2m/n$, that is, the bound in (20) is better than the bound in (6).

Theorem 8.

The bound in (20) improves the bound in (14) for all connected nonsingular graphs.

Proof.

Since$$\begin{array}{}\text{(30)}& \sqrt{\frac{{\displaystyle {\sum }_{i=1}^n{h}_i^2}}{{\displaystyle {\sum }_{i=1}^n{d}_i^2}}}\ge \sqrt{\frac{{{\displaystyle {\sum }_{i=1}^n{h}_i}}^2}{n{\displaystyle {\sum }_{i=1}^n{d}_i^2}}}=\sqrt{\frac{1}{n}{\displaystyle \sum _{i=1}^n{d}_i^2}}=\sqrt{\frac{M_{1}G}{n}},\end{array}$$by using the properties of the $g$ function, we can write $g\sqrt{{\displaystyle {\sum }_{i=1}^n{h}_i^2}/{\displaystyle {\sum }_{i=1}^n{d}_i^2}}\ge g\sqrt{M_{1}G/n}$, that is, the bound in (20) is better than the bound in (14).

Acknowledgments

J. Rodríguez was supported by MINEDUC-UA Project, code ANT-1899, and funded by the Initiation Program in Research-Universidad de Antofagasta, INI-19-06, and Programa Regional MATHAMSUD MATH2020003.

References

[1] I. Gutman, N. Trinajstić, "Graph theory and molecular orbitals. Total π -electron energy of alternant hydrocarbons," Chemical Physics Letters, vol. 17 no. 4, pp. 535-538, DOI: 10.1016/0009-2614(72)85099-1, 1972.

[2] I. Gutman, O. E. Polansky, Mathematical Concepts in Organic Chemistry, 1986.

[3] I. Gutman, "The energy of a graph: old and new results," Algebraic Combinatorics and Applications, pp. 196-211, DOI: 10.1007/978-3-642-59448-9_13, 2001.

[4] H. Liu, M. Lu, F. Tian, "Some upper bounds for the energy of graphs," Journal of Mathematical Chemistry, vol. 41 no. 1,DOI: 10.1007/s10910-006-9183-9, 2007.

[5] S. Filipovski, R. Jajcay, "New upper bounds for the energy and spectral radius of graphs," MATCH Communications in Mathematical and in Computer Chemistry, vol. 84, pp. 335-343, 2020.

[6] K. C. Das, I. Gutman, "Bounds for the energy of graphs," Hacettepe Journal of Mathematics and Statistics, vol. 45 no. 3, pp. 695-703, DOI: 10.15672/hjms.20164513097, 2016.

[7] A. Jahanbani, "Some new lower bounds for energy of graphs," Applied Mathematics and Computation, vol. 296, pp. 233-238, DOI: 10.1016/j.amc.2016.10.019, 2017.

[8] A. Jahanbani, "Upper bounds for the energy of graphs," MATCH Communications in Mathematical and in Computer Chemistry, vol. 79, pp. 275-286, 2018.

[9] I. Gutman, "McClelland-type approximations for total π -electron energy of benzenoid hydrocarbons," MATCH Communications in Mathematical and in Computer Chemistry, vol. 26, pp. 123-135, 1991.

[10] I. Gutman, "The McClelland approximation and the distribution of π -electron molecular orbital energy levels," Journal of the Serbian Chemical Society, vol. 72 no. 10, pp. 967-973, DOI: 10.2298/jsc0710967g, 2007.

[11] I. Gutman, M. Milun, N. Trinajstić, "Comment on the paper: “Properties of the latent roots of a matrix. Estimation of π ‐electron energies” by B. J. McClelland," The Journal of Chemical Physics, vol. 59 no. 5, pp. 2772-2774, DOI: 10.1063/1.1680406, 1973.

[12] B. J. McClelland, "Properties of the latent roots of a matrix: the estimation of π ‐electron energies," The Journal of Chemical Physics, vol. 54 no. 2, pp. 640-643, DOI: 10.1063/1.1674889, 1971.

[13] S. Akbari, A. H. Ghodrati, M. A. Hosseinzadeh, "Some lower bounds for the energy of graphs," Linear Algebra and Its Applications, vol. 591, pp. 205-214, DOI: 10.1016/j.laa.2020.01.001, 2020.

[14] N. Alawiah, N. J. Rad, A. Jahanbani, H. Kamarulhaili, "New upper bounds on the energy of a graph," MATCH Communications in Mathematical and in Computer Chemistry, vol. 79, pp. 287-301, 2018.

[15] S. Filipovski, R. Jajcay, "Bounds for the energy of graphs," Mathematics, vol. 9 no. 14,DOI: 10.3390/math9141687, 2021.

[16] A. Jahanbani, "Lower Bounds for the Energy of graphs," AKCE International Journal of Graphs and Combinatorics, vol. 15 no. 1, pp. 88-96, DOI: 10.1016/j.akcej.2017.10.007, 2018.

[17] H. Shooshtary, J. Rodriguez, "New bounds on the energy of a graph," Communications in Combinatorics and Optimization,DOI: 10.22049/CCO.2021.26999.1179, 2021.

[18] G. Caporossi, D. Cvetković, I. Gutman, P. Hansen, "Variable neighborhood search for extremal graphs. 2. Finding graphs with extremal energy," Journal of Chemical Information and Computer Sciences, vol. 39 no. 6, pp. 984-996, DOI: 10.1021/ci9801419, 1999.

[19] K. Das, S. A. Mojallal, I. Gutman, "Improving McClellands lower bound for energy," MATCH Communications in Mathematical and in Computer Chemistry, vol. 70, pp. 663-668, 2013.

[20] O. Favaron, M. Mahéo, J.-F. Saclé, "Some eigenvalue properties in graphs (conjectures of Graffiti-II)," Discrete Mathematics, vol. 111 no. 1-3, pp. 197-220, DOI: 10.1016/0012-365x(93)90156-n, 1993.

[21] A. Yu, M. Lu, F. Tian, "On the spectral radius of graphs," Linear Algebra and Its Applications, vol. 387, pp. 41-49, DOI: 10.1016/j.laa.2004.01.020, 2004.

[22] Y. Hong, "Sharp upper and lower bounds for largest eigenvalue of the laplacian matrix of trees," Discrete Mathematics, vol. 296,DOI: 10.1016/j.disc.2005.04.001, 2003.

[23] J. H. Koolen, V. Moulton, I. Gutman, "Improving the McClelland inequality for total π -electron energy," Chemical Physics Letters, vol. 320 no. 3-4, pp. 213-216, DOI: 10.1016/s0009-2614(00)00232-3, 2000.

[24] R. Kumar, "Bounds for eigenvalues of a graph," Journal of Mathematical Inequalities, vol. 4 no. 3, pp. 399-404, DOI: 10.7153/jmi-04-36, 2010.

[25] D. Cvetkovic, M. Doob, H. Sachs, Spectra of Graphs Theory and Applications, 1980.