Trees with the second-minimal ABC energy

1.   Introduction

Let $G$ be a simple connected graph with vertex set $V(G) = \{v_1, v_2, \ldots, v_n\}$ and edge set $E(G)$. The eigenvalues of adjacency matrix $A(G)$ are called the eigenvalues of $G$. The energy $\mathcal{E}(G)$ of $G$ is defined as the sum of the absolute values of its eigenvalues of $A(G)$, which is studied in chemistry and used to approximate the total-electron energy of a molecule ^[3]. The singular values of an $n\times m$ matrix $M$ are the square roots of the eigenvalues of $MM^*$ if $n\ge m$ or $M^*M$ if $n < m$, where $M^*$ is the transpose conjugate of $M$. Nikiforov ^[4] extended the concept of energy to all matrices and defined the energy of a matrix $M$, denoted by $\mathcal{E}(M)$, as the sum of the singular values of $M$. Clearly, $\mathcal{E}(A(G)) = \mathcal{E}(G)$.

Estrada et al. ^[12] introduced the atom-bond connectivity index as

Moreover, they introduced the atom-bond connectivity matrix (or ABC matrix for short) $ABC_G$ of $G$, which is correlated with the ABC index of $G$. The $(i, j)$-entry of the matrix $ABC_G$ is equal to $\sqrt{\frac{d_i+d_j-2}{d_id_j}}$ if $v_iv_j\in E(G)$ and $0$ otherwise. The eigenvalues of the ABC matrix of $G$, denoted by $\mu_1, \mu_2, \dots, \mu_n$, are said to be the ABC eigenvalues of $G$. The atom-bond connectivity energy (ABC energy) of a connected graph $G$ is defined in ^[8] as

Recently, several theoretical and computational properties of the ABC energy of graphs have been obtained, see e.g., ^[1,8,13]. Estrada ^[8] and Chen ^[13] gave an upper bound and a lower bound for the ABC energy in terms of the general Randić index, respectively. Ghorbani et al. ^[1] established some new bounds for the ABC energy. Gao and Shao ^[7] determined the unique tree with the minimum ABC energy. In this paper, we determine the trees with the minimum ABC energy among all trees on $n$ vertices except the star $S_n$.

2.   Preliminaries

A matching in a graph is a set of edges without common vertices. A $k$-matching is a matching consisting of $k$ edges. Let $T$ be a tree, $M$ be a matching of $T$ and $M^k(T)$ be the set of all $k$-matchings of $T$. We define $m^*_M(T)$ and $m^*(T, k)$ by

and

respectively. By Sachs Theorem ^[14], the characteristic polynomial $\phi_{ABC}(T, x)$ of the ABC matrix of a tree $T$ can be expressed as

Then by Coulson integral formula, we get

Let $T_1$ and $T_2$ be two trees on $n$ vertices. If $m^*(T_1, k)\ge m^*(T_2, k)$ for all $k$, then by (2.1) we get $\mathcal{E}_{ABC}(T_1)\ge \mathcal{E}_{ABC}(T_2)$. Moreover, if there exists some $k$ such that $m^*(T_1, k) > m^*(T_2, k)$, then $\mathcal{E}_{ABC}(T_1) > \mathcal{E}_{ABC}(T_2)$.

Let $T$ be a tree on $n$ vertices, $B = (b_{ij})$ be an $n\times n$ nonnegative real symmetric matrix and $ABC_T\ge B$. Let $M$ be a matching of $T$, $m^*_M(B) = \prod_{v_iv_j\in M}b_{ij}^2$ and $m^*(B, k) = \sum_{M\in M^k(T)}m^*_M(B)$. Then

Clearly, $m^*(T, k)\ge m^*(B, k)$. Thus $\mathcal{E}_{ABC}(T)\ge\mathcal{E}(B)$. Moreover, if $(ABC_T)_{ij} > b_{ij}$ for some $v_iv_j\in E(T)$, then $\mathcal{E}_{ABC}(T) > \mathcal{E}(B)$. Thus we can get the following lemma.

Lemma 2.1. Let $T$ be a tree on $n$ vertices and $B$ be an $n\times n$ nonnegative real symmetric matrix. If $ABC_T\ge B$, then $\mathcal{E}_{ABC}(T)\ge\mathcal{E}(B)$. Moreover, if $(ABC_T)_{ij} > b_{ij}$ for some $v_iv_j\in E(T)$, then $\mathcal{E}_{ABC}(T) > \mathcal{E}(B)$.

Let $uv$ be an edge of a tree $T$ and $T-uv = T_1\cup T_2$, where $T_1(T_2)$ is the component of $T-uv$ containing $u(v, \ \text{respectively})$. We denote the sub-matrices of $ABC_T$ spanned by the vertices of $T_1$ and $T_2$ by $(ABC_T)_{V(T_1)}$ and $(ABC_T)_{V(T_2)}$, respectively.

By Lemma 2.1, we have the next lemma.

Lemma 2.2. Let $uv$ be an edge of a tree $T$ and $T-uv = T_1\cup T_2$, where $T_1(T_2)$ is the component of $T-uv$ containing $u (v, \ {{respectively}})$. Then

Suppose that $uv$ is not a pendent edge. If $d_T(w)\le 2$ for any $w\in N_T(u)\setminus \{v\}$, then

Furthermore, if $d(w)\le 2$ for any $w\in N_T(u)\cup N_T(v)\setminus \{u, v\}$, then

Lemma 2.3. (^[7]) Let $T$ be a tree of order $n\ge 3$. Then $\mathcal{E}_{ABC}(T)\ge 2\sqrt{n-2}$, withequality if and only if $T\cong S_n$, where $S_n$ is the star of order $n$.

Lemma 2.4. (^[7]) Let $t\ge 2, x_i\ge 3$ for $i = 1, \ldots, t$, and $\sum_{i = 1}^tx_i\ge 8.$ Then $\sum_{i = 2}^t\sqrt{x_i-2}\ge\sqrt{\sum_{i = 2}^tx_i+(t-1)-2}$.

3.   The minimum ABC energy of trees

For two graphs $G$ and $H$, we define $G\cup H$ to be their disjoint union. In addition, let $kG$ be the disjoint union of $k$ copies of $G$. Let $S_n^*$ be the tree formed by attaching a vertex to a pendent vertex of the star $S_{n-1}$. Note that

Thus

Lemma 3.1. Let $x\geq 11$. Then

Proof. It is equivalent to prove that

Let $f(x) = 2\sqrt{x-5}-\sqrt{2}\sqrt{x-4+\frac{1}{x-2}}-\frac{1}{x-2}-1$ with $x\geq 11$. Then

Thus $f(x)$ is a strictly monotonously increasing function on $x$. Noting that $f(11) = 0.0166 > 0$, then the lemma holds.

From Lemma 3.1, $\mathcal{E}_{ABC}(S_n^*) < 2+2\sqrt{n-5}$ for $n\ge 11$.

For $n = 1, 2, 3$, there is only unique tree $S_n$. For $n = 4$, there are exactly two trees $P_4$ and $S_4$. Obviously, $P_4$ is the tree with the second minimum ABC energy. For $n = 5$, there are exactly three trees $P_5$, $S_5$ and $S_5^*$. By direct calculation, we have $\mathcal{E}_{ABC}(S_5^*) = 3.9831 > \mathcal{E}_{ABC}(P_5) = \sqrt{2}+\sqrt{6} > 2\sqrt{3} = \mathcal{E}_{ABC}(S_5)$. Thus $P_5$ is the tree with the second minimum ABC energy. Let $P_5 = v_1v_2v_3v_4v_5$, we denote the tree, obtained by attaching a new vertex to $v_2$ of $P_5$, by $P^*_6$. For $n = 6$, there are exactly six trees $T_{2.8}, T_{2.9}, T_{2.10}, T_{2.11}, T_{2.12}, T_{2.13}$ (see tables of graph spectra in ^[14]), where $T_{2.8}\cong S_6, T_{2.9}\cong S_6^*$, $T_{2.11}\cong P_6^*$ and $T_{2.13}\cong P_6$. By direct calculation, $\mathcal{E}_{ABC}(T_{2.12}) = 5.0590 > \mathcal{E}_{ABC}(P_6) = 4.9412 > \mathcal{E}_{ABC}(T_{2.10}) = 4.8074 > \mathcal{E}_{ABC}(S_6^*) = 4.6352 > \mathcal{E}_{ABC}(P_6^*) = 4.6260 > \mathcal{E}_{ABC}(S_6) = 4$.

By simple calculations, we obtain the following lemma.

Lemma 3.2. Let $T$ be an $n$-vertex tree not isomorphic to $S_n$, where $7\le n\le 10$. Then $\mathcal{E}_{ABC}(T)\ge\mathcal{E}_{ABC}(S_n^*)$ with equality if and only if $T\cong S_n^*$.

Lemma 3.3. Let $T$ be a tree on $n\ge 11$ vertices.

(i) Let $u_1v_1\in E(G)$ and $T-u_1v_1 = T_1\cup T_2$, where $T_1(T_2)$ is the component of $T-u_1v_1$ containing $u_1(v_1, \ \mathit{\text{respectively}})$. If $d(w)\le 2$ for any $w\in N(u_1)\cup N(v_1)\setminus\{u_1, v_1\}$ and $|V(T_1)| = n_1\ge|V(T_2)| = n_2\ge 3$, then $\mathcal{E}_{ABC}(T) > \mathcal{E}_{ABC}(S_n^*)$.

(ii) Let $u_2v_2, u_3v_3\in E(G)$, $T-u_2v_2\cong P_2\cup T_3$ and $T_3-u_3v_3\cong P_2\cup T_4$, where $T_3$ is one of the component of $T-u_2v_2$ and $T_4$ is one of the component of $T_3-u_3v_3$. If $d_T(w_1)\leq2$ for any $w_1\in N_T(u_2)\cup N_T(v_2)\setminus\{u_2, v_2\}$ and $d_{T_3}(w_2)\le 2$ for any $w_2\in N_{T_3}(u_3)\cup N_{T_3}(v_3)\setminus\{u_3, v_3\}$, then $\mathcal{E}_{ABC}(T) > \mathcal{E}_{ABC}(S_n^*)$.

Proof. (ⅰ) By Lemmas 2.2 and 2.3, we have

(ⅱ) Similarly, by Lemmas 2.2 and 2.3, we have

We complete the proof.

Lemma 3.4. Let $n\ge 11$. Then $\mathcal{E}_{ABC}(P_n) > \mathcal{E}_{ABC}(S_n^*)$.

Proof. By Lemma 2.2, we have $\mathcal{E}_{ABC}(P_n) > \mathcal{E}_{ABC}(P_3)+\mathcal{E}_{ABC}(P_{n-3}) \ge 2+2\sqrt{n-5} > \mathcal{E}_{ABC}(S_n^*)$.

A tree is called starlike if it has exactly one vertex of degree greater than two.

Lemma 3.5. Let $T\not \cong S_n$ be a starlike tree with order $n\ge 11$ and $v$ be the unique vertex with degree at least three. Let $T-v = n_1P_1\cup n_2P_2\cup\dots\cup n_mP_m$ and $\sum_{i = 1}^m in_i+1 = n$. Then $\mathcal{E}_{ABC}(T) > \mathcal{E}_{ABC}(S_n^*)$.

Proof. If $n_i\ge 1$ for some $i\ge 3$, then there exists an edge $uv$ such that $T-uv = T_1\cup T_2$, where $T_1(T_2)$ is the component of $T-uv$ containing $u(v, \ \text{respectively})$, $|V(T_1)|, |V(T_2)|\ge 3$ and $d(w)\le 2$ for any $w\in N(u)\cup N(v)\setminus \{u, v\}$. Then by (ⅰ) of Lemma 3.3 we can get the result. Suppose that $n_i = 0$ for all $i\ge 3$. If $n_2 = 0$, then $T\cong S_n$. If $n_2 = 1$, then $T\cong S_n^*$. If $n_2\ge 2$, then by (ⅱ) of Lemma 3.3 we can get the result.

Let $T$ be a tree and $R(T)$ be set of vertices of degree greater than two in $T$.

Lemma 3.6. Let $T$ be a tree with $n\ge 11$ vertices and $|R(T)|\ge 2$. If there are no adjacent vertices in $R(T)$, then $\mathcal{E}_{ABC}(T) > \mathcal{E}_{ABC}(S_n^*)$.

Proof. Let $d(u)\geq 3$ and $d(v)\geq 3$ and $P_l = uv_1\dots v_{l-1}v$ be the single path connecting $u$ and $v$ with $d(v_1) = \cdots = d(v_{l-1}) = 2$. Clearly, $l\ge 2$. Without loss of generality, we suppose that $T-uv_1 = T_1\cup T_2$ such that $T_1$ is a starlike-tree or a path, where $u\in V(T_1)$.

If $l\ge3$, then by (i) of Lemma 3.3 we can get the result.

Suppose now that $l = 2$. Let $T'_1(T'_2)$ be the component of $T-uv_1-v_1v$ containing $u(v,$ respectively$)$, $s = |V(T'_1)|$ and $t = |V(T'_2)|$. Obviously, $s+t+1 = n$.

If $s = 3$, then the ABC matrix of $T$ can be written as

where

and $D = (ABC_{T})_{V(T'_2)}$. Let

Obviously, $D\ge ABC_{T'_2}$. Thus $ABC_T > A$. By Lemmas 2.1 and 2.3, we have

Suppose that $s = 4$. Then $T'_1\cong S_4$ or $P_4$. If $T'_1\cong S_4$, then the ABC matrix of $T$ can be written as

where

and $K = (ABC_{T})_{V(T'_2)}$. Let

Obviously, $K\ge ABC_{T'_2}$. Thus $ABC_T > M$. By Lemmas 2.1 and 2.3 we have

Suppose now that $T'_1\cong P_4$. Let $T'_1 = u_1uu_2u_3$. Then by Lemmas 2.2 and 2.3, we have

By symmetry, we now suppose that $5\le s, t\le n-6$, then by Lemmas 2.2 and 2.3, we have

Lemma 3.7. Let $T$ be a tree with $n\ge 11$ vertices and $|R(T)|\ge 2$. If there exist adjacent vertices in $R(T)$, then $\mathcal{E}_{ABC}(T) > \mathcal{E}_{ABC}(S_n^*)$.

Proof. Let $E^0 = \{uv\in E(T)| d(u), d(v)\ge 3\}$, and $T-E^0 = xP_1\cup y P_2\cup T_1\cup\cdots \cup T_z$, where $T_1, \ldots, T_z$ are components of $T-E^0$ with at least three vertices. Let $xP_1 = \{v_1, \ldots, v_x\}$ and $yP_2 = \{v_{x+1}v_{x+2}, \dots, v_{x+2y-1}v_{x+2y}\}$. Then $d_T(v_i)\geq 3$ with $1\leq i\leq x$, $d_T(v_{x+2j-1})\geq 3$ and $d_T(v_{x+2j}) = 1$ with $1\leq j\leq y$, and for each component $T_i$ with $1\leq i\leq z$, there exists a vertex $v_i\in V(T_i)$ such that $d_T(v_i)\geq d_{T_i}(v_i)+1$. Let $|V(T_i)| = s_i$ for $1\le i\le z$. Thus we have

Thus we get that $z\ge x+2$. We discuss the following four cases.

Case 1. $y = 0$ and $z = 2$.

Then $x = 0$ and $s_1+s_2 = n$. By Lemmas 2.2 and 2.3, we get

Case 2. $y = 0$ and $z\ge3$.

Then $x+\sum_{i = 1}^zs_i = n$. Without loss of generation, we suppose that $3\leq s_z\le s_{z-1}\le\cdots\le s_2\le s_1$.

If $\sum_{i = 1}^{z-1}s_i = 6$, then $z = 3, s_z = 3$ and $x\le 1$. Thus $n\le 10$, a contradiction.

If $\sum_{i = 1}^{z-1}s_i = 7$, then $z = 3, s_1 = 4, s_2 = s_3 = 3$. Thus $x = 1$ and $n = 11$. Obviously, $T_2\cong T_3\cong S_3$ and $T_1\cong S_4$ or $P_4$. By Lemmas 2.2 and 2.3, we have

Suppose that $\sum_{i = 1}^{z-1}s_i\ge 8$. By Lemmas 2.2–2.4, we have that

Case 3. $y\ge1$ and $z\ge 3$.

Then $\sum_{i = 1}^{z-1}s_i+s_z+x+2y = n$. By Lemmas 2.2 and 2.3, we have

If $\sum_{i = 1}^{z-1}s_i\ge 8,$ then by Lemma 2.4, we have

Here, the last but one inequality holds because $f(y) = 2y\sqrt{\frac{2}{3}}+2\sqrt{n-5-2y}+2$ is increasing for $0\leq y\leq \frac{2n-13}{4}$.

Suppose that $\sum_{i = 1}^{z-1}s_i\le 7$. Then $z = 3$. Thus $s_1+s_2 = 6$ or $7$, $s_3 = 3$ and $x\leq 1$.

Suppose first that $s_1+s_2 = 7$ and $s_3 = 3$. If $x = 0,$ then $n = 2y+10$. Hence

Suppose now that $x = 1$. Then $n = 2y+11$. Hence

Let $f(x) = (x-11)\sqrt{\frac{2}{3}}+4+2\sqrt{2}-2\sqrt{x-3+\frac{1}{x-2}+\sqrt{2}\cdot\sqrt{x-4+\frac{1}{x-2}}}$. It is easy to get that $f'(x) > 0$ for $x\geq 11$. Then $f(x)$ is an increasing function on $x$ and $f(x)\geq f(11) > 0$. Thus

By a similar discussion as above, we can get the result for the case $s_1+s_2 = 6$ and $s_3 = 3$.

Case 4. $y\ge 1$ and $z = 2$.

Then $x = 0, n = 2y+s_1+s_2$. If $n-2y\ge 11$, then by Lemmas 2.1–2.3, we have

Suppose that $n-2y\le10$. Then $6\leq s_1+s_2\leq 10$. If $s_1+s_2 = 10$, then by Lemmas 2.1–2.3, we have

Similarly, for each $6\leq s_1+s_2\leq 9$, we may also get the result.

Combining Lemmas 3.2 and 3.4–3.7, we get our main result.

Theorem 3.1. Among all trees (except the star) on $n\ge 5$ vertices, $P_5$ is the unique tree with the minimum ABC energy for $n = 5$, $P^*_6$ is the unique tree with the minimum ABC energy for $n = 6$ and $S_n^*$ is the unique tree with the minimum ABC energy for $n\geq 7$.

4.   Conclusions

In this paper, motivated by the unique tree with the minimum ABC energy, we determine the trees with the minimum ABC energy among all trees on $n$ vertices except the star $S_n$.

Acknowledgments

The authors would like to thank anonymous referees for helpful comments and suggestions which improved the original version of the paper. This work was supported by the Natural Science Foundation of Guangdong Province (No.2021A1515010028).

Conflict of interest

The authors declare that they have no competing interests.