Minimum atom-bond sum-connectivity index of trees with a fixed order and/or number of pendent vertices

1.   Introduction

A property of a graph that is preserved by isomorphism is known as a graph invariant ^[1]. The order and degree sequence of a graph are examples of graph invariants. The graph invariants that assume only numerical values are usually referred to as topological indices in the chemical graph theory ^[2].

For evaluating the extent of branching of the carbon-atom skeleton of saturated hydrocarbons, Randić ^[3] devised a topological index and called it as the branching index, which nowadays is known as the connectivity index (also, the Randić index).

The connectivity index of a graph $G$ is the following number:

where $d_v$ and $d_w$ denote the degrees of the vertices $v$ and $w$ of $G$ respectively, and $E(G)$ denotes the set of edges of a graph $G$. It is believed that the connectivity index is the most-studied topological index (in both theoretical and applied aspects) ^[4]. Detail about the study of the connectivity index can be found in the survey papers ^[5,6], books ^[7,8], and related papers cited therein.

Because of the success of the connectivity index, many modified versions of this index have been introduced in the literature. The atom-bond connectivity (ABC) index ^[9,10] and the sum-connectivity (SC) index ^[11] are among the well-studied modified versions of the connectivity index. The ABC and SC indices of a graph are defined as

and

The readers interested in detail about the ABC and SC indices are referred to the survey papers ^[12] and ^[13], respectively.

Using the main idea of the SC index, a modified version of the ABC index was proposed in ^[14] recently and it was referred to as the atom-bond sum-connectivity (ABS) index. The ABS index of a graph $G$ is defined as

Although the ABS index is a special case of a general topological index considered in ^[15], no result reported in ^[15] covers the ABS index. The graphs possessing the maximum/minimum ABS index in the class of all (i) (molecular) trees (ii) general graphs, with a given order, were characterized in ^[14]. Analogous results for unicyclic graphs were reported in ^[16], where the chemical applicability of the ABS index was also investigated.

A vertex of degree one in a tree $T$ is called a pendent vertex and a vertex of degree at least three in $T$ is called a branching vertex. A path $P$ in a tree $T$ connecting a branching vertex and a pendent vertex is called a pendent path, provided that every other vertex (if existing) of $P$ has degree two in $T$. A path $P$ in a tree $T$ is said to be an internal path if it connects two branching vertices and every other vertex (if existing) of $P$ has degree two in $T$. A tree with one non-pendent vertex is called a star. A double star is a tree with exactly two non-pendent vertices. A double star tree with non-pendent vertices $u$ and $v$ is called balanced if $|d_u-d_v|\leq 1$. For a general reference on graph theory, see ^[17].

Ali et al. ^[16] posed a problem asking to determine trees possessing the minimum value of the ABS index among all trees with a fixed number of pendent vertices. The main goal of the present paper is to determine trees possessing the minimum value of the $ABS$ index in two classes of trees. For positive integers $n$ and $p$, $\Gamma_p$ denotes the class of all trees with $p$ pendent vertices and $\Gamma_{n, p}$ denotes the class of all trees of order $n$ and $p$ pendent vertices. In Section 2 we give a complete solution to the problem posed by Ali et al. ^[16], where we show that the star graph $S_{p+1}$ uniquely attains the minimum value of the $ABS$ index in the class $\Gamma_p$. In Section 3 we provide results on trees that minimize the value of the $ABS$ index in $\Gamma_{n, p}$.

2.   Trees with a fixed number of pendent vertices

We will need the next already known result.

Lemma 1. [14, Corollary 8] Let $u$ and $v$ be nonadjacent vertices in a connected graph $G$, then $ABS(G + uv) > ABS(G)$, where $G+uv$ is the graph obtained from $G$ by adding the edge $uv$.

Lemma 2. Let $p\geq2$ be an integer. If $T^{\ast}$ is a tree attaining the minimum value of the $ABS$ index in the class $\Gamma_p$, then $T^{\ast}$ has no vertex of degree $2$.

Proof. Suppose to the contrary that $T^{\ast}$ has at least one vertex of degree $2$. Take $v\in V(T^{\ast})$ such that $N(v) = \{u, w\}$ and $d_u\ge d_w\ge1$. Let $T'$ be the tree formed by removing the vertex $v$ (and its incident edges) and adding the edge $uw$ (see Figure 1). In what follows, by $d_x$ we denote the degree of a vertex $x$ in $T^{\ast}$. Using the definition of the ABS index, we have

a contradiction to the assumption that $T^{\ast}$ attains the minimum value of the ABS index among all trees with $p$ pendent vertices.□

Lemma 3. The function $f$ defined by

with $x\ge y\ge3$, is strictly decreasing on $y$.

Proof. We have

where

Certainly, the function $g$ is strictly increasing on $y$ because $y\ge3$. Hence, $g(y) < g(x+y-2)$ as $x\ge3$. Consequently, Eq (2.1) gives

Since the function $\psi$ defined by

is strictly decreasing for $t > 2$, from (2.2) it follows that $\frac{\partial f}{\partial y} < 0$. □

Lemma 4. Let

and define the function $\psi(x, y;s)$ as

where $x, y\geq 1$ and $s > 0$. Then $\psi(x, y;s)$ is strictly decreasing on $x$ and on $y$.

Proof. Since

it suffices to show the case of $x$. Note that the first partial derivatives of $f$ are calculated as

which are both strictly decreasing in $x$. This implies that

and

Thus $\psi(x, y;s)$ is strictly decreasing on $x$ and on $y$. □

Theorem 1. Let $p\geq 2$ be an integer, then for every $T\in \Gamma_p$,

with equality holds if and only if $T\cong S_{p+1}$.

Proof. Let $T$ be a graph attaining the minimum $ABS$ value among all trees with $p$ pendent vertices. By Lemma 2, $T$ has no vertex of degree $2$. We claim that $T$ has only one vertex of degree greater than $2$. Contrarily, we assume that $T$ contains at least two vertices of degree greater than $2$. Among the vertices of degrees at least $3$, we pick $u, v\in V(T)$ such that $uv\in E(G)$ (Lemma 2 guarantees the existence of the vertices $u$ and $v$ when $T$ has at least one pair of vertices of degrees greater than $2$). Without loss of generality, we suppose that $d_u\ge d_v$. Let $v_1, \cdots, v_{d_v-1}$ be the neighbors of $v$ different from $u$. Construct a new tree $T'$ by dropping the vertex $v$ (and its incident edges) and inserting the edges $v_1u, \cdots, v_{d_v-1}u$, see Figure 2. Certainly, both the trees $T$ and $T'$ have the same number of pendent vertices. However, in the following we show that $ABS(T) > ABS(T')$, which gives a contradiction to the minimality of $ABS(T)$, and hence, $T$ must contain exactly one vertex of degree greater than $2$, as desired.

In what follows, by $d_w$ we denote the degree of a vertex $w$ in $T$. If $u_1, \cdots, u_{d_u-1}$ are the neighbors of $u$ different from $v$, then

By Lemma 4, the following inequalities hold for all $i = 1, ..., d_u-1$ and $j = 1, ..., d_v-1$:

and

Thus, Eq (2.3) yields

Since $d_u\ge d_v$, by Lemma 3, Inequality (2.4) gives

By Lemma 3, the function $g(s)$, which is defined by

with $s\ge3$, is strictly decreasing, and

Therefore, the righthand side of (2.5) is positive for $d_u\ge3$. This completes the proof. □

3.   Trees with a fixed order and pendent vertices

In this section, we characterize trees attaining the minimum value of the ABS index in $\Gamma_{n, p}$, where $p\geq3$ and $n\geq3p-2$.

Lemma 5. If $y$ is a fixed real number greater than or equal to $3$ then the function $f$, defined in Lemma 4, is strictly increasing in $x$.

For a tree $T$, denote by $W_1(T)$ the set of pendent vertices of $T$, $W_2(T) = \cup_{v\in W_1(T)}N(v)$, and $W_3(T) = V(T)\setminus (W_1(T)\cup W_2(T))$. A vertex in $T$ of degree at least three is called a branching vertex. A path is called an internal path, if its end vertices are branching vertices and every other vertex has degree two. A path is called a pendent path if one of the end vertices is pendent and every other vertex has degree two.

Lemma 6. Let $T^{\ast}\in \Gamma_{n, p}$ be attaining minimum $ABS$ value, then every internal path of $T^{\ast}$ has length one.

Proof. For a contradiction, assume $T^{\ast}$ contains an internal path $v = v_0-v_1-v_2-..-v_r = u$ of length $r\geq 2$. Let $w\in W_2(T)$ and let $y$ be a pendent vertex adjacent to $w$. Let $T' = T^{\ast}-\{vv_1, uv_{r-1}\}+\{vu, yv_1\}$. Clearly $T'\in \Gamma_{n, p}$. In what follows, by $d_x$ we denote the degree of a vertex $x$ in $T^{\ast}$. If $r > 2$, then

which yields a contradiction. If $r = 2$, then

Again, this contradicts the minimality of $ABS(T^{\ast})$. Thus $T^{\ast}$ does not have an internal path of length greater than one. □

Lemma 7. Let $T^{\ast}\in \Gamma_{n, p}$ be attaining minimum $ABS$ value, then $d_u\leq d_v$ for every $u\in W_2(T^{\ast})$ and $v\in W_3(T^{\ast})$.

Proof. Let $y$ be a pendent vertex adjacent to $u$ and let $x$ be a non-pendent vertex adjacent to $v$ and not on the $u-v$ path. Let $T' = T^{\ast}-\{xz\mid z\in N(x)\setminus\{v\}\}+\{zy\mid z\in N(x)\setminus\{v\}\}$. In what follows, by $d_x$ we denote the degree of a vertex $x$ in $T^{\ast}$. Clearly, $T'\in \Gamma_{n, p}$, and so $ABS(T')\geq ABS(T^{\ast})$. Thus, we have

Hence, $d_u\leq d_v$. □

Lemma 8. Let $T\in \Gamma_{n, p}$. If $n = 3p-2+t$ for some $t\geq0$, then the following assertions hold.

(i) $d_v = 2$ for all $v\in W_2(T).$

(ii) $\sum_{u\in W_3(T)}d_u = 3p-6+2t.$

Proof. (i) We have $p+\sum_{v\in W_2(T)}d_v+\sum_{u\in W_3(T)}d_u = 6p-6+2t$. Seeking a contradiction, assume $d_{v_0}\geq3$ for some ${v_0}\in W_2(T)$. Let $\beta = min\{d_u\mid u\in W_3(T)\}$, then by Lemma 7, $\beta \geq d_{v_0}\geq 3$. On the other hand, since $d_v\geq 2$ for all $v\in W_2(T)$, we have

Therefore,

a contradiction. Thus, $d_v = 2$ for all $v\in W_2(T)$.

(ii) We conclude from part (i) that $|W_2(T)| = p$, so $p+2p+\sum_{u\in W_3(T)}d_u = 6p-6+2t$, which yields $\sum_{u\in W_3(T)}d_u = 3p-6+2t.$ □

Remark 9. Let $T^{\ast}\in \Gamma_{n, p}$ be a tree attaining minimum $ABS$ value. It results from Lemma 7 that every vertex of $T^{\ast}$ of degree two is on a pendent path. Assume there are two vertices $u, v\in W_3(T^{\ast})$ such that $d_u = d_v = 2$ and $u$ and $v$ do not belong to the same pendent path. Since $v\in W_3(T^{\ast})$ and $d_v = 2$, there are two vertices $x$ and $y$ such that $d_x\leq d_y = 2$ and $v-y-x$. Let $z$ be the pendent vertex at the end of the pendent path containing $u$ and let $T' = T^{\ast}-{xy}+{zy}$. Clearly, $T'\in\Gamma_{n, p}$ and $ABS(T') = ABS(T^{\ast})$. We conclude that it is possible to obtain a tree $T_1^{\ast}\in \Gamma_{n, p}$, in which all vertices of degree two in $W_3(T_1^{\ast})$ belong to the same pendent path, such that $ABS(T_1^{\ast}) = ABS(T^{\ast})$. Moreover, $T^{\ast}$ and $T_1^{\ast}$ have the same maximum degree and the subtrees of $T^{\ast}$ and $T_1^{\ast}$ induced on their sets of branching vertices are isomorphic.

Theorem 2. Let $p\geq3$ and $n\geq 3p-2$. If $T^{\ast}\in \Gamma_{n, p}$ be attaining the minimum $ABS$ value, then the maximum degree of $T^{\ast}$ is three.

Proof. For a contradiction, assume $T^{\ast}$ has a vertex of degree at least $4$. Let $\beta = min\{d_v\mid v\in W_3(T)\}$, then by Lemma 8 (ii), $4+\beta(|W_3(T^{\ast})|-1)\leq 3p-6+2t$. Consequently, $\beta\leq \frac{3p-10+2t}{p-3+t} < 3$, so there is a vertex $u\in W_3(T^{\ast})$ such that $d_u = 2$. We select $u$ so that one of its neighbors is of degree at least three. Now, let $v$ be the farthest vertex from $u$ that of degree at least $4$. Clearly, for each vertex $x\in N(v)$ that does not lie on the $u-v$ path, we have $d_x\leq 3$. In what follows, $d_a$ denotes the degree of a vertex $a$ in $T^{\ast}$.

Case 1. $u\in N(v)$. In this case, choose $y\in N(v)\setminus\{u\}$ and let $T' = T^{\ast}-\{yv\}+\{yu\}$, then

Consider the function

We have

where $A_1 = (s^2+3s-2)(s+3)^2\sqrt{(s+1)(s+2)}$ and $B_1 = (s^2+5s+2)(s+2)^2\sqrt{s(s+3)}$. Since $A^2_1-B_1^2 = -14s^5-137s^4-456s^3-577s^2-140s+108\leq 0$ for $s\geq 1$, we get $h_1'(s)\leq 0$ for $s\geq 1$ and, thus, $h_1(s)$ is strictly decreasing for $s\geq1$. This implies that $ABS(T')-ABS(T^{\ast}) < h_1(d_v)\leq h_1(4) < 0$, a contradiction.

Case 2. $u\not\in N(v)$. Let $w\in N(v)$ and $z\in N(u)$ such that $w$ and $z$ lie on the $u-v$ path. By Case 1, we may suppose that $d_z\geq 3$. Now, we divide this case into four subcases.

Subcase 2.1. $d_v \geq 5$. Let $y\in N(v)\setminus \{w\}$ and take $T' = T^{\ast}-\{yv\}+\{yu\}$, then $T'\in \Gamma_{n, p}$. Moreover, from Lemma 4, it follows that

The function $h_2(s) = 2f(3, 3)-f(3, s)-f(2, 2)-(s-2)(f(3, s)-f(3, s-1))$ is strictly decreasing for $s\geq 1$, and so $ABS(T')-ABS(T^{\ast}) < h_2(5) < 0,$ a contradiction.

Subcase 2.2. $d_v = 4$ and $d_w\leq 3$. Let $y\in N(v)\setminus \{w\}$ and take $T' = T^{\ast}-\{yv\}+\{yu\}$, then $T'\in \Gamma_{n, p}$. Moreover,

a contradiction.

Subcase 2.3. $d_v = 4$ and $d_w\geq 6$. Note that $d_x\leq 4$ for each $x\in N_w\setminus \{w_1, v\}$ because, otherwise, we reach a contradiction as in Subcase 2.1, where $w_1$ is the unique neighbor of $w$ in the $u-v$ path. Let $T' = T^{\ast}-\{vw\}+\{vu\}$, then

The function

is strictly decreasing for $s\geq1$. Thus, $ABS(T')-ABS(T^{\ast}) < h_4(6) < 0$, a contradiction.

Subcase 2.4. $d_v = 4$ and $4\leq d_w\leq 5$. Let $w_1$ be the unique neighbor of $w$ in the $u-v$ path and let $b_1, ..., b_k$ be all vertices in $N(w)\setminus\{w_1\}$ of degree four (with $b_1 = v$), then by Lemma 8 (ii), there are $k+1$ distinct vertices $x_i\in W_3(T^{\ast})$ such that $d_{x_i} = 2$. The vertex $x_{k+1}$ exists because $d_w\geq4$. By Remark 9, we may assume that these vertices form a path $u = x_1-x_2-...-x_k-x_{k+1}$. For each $i = 2, ..., k$, select $c_i\in N(b_i)\setminus\{w\}$ and let $T' = T^{\ast}-(\{c_ib_i, i = 2, ..., k\}\cup\{vw\})+(\{c_ix_i, i = 2, ..., k\}\cup\{vu\})$. Note that since $v$ is closer to $u$ than $c_i$, we have $d_{c_i}\leq 3$. Thus,

Calculations show that the righthand side of this inequality is negative when $d_w\in\{4, 5\}$ and $k\in\{1, ..., d_w\}$. This also yields a contradiction. Therefore, the maximum degree of $T^{\ast}$ is $3$ as desired. □

Now, we are ready to characterize the trees that minimize $ABS$ index in $\Gamma_{n, p}$, where $p\geq3$ and $n\geq3p-2$. For $p\geq3$ and $n = 3p-2+t$ with $t\ge0$, let $\Gamma_{n, p}^* \subset \Gamma_{n, p}$ such that an arbitrary tree $T^{\ast}$ belonging to the class $\Gamma_{n, p}^*$ is defined as follows.

(1) Let $T_0$ be a tree of order $p-2$ and maximum degree $\Delta = min\{p-3, 3\}$.

(2) Construct a tree $T_1$ from $T_0$ by attaching $3-i$ pendent path(s) of length two at each vertex of degree $i$ for $i = 1, 2, 3$. (Note that the order of $T_1$ is $5n_1(T_0)+3n_2(T_0)+n_3(T_0)$, which is equal to $3p-2$ because $n_1(T_0)+n_2(T_0)+n_3(T_0) = p-2$ and $n_1(T_0)+2n_2(T_0)+3n_3(T_0) = 2(p-3)$, where $n_k(T_0)$ denotes the number of vertices of degree $k$ in $T_0$.

(3) Finally, $T^{\ast}$ is obtained from $T_1$ by inserting $t$ vertices of degree two into one or more pendent paths.

Figure 3 gives a tree of the class $\Gamma_{n, p}^*$.

Theorem 3. Let $p\geq3$ and $n = 3p-2+t$ where $t\geq0$. If $T\in \Gamma_{n, p}$, then

with equality if, and only if, $T\in \Gamma_{n, p}^*$.

Proof. Let $T^{\ast}\in \Gamma_{n, p}$ have the minimum $ABS$ value, then by Theorem 2, the maximum degree in $T$ is three. For $i, j = 1, 2, 3$ let $n_{i, j}$ be the number of edges in $T^{\ast}$ that joints vertices of degrees $i$ and $j$. Clearly, $n_{1, 1} = 0$. From Lemma 8 (i), we get $n_{1, 2} = p$ and $n_{1, 3} = 0$. Let $d$ be the number of vertices of degree $3$, then by Lemma 8 (ii), we get $2(p-2+t-d)+3d = 3p-6+2t$. Thus, $d = p-2$. Since $T$ has no internal paths of length more than one, the induced subgraph of $T$ over the set of vertices of degree three is a tree on $p-2$ vertices. Thus, $n_{3, 3} = p-3$. There are $3(p-2)$ edges incident with the vertices of degree $3$. Each one of these edges is either joining two vertices of degree $3$ or a vertex of degree $3$ and a vertex of degree $2$. Thus, we get $n_{2, 3}+2n_{3, 3} = 3(p-2)$ and, hence, $n_{2, 2} = 3(p-2)-2(p-3) = p$. By subtracting the values $n_{1, 2} = p$, $n_{2, 3} = p$, $n_{3, 3} = p-3$ from $n-1 = 3p-3+t$, we get $n_{2, 2} = t$. Thus,

□

Here, we remark that the statements of Lemma 3.11 and Corollary 3.12 in paper ^[18] concerning chemical trees are not complete; these statements should include the condition $n\geq 3p-2$. Indeed, Figure 4 gives the example of (general and chemical) trees with maximum degree $\Delta\geq4$ attaining minimum ABS value in the class $\Gamma_{n, p}$ with $n\leq 3p-3$. Thus, the condition $n\geq 3p-2$ in Theorem 2 and in the aforementioned two results of ^[18] is necessary. The problem of characterizing trees attaining the minimum values of the ABS index in $\Gamma_{n, p}$ under the conditions $p\geq 3$ and $p+1\leq n\leq 3p-3$ is still open (the maximal version of this problem was recently solved in ^[19]). In the remainder of this section, we address this problem. Note that $\Gamma_{p+1, p}$ consists of only one tree, namely, the star tree. The next theorem deals with the case $n = p+2$.

Theorem 4. Let $p\geq 3$, then the minimum $ABS$ index in $\Gamma_{p, p+2}$ is attained uniquely by the balanced double star.

Proof. Let $T^{\ast}\in \Gamma_{p, p+2}$ be attaining minimum $ABS$ index. Assume that $u, v\in V(T^{\ast})$ are the non-pendent vertices with $d_u\geq d_v+2$. Let $w\in N(u)\setminus\{v\}$ and let $T' = T-\{uw\}+\{vw\}$, then

where $g(x) = x(f(1, x+1)-f(1, x))+f(1, x+1)$. The derivative of $g(x)$ is given by

where $A = (x^2+3x+1)(x + 1)^2\sqrt{(x - 1)(x + 2)}$ and $B = (x^2+x-1)(x+2)^2\sqrt{x(x + 1)}$. Since $A^2-B^2 > 0$ for $x\geq 1$, we get that $g(x)$ is decreasing, so $ABS(T')-ABS(T^{\ast}) < 0$, a contradiction. □

4.   Conclusions

We have characterized the unique graph possessing the minimum ABS index in the class of all trees of a fixed number of pendent vertices; the star is the unique extremal graph in the mentioned class of graphs (see Theorem 1). We have also addressed the problem of determining graphs possessing the minimum ABS index in the class of all trees with $n$ vertices and $p$ pendent vertices; such extremal trees have the maximum degree $3$ when $n\ge 3p-2\ge7$, and the balanced double star is the unique such extremal tree for the case $p = n-2$ (see Theorems 2, 3 and 4). Figure 4 gives all the graphs attaining minimum ABS index in the class $\Gamma_{n, p}$ for $p = 4, 5, 6$ and $p+3\leq n \leq 3p-3$. These graphs are obtained by utilizing a computer software. Observe that for every $(n, p)\not\in\{(8, 4), (9, 5), (13, 6)\}$ with $p = 4, 5, 6$ and $p+3\leq n \leq 3p-3$, there is the unique graph attaining minimum ABS index in the class $\Gamma_{n, p}$; however, for every $(n, p)\in\{(8, 4), (9, 5), (13, 6)\}$, there exist exactly two such extremal graphs. From the trees depicted in Figure 4, one may expect some certain structural properties of a tree attaining minimum ABS index in the class $\Gamma_{n, p}$ when $p\ge7$ and $p+3\leq n \leq 3p-3$. However, these trees seem to be insufficient for making some sound conjectures. In the future, it would be interesting to solve the problem of determining graphs possessing the minimum ABS index in the class $\Gamma_{n, p}$ when $p\ge7$ and $p+3\leq n \leq 3p-3$.

Use of AI tools declaration

The authors declare they have not used Artificial Intelligence (AI) tools in the creation of this article.

Acknowledgments

This work is supported by Scientific Research Deanship, University of Ha'il, Saudi Arabia, through project number RG-23 093.

Conflict of interest

The authors declare that they do not have any conflict of interest.