Graphical edge-weight-function indices of trees

1.   Introduction

For foundational concepts in graph theory and chemical graph theory that are utilized in this paper without explicit definitions, we refer the reader to the comprehensive texts such as ^[13,16,28] for general graph theory, and ^[19,48,50] for those specific to chemical graph theory. These references offer detailed explanations and are essential for understanding the fundamental terms used herein.

A graph comprising $n$ vertices is termed an $n$-order graph. The notation $E(G)$ is used to denote the edge set of a graph $G$, while $V(G)$ represents its vertex set. For any vertex $x \in V(G)$, the degree of $x$ is denoted as $d_G(x)$. A vertex with a degree of 1 is specifically termed a pendent vertex. A matching in a graph is defined as a set of edges such that no two edges share a common vertex, ensuring they are pairwise non-adjacent. When a matching consists of exactly $\ell$ edges, it is referred to as an $\ell$-matching. The concept of a maximum matching is one of the central concepts of this study; it is the largest possible matching within a graph, and the number of edges in such a matching is called the matching number of the graph.

A graph invariant is a fundamental characteristic of a graph that remains unchanged under any isomorphism of the graph ^[28]. In the domain of chemical graph theory, the real-valued graph invariants are often referred to as topological indices ^[19,48,50]. The study of topological indices is primarily motivated by their significant utility in predicting various properties of chemical compounds, as demonstrated in numerous studies such as ^{[18,19,27,30,41]}.

Topological indices that are formulated in the following specific form have been categorized as graphical edge-weight-function indices ^[32]:

Here, $\mathfrak{f}$ represents a real-valued symmetric function that is defined on the Cartesian square of the set of all distinct elements within the degree sequence of the graph $G$. These indices have also been investigated under the terminology "bond incident degree indices," as observed in studies such as ^[1,10,46,51]. We remark here that the class of graphical edge-weight-function indices is a subclass of a broader class of particular topological indices known as degree-based topological indices ^[25].

Let us consider a tree graph $T$. The current study is focused on establishing the best possible bounds for $\mathcal{I}_\mathfrak{f}(T)$, expressed in terms of the order of $T$ and a parameter $\mathfrak{p}$, subject to specific constraints applied to the function $\mathfrak{f}$. The parameter $\mathfrak{p}$ could be one of the following: (ⅰ) the matching number, (ⅱ) the number of pendent vertices, and (ⅲ) the maximum degree. Furthermore, all tree graphs that attain these bounds are thoroughly characterized. The constraints considered here for the function $\mathfrak{f}$ are satisfied by a considerable number of existing topological indices. To illustrate the applicability of the obtained results, we focus on the Euler-Sombor (ES) index ^[45]. In this context, the index $\mathcal{I}_\mathfrak{f}$ corresponds to the ES index when the function $\mathfrak{f}$ is defined as $\mathfrak{f}(a_1, a_2) = \sqrt{a_1^2+a_2^2+a_1a_2}$. Hence,

2.   Preliminaries

This section consists of the foundational definitions, notations, and a selection of preliminary lemmas that are needed for the discussions and proofs in the subsequent sections of this paper.

We denote the path graph with $n$ vertices as $P_n$ and the star graph with $n$ vertices as $S_n$. Given a subset $S \subset V(G)$, the graph obtained by removing all the vertices of $S$ and their corresponding incident edges from $G$ is denoted by $G-S$. In the case when $S$ consists of a single vertex, say $S = \{x\}$, the notation can be simplified to $G-x$ for ease of reference.

An edge incident to a pendent vertex, i.e., a vertex of degree 1, is known as a pendent edge. The maximum degree of a graph $G$ is denoted by $\triangle$. A non-trivial path $P:z_1z_2\dots z_k$ in a graph $G$ is said to be a pendent path if $\min\{d_G(z_1), d_G(z_k)\} = 1$, $\max\{d_G(z_1), d_G(z_k)\}\ge3$ and $d_G(z_i)$ when $2\le i\le k-1$.

The open neighborhood of a vertex $x\in V(G)$, denoted by $N_{G}(x)$, is defined as the set of vertices in $G$ that are adjacent to $x$. These vertices are referred to as the neighbors of $x$ within the graph $G$.

Lemma 2.1. Define a function $\mathfrak{f}$ by $\mathfrak{f}(r_1, r_2) = \sqrt{r_1^2+r_2^2+r_1r_2}$ on the Cartesian square of the set of positive real numbers. Define $\vartheta(r_1, r_2) = \mathfrak{f}(r_1, r_2)-\mathfrak{f}(r_1-1, r_2)$ for $r_1 > 1$ and $r_2 > 0$. Then, for $i\in\{1, 2\}$,

Proof. We only prove the last two inequalities. Since the function $\frac{\partial \mathfrak{f}}{\partial r_1}$ (the partial derivative of $\mathfrak{f}$ with respect to $r_1$) is strictly increasing in $r_1$ and the function $\frac{\partial \mathfrak{f}}{\partial r_2}$ is strictly decreasing in $r_1$, we have

Lemma 2.2. Consider the function $\mathfrak{f}$ defined in Lemma 2.1. The function $\Phi$ defined as

is strictly increasing.

Proof. By the definition of $\vartheta$ defined in Lemma 2.1, we have

Now, because of Lemma 2.1, the derivative function $\Phi'$ of $\Phi$ satisfies the following inequality chain:

3.   Fixed-order trees with a given matching number

For $n\ge 2\ell\ge 2$, let $T_{n, \ell}$ denote the graph formed by subdividing $\ell-1$ pendent edges of the $(n-\ell+1)$-order star graph $S_{n-\ell+1}$ (see Figure 1). Certainly, the graph $T_{n, \ell}$ has a matching number $\ell$.

For a matching $U$ in a graph $G$, a vertex $x\in V(G)$ incident with a member of $U$ is known as $U$-saturated; particularly, if all the vertices of $G$ are $U$-saturated, then $U$ is called a perfect matching. We remark that the graph $T_{2\ell, \ell}$ has a perfect matching for every $\ell\ge1$.

Before proving the first main result of the current section, we recall the following known result:

Lemma 3.1. (See Lemmas 2.6 and 2.7 in ^[15]) Let $G$ be an $n$-order tree.

(i) If $G$ has a matching number $\ell$ such that $2\ell = n\ge4$, then there is a pendent edge in $T$ incident with a vertex having degree $2$.

(ii) If $2\le2\ell < n$ and if $G$ contains at least one $\ell$-matching, then $G$ has an $\ell$-matching $U$ and a pendent vertex $w$ such that $w$ is not incident with any member of $U$.

Theorem 3.1. Let $\mathfrak{f}$ be a real-valued symmetric function defined on the Cartesian square of the set of those real numbers that are greater than or equal to 1. Let $t\ge2$ and $r\ge1$. If

(i) the function $g$ defined as $g(t, r) = \mathfrak{f}(t, r) - \mathfrak{f}(t-1, r)$, is strictly decreasing in $r$, and

(ii) the function $\hbar$ defined as $\hbar(t) = \mathfrak{f}(t, 2) + \mathfrak{f}(t, 1) - \mathfrak{f}(t-1, 1) + (t-2) \left[\mathfrak{f}(t, 2) - \mathfrak{f}(t-1, 2)\right],$ is strictly increasing,

then the inequality

is valid for every $2\ell$-order tree $G$ with a matching number $\ell(\ge1)$. The sufficient and necessary condition for the equality in (3.1) to hold is that $G \cong T_{2\ell, \ell}$ (see Figure 1).

Proof. Set $\varphi(\ell) = \mathfrak{f}(\ell, 1) +(\ell-1)\left[\mathfrak{f}(\ell, 2)+\mathfrak{f}(1, 2)\right]$. The induction on $\ell$ will be used to prove the theorem. The desired conclusion holds for $\ell\in\{1, 2\}$ because $G \cong P_2$ when $\ell = 1$ and $G \cong P_4$ when $\ell = 2$. This starts the induction. Now, we assume that $\ell\ge3$ and that the theorem holds for all $2(\ell-1)$-order trees with a matching number $\ell-1$. Next, we consider a $2\ell$-order tree $G$ with a matching number $\ell(\ge3)$. Let $U$ be the maximum matching of $G$. By using Lemma 3.1(ⅰ), we pick a pendent vertex $u\in V(G)$ adjacent to a vertex $v$ of degree $2$. Clearly, $uv \in U$. Since the tree $G - \{u, v\}$ has order $2(\ell-1)$ and has the matching number $\ell-1$, by inductive hypothesis it holds that

with equality iff $G \cong T_{2(\ell-1), \ell-1}$. Let $w$ be the neighbor of $v$ different from $u$. Note that the vertex $w$ has at most one pendent neighbor and that $2\ell\ge6$, and hence we have

Let $N_G(w) = \{w_0( = v), w_1, \cdots, w_{t-1}\}$. Assume that the vertices $w_{r+1}$, $w_{r+2}$, $\cdots$, $w_{t-1}$ are non-pendent, where $r = 0$ or $1$, and $d_G(w_1) = 1$ if $r = 1$. By condition (ⅰ), we have

Since $t\ge2$, again by condition (ⅰ), we have

and hence (3.3) yields

Now, by condition (ii), we have

From (3.2), (3.4), and (3.5), it follows that $\mathcal{I}_\mathfrak{f}(G)\le \varphi(\ell)$ with equality iff the equalities in (3.2)–(3.5) hold; that is, iff $G-\{u, v\} \cong T_{2(\ell-1), \ell-1}$, $d_G(w_{r+1}) = \cdots = d_G(w_{t-1}) = 2$, $r = 1$ and $t = \ell$. Thus, $\mathcal{I}_\mathfrak{f}(G)\le \varphi(\ell)$ with equality iff $G \cong T_{2\ell, \ell}$. This completes the induction and thence the proof.

The next result's proof is completely analogous to that of Theorem 3.1 and thus we omit it.

Theorem 3.2. Let $\mathfrak{f}$ be a real-valued symmetric function defined on the Cartesian square of the set of those real numbers that are greater than or equal to 1. Let $t\ge2$ and $r\ge1$. If

(i) the function $g$ defined as $g(t, r) = \mathfrak{f}(t, r) - \mathfrak{f}(t-1, r)$, is strictly increasing in $r$, and

(ii) the function $\hbar$ defined as $\hbar(t) = \mathfrak{f}(t, 2) + \mathfrak{f}(t, 1) - \mathfrak{f}(t-1, 1) + (t-2) \left[\mathfrak{f}(t, 2) - \mathfrak{f}(t-1, 2)\right],$ is strictly decreasing,

then the inequality

is valid for every $2\ell$-order tree $G$ with a matching number $\ell(\ge1)$. The sufficient and necessary condition for the equality in (3.6) to hold is that $G \cong T_{2\ell, \ell}$ (see Figure 1).

Theorem 3.3. Let $\mathfrak{f}$ be a real-valued symmetric function defined on the Cartesian square of the set of those real numbers that are greater than or equal to 1. Let $t_1\ge2$ and $t_2\ge1$. If

(i) the function $g$ defined as $g(t_1, t_2) = \mathfrak{f}(t_1, t_2) - \mathfrak{f}(t_1-1, t_2)$, is strictly decreasing in $t_2$,

(ii) the function $\hbar$ defined as $\hbar(t_1) = \mathfrak{f}(t_1, 2) + \mathfrak{f}(t_1, 1) - \mathfrak{f}(t_1-1, 1) + (t_1-2) \left[\mathfrak{f}(t_1, 2) - \mathfrak{f}(t_1-1, 2)\right],$ is strictly increasing, and

(iii) the function $\phi$ defined as $\phi(t_1, t_2) = \mathfrak{f}(t_1, 1)+(t_2-1) \Big(\mathfrak{f}(t_1, 1)-\mathfrak{f}(t_1-1, 1)\Big)$+$(t_1-t_2) \Big(\mathfrak{f}(t_1, 2)-\mathfrak{f}(t_1-1, 2)\Big)$, is strictly increasing in $t_1$ for $t_1\ge t_2+1$,

then the inequality

is valid for every $n$-order tree $G$ with a matching number $\ell(\ge1)$. The sufficient and necessary condition for the equality in (3.7) to hold is that $G \cong T_{n, \ell}$ (see Figure 1).

Proof. For the case when $\ell = 1$, the theorem obviously holds. In what follows, assume that $\ell\ge2$. Take

We prove the result by induction on $n$. If $n = 2\ell$, then the result follows from Theorem 3.1. Suppose that $G$ is an $n$-order tree having matching number $\ell$ such that $n > 2\ell$, provided that the result holds for every $(n-1)$-order tree with the matching number $\ell$. By Lemma 3.1(ⅱ), $G$ has an $\ell$-matching $M$ and a pendent vertex $u$ such that $u$ is not incident with any member of $M$, which implies that $G - u$ is an $(n-1)$-order tree having matching number $\ell$. Thus, by the inductive hypothesis, we have

with equality iff $G\cong T_{n-1, \ell}$. Let $v$ be the unique neighbor of $u$. Since $uv\not\in M$ and because $M$ is a maximum matching in $G$, $M$ must contain an edge incident with $v$. Thereby, the number of those edges incident with $v$ that do not belong to $M$ is $d_G(v) - 1$, which implies that $d_G(v) - 1 \le n-1-|M|$, that is, $d_G(v) \le n- \ell$. Let $r$ be the number of pendent neighbors of $v$ in $G$. Certainly, $1 \le r \le d_G(v) - 1$. Since at least $r-1$ pendent neighbors of $v$ are $M$-unsaturated and the number of $M$-unsaturated vertices of $G$ is $n-2|M|$, we have $r -1\le n - 2|M|$, which implies that $r\le n-2\ell+1$, i.e., the vertex $v$ has at most $n - 2\ell+1$ pendent neighbors. Let $N_G(v) = \{v_1 ( = u), v_2, \cdots, v_r, v_{r+1}, \cdots, v_{s}\}$, where the vertices $v_1, \cdots, v_{r}$ are pendent and the vertices $v_{r+1}, \cdots, v_{s}$ are non-pendent. By condition (ⅰ), we have

Since $r+1\le s\le n-\ell$, by condition (ⅲ), the inequality (3.9) yields

Since $n > 2\ell\ge4$ (which implies that $n-\ell > 2$), by condition (ⅰ), we have

and hence, because of the inequality $r\le n-2\ell+1$, the inequality (3.10) gives

Now, from (3.8) and (3.11), it follows that $\mathcal{I}_\mathfrak{f}(G) \le \Psi(n, \ell)$. The equation $\mathcal{I}_\mathfrak{f}(G) = \Psi(n, \ell)$ holds iff all equalities in (3.8)–(3.11) hold; that is, iff $G-u\cong T_{n-1, \ell}$, $d_G(v_{r+1}) = \cdots = d_G(v_{s}) = 2$, $s = n-\ell$ and $r = n-2\ell+1$. In other words, the equation $\mathcal{I}_\mathfrak{f}(G) = \Psi(n, \ell)$ holds iff $G\cong T_{n, \ell}$.

Since the next result's proof (which uses Theorem 3.2) is totally analogous to that of Theorem 3.3, we omit it.

Theorem 3.4. Let $\mathfrak{f}$ be a real-valued symmetric function defined on the Cartesian square of the set of those real numbers that are greater than or equal to 1. Let $t_1\ge2$ and $t_2\ge1$. If

(i) the function $g$ defined as $g(t_1, t_2) = \mathfrak{f}(t_1, t_2) - \mathfrak{f}(t_1-1, t_2)$, is strictly increasing in $t_2$,

(ii) the function $\hbar$ defined as $\hbar(t_1) = \mathfrak{f}(t_1, 2) + \mathfrak{f}(t_1, 1) - \mathfrak{f}(t_1-1, 1) + (t_1-2) \left[\mathfrak{f}(t_1, 2) - \mathfrak{f}(t_1-1, 2)\right],$ is strictly decreasing, and

(iii) the function $\phi$ defined as $\phi(t_1, t_2) = \mathfrak{f}(t_1, 1)+(t_2-1) \Big(\mathfrak{f}(t_1, 1)-\mathfrak{f}(t_1-1, 1)\Big)$+$(t_1-t_2) \Big(\mathfrak{f}(t_1, 2)-\mathfrak{f}(t_1-1, 2)\Big)$, is strictly decreasing in $t_1$ for $t_1\ge t_2+1$,

then the inequality

is valid for every $n$-order tree $G$ with a matching number $\ell(\ge1)$. The sufficient and necessary condition for the equality in (3.12) to hold is that $G \cong T_{n, \ell}$ (see Figure 1).

Theorem 3.3 yields the next result about the ES index (whose definition is given in the introduction section).

Corollary 3.1. Let $G$ be an $n$-order tree with a matching number $\ell(\ge1)$, where $n\ge 2\ell$. Then

with equality iff $G\cong T_{n, \ell}$.

Proof. We recall that $\mathcal{I}_\mathfrak{f}$ gives the ES index if we take $\mathfrak{f}(a_1, a_2) = \sqrt{a_1^2+a_2^2+a_1a_2}$. By Lemmas 2.1 and 2.2, all the conditions of Theorem 3.3 are satisfied for $\mathfrak{f}$. Hence, the required conclusion is obtained from Theorem 3.3.

The topological index $\mathcal{I}_\mathfrak{f}$ corresponds to the harmonic index ^[11,23] or the Randić index ^[37,39,43] or the sum-connectivity index ^[11,54], or the AG (arithmetic-geometric) index (for example, see ^[52]), or the MMR (modified misbalance rodeg) index ^[36], or the SDD (symmetric division deg) index ^[9,49], or the sigma index ^[3,24], or the RSO (Reduced-Sombor) index ^[26] if one takes $\mathfrak{f}(a_1, a_2) = 2(a_1+a_2)^{-1}$ or $\mathfrak{f}(a_1, a_2) = (a_1a_2)^{-1/2}$ or $\mathfrak{f}(a_1, a_2) = (a_1+a_2)^{-1/2}$, or $\mathfrak{f}(a_1, a_2) = (2\sqrt{a_1a_2}\, )^{-1}(a_1+a_2)$, or $\mathfrak{f}(a_1, a_2) = (\sqrt{a_1}-\sqrt{a_2})^{2}$, or $\mathfrak{f}(a_1, a_2) = (a_1a_2)^{-1}(a_1^2+a_2^2)$, or $\mathfrak{f}(a_1, a_2) = (a_1-a_2)^{2}$, or $\mathfrak{f}(a_1, a_2) = \sqrt{(a_1-1)^2+(a_2-1)^2}$, respectively.

Remark 3.1. We have verified that all the conditions of Theorem 3.3 are satisfied for the functions associated with the AG, MMR, SDD, sigma, and RSO indices. For the RSO index, we verified that the inequality $g(t_1, t_2) < g(t_1, 1)$ holds for $t_1\ge2$ and $t_2 > 1$, the inequality $\hbar(t_1) > \hbar(2)$ holds for $t_1 > 2$, and the inequality $\phi(t_1, t_2) > \phi(2, t_2)$ holds for $t_1\ge t_2+1\ge2$ and $t_1 > 2$; then, we used the tool of differentiation to verify the remaining cases (concerning the RSO index). Hence, Theorem 3.3 covers these five indices. The corresponding result concerning the SDD index is already known (see ^[21]); however, the corresponding results concerning the AG, sigma, RSO, and MMR indices are new (to the best of the authors' knowledge).

Remark 3.2. We have verified that all the conditions of Theorem 3.4 are satisfied for the functions associated with the harmonic, Randić, and sum-connectivity indices. Hence, Theorem 3.4 covers these three indices. The special cases of Theorem 3.4 corresponding to these three indices are already known in the literature; see ^[22,34,35]. Hence, Theorem 3.4 generalizes several existing results.

Remark 3.3. Since the sum of the independence number and matching number of any $n$-order tree (or more generally, $n$-order bipartite graph) is $n$, Theorems 3.3 and 3.4 directly give bounds for $n$-order trees with a given independence number. Therefore, these two theorems extend the recent study ^[46].

Remark 3.4. The topological index $\mathcal{I}_\mathfrak{f}$ corresponds to the Sombor (SO) index ^[26,33,42] when one takes $\mathfrak{f}(a_1, a_2) = \sqrt{a_1^2+a_2^2}$. In Corollary 3.1, we have seen that Theorem 3.3 directly provides an upper bound on the ES index. Here, we remark that this theorem also implies that the inequality (3.7) is valid for the SO index because it can be easily seen that Lemmas 2.1 and 2.2 also hold for the function associated with the SO index. This special case of Theorem 3.3 concerning the SO index is already known; see ^[17,53].

Remark 3.5. The topological index $\mathcal{I}_\mathfrak{f}$ corresponds to the first Zagreb index or the second Zagreb index (for example, see ^[12,14]), if one takes $\mathfrak{f}(a_1, a_2) = a_1+a_2$ or $\mathfrak{f}(a_1, a_2) = a_1a_2$, respectively. One of the referees of the present paper asked to check whether Theorem 3.3 or Theorem 3.4 is applicable to the Randić index and the Zagreb indices. We have already seen in Remark 3.2 that Theorem 3.4 covers Randić index. On the other hand, although neither of the aforementioned two theorems is applicable to either of the Zagreb indices, the conclusion of Theorem 3.3 remains true for these Zagreb indices; see ^[31,46,47]. Therefore, it would be interesting to modify the conditions of Theorem 3.3 in such a way that it covers additional indices, including the Zagreb indices.

4.   Fixed-order trees with a given number of pendent vertices

For $2\le p\le n-1$, let $P_{n, p}$ denote the tree obtained from the $(n-p+1)$-order path $P_{n-p+1}$ by attaching $p-1$ pendent vertices to exactly one of the pendent vertices of $P_{n-p+1}$ (see Figure 2).

Theorem 4.1. Let $\mathfrak{f}$ be a real-valued symmetric function defined on the Cartesian square of the set of those real numbers that are greater than or equal to 1. Let $t\ge2$ and $r\ge1$. If

(i) the function $g$ defined as $g(t, r) = \mathfrak{f}(t, r) - \mathfrak{f}(t-1, r)$, is strictly decreasing in $r$, and

(ii) the function $\hbar$ defined as $\hbar(t) = \mathfrak{f}(t, 1) +(t-2)\left(\mathfrak{f}(t, 1)-\mathfrak{f}(t-1, 1)\right) +\left(\mathfrak{f}(t, 2)-\mathfrak{f}(t-1, 2)\right)$, is strictly increasing,

then the inequality

is valid for every $n$-order tree $G$ with $p$ pendent vertices, provided that $2\le p \le n-2$. The sufficient and necessary condition for the equality in (4.1) to hold is that $G \cong P_{n, p}$ (see Figure 2).

Proof. We use induction on $n$ to prove the result. If $n\in\{4, 5\}$ then $G\cong P_{n, p}$. Next, suppose that $n > 5$. Assume that the theorem holds for all $(n-1)$-order trees with $p'$ pendent vertices such that $2 \le p' \leq (n-1)-2$.

Now, we assume that $G$ has $n$ order and $p$ pendent vertices such that $2 \leq p \leq n-2$. Consider a pendent edge $xy\in E(G)$ with $d_G(x) > 1$.

Case 1. The degree of $x$ in $G$ is at least 3.

Take $N_G(x): = \{x_1, x_2, \cdots, x_{d_G(x)-1}\}\setminus\{y\}$ with $d_G(x_1)\ge d_G(x_2)\ge \cdots \ge d_G(x_{d_G(x)-1})$. Note that $d_G(x_1)\ge2$ because $G$ is different from the star $S_n$. In what follows, we also take $d_G(x) = \jmath$. By using condition (ⅰ), we have

with equality iff $d_G(x_1) = 2$ and $d_G(x_2) = \cdots = d_G(x_{\jmath-1}) = 1$. Since the maximum degree of $G$ cannot be greater than $p$, we have $\jmath\le p$, and hence, by using condition (ⅱ) in (4.2), we obtain

with equality iff $d_G(x_1) = 2$, $d_G(x_2) = \cdots = d_G(x_{\jmath-1}) = 1$ and $\jmath = p$. In the considered case, we always have $p\ge3$. Also, the graph $G-y$ contains exactly $p-1$ pendent vertices. Since $2\le p-1\le (n-1)-2$, we can apply the inductive hypothesis, and hence we have

with equality iff $G-y\cong P_{n-1, p-1}$. Now, (4.1) follows from (4.3) and (4.4).

Case 2. The vertex $x$ has degree 2 in $G$.

For $p = n-2$, we have $G\cong P_{p+2, p}$. In what follows, suppose that $p < n-2$. Let $x'\in N_G(x)\setminus \{y\}$. Since $n\ge6$, the vertex $x'$ cannot be pendent, and hence, by condition (ⅰ), we have

where the right equality holds iff $d_{G}(x') = 2$. In the considered case, $G-y$ contains exactly $p$ pendent vertices. Since $2\le p \leq (n-1)-2$, we can apply the inductive hypothesis, and hence, we have

Certainly, the equation

holds iff $d_{G}(x') = 2$ and $G-y\cong P_{n-1, p}$; that is, iff $G\cong P_{n, p}$.

As the next result's proof is totally similar to that of Theorem 4.1, we omit it.

Theorem 4.2. Let $\mathfrak{f}$ be a real-valued symmetric function defined on the Cartesian square of the set of those real numbers that are greater than or equal to 1. Let $t\ge2$ and $r\ge1$. If

(i) the function $g$ defined as $g(t, r) = \mathfrak{f}(t, r) - \mathfrak{f}(t-1, r)$, is strictly increasing in $r$, and

(ii) the function $\hbar$ defined as $\hbar(t) = \mathfrak{f}(t, 1) +(t-2)\left(\mathfrak{f}(t, 1)-\mathfrak{f}(t-1, 1)\right) +\left(\mathfrak{f}(t, 2)-\mathfrak{f}(t-1, 2)\right)$, is strictly decreasing,

then the inequality

is valid for every $n$-order tree $G$ with $p$ pendent vertices, provided that $2\le p \le n-2$. The sufficient and necessary condition for the equality in (4.5) to hold is that $G \cong P_{n, p}$ (see Figure 2).

From Theorem 4.1, we have the next result about the ES index.

Corollary 4.1. If $G$ is an $n$-order tree possessing $p$ pendent vertices, provided that the inequality $2\le p\le n-2$ holds, then

with equality iff $G\cong P_{n, p}$ (see Figure 2).

Proof. By Lemma 2.1, all the hypotheses of Theorem 4.1 hold for $\mathfrak{f}(a_1, a_2) = \sqrt{a_1^2+a_2^2+a_1a_2}$. Therefore, we obtain the required conclusion from Theorem 4.1.

The index $\mathcal{I}_\mathfrak{f}$ corresponds to the ABC (atom-bond connectivity) index ^[4,20,40], or the ABS (atom-bond sum-connectivity) index ^[6,8,38], or the MSDD (modified symmetric division deg) index ^[2], if one takes $\mathfrak{f}(a_1, a_2) = \sqrt{(a_1a_2)^{-1}(a_1+a_2-2)}$, or $\mathfrak{f}(a_1, a_2) = \sqrt{(a_1+a_2)^{-1}(a_1+a_2-2)}$, or $\mathfrak{f}(a_1, a_2) = \sqrt{(2a_1a_2)^{-1}(a_1^2+a_2^2)}$, respectively.

Remark 4.1. Since the constraints of Theorem 4.1 are satisfied for each of the functions associated with the following topological indices, Theorem 4.1 holds for each of these topological indices: ABC index, ABS index, AG index, MMR index, MSDD index, SDD index, sigma index, SO index, RSO index (for the definitions of AG, MMR, SDD, sigma, and RSO indices, see the paragraph right before Remark 3.1, while the definition of SO index is given in Remark 3.4).

Remark 4.2. Since the constraints of Theorem 4.2 are satisfied for each of the functions associated with the following topological indices, Theorem 4.2 covers each of these three topological indices: Randić index, harmonic index, sum-connectivity index (the definitions of these three indices are given in the paragraph right before Remark 3.1.)

5.   Fixed-order trees with a given maximum degree

In this section, we attempt the problem of characterizing the graphs possessing the extremum values of $\mathcal{I}_\mathfrak{f}$ among all fixed-order trees with a given maximum degree. We start with the following lemma:

Lemma 5.1. Let $\mathfrak{f}$ be a real-valued symmetric function defined on the Cartesian square of the set of those real numbers that are greater than or equal to 1, such that

(i) $\mathfrak{f}$ is strictly increasing in one variable (and hence in both variables because of symmetry),

(ii) the inequality $\mathfrak{f}(x, 1)-\mathfrak{f}(2, 2) > 0$ holds for $x\ge3$, and

(iii) the inequality $(x-1)[\mathfrak{f}(x, 2)-\mathfrak{f}(2, 2)]+ (x-2)[\mathfrak{f}(1, 2)-\mathfrak{f}(2, 2)] > 0$ holds for $x\ge3$.

Over the class of all $n$-order trees with maximum degree $\triangle$, let $G$ be a tree possessing the minimum value of $\mathcal{I}_\mathfrak{f}$, where $3 \leq \triangle \leq n-1$. Then, $G$ has no more than one vertex of degree at least $3$.

Proof. Contrarily, suppose that $G$ has more than one vertex of degree at least 3. We pick $z\in V(G)$ such that $d_G(z) = \triangle$. Among those vertices of $G$ that have degrees at least $3$, we choose $y$ such that the distance $d_G(y, z)$ between them is the maximum. Take $d_{G}(y) = \xi$. Certainly, $\xi\geq 3$ and $y \neq z$. Let $N_G(y) = \{y_1, y_2, \dots, y_\xi\}$, where $y_\xi$ lies on the unique $y-z$ path and it is possible that $y_\xi = z$. We observe that $y$ is the common end vertex of $\xi-1$ pendent paths, and hence $d_{G}(y_i) \in \{1, 2\}$ for every $i\in\{1, 2, \ldots, \xi-1\}$.

Case 1. $d_{G}(y_i) = 1$ for every $i\in\{1, 2, \ldots, \xi-1\}$.

Define a new graph $G^\star$ such that $V(G^\star) = V(G)$ and

Note that the maximum degree of $G^\star$ is $\triangle$. By conditions (ⅰ) and (ⅱ), we have

a contradiction against the assumption that $\mathcal{I}_\mathfrak{f}(G)$ is minimum.

Case 2. $d_{G}(y_i) = 1$ and $d_{G}(y_j) = 2$ for some $i, j\in\{1, 2, \ldots, \xi-1\}$.

Without loss of generality, suppose $d_{G}(y_1) = 1$ and $d_{G}(y_2) = 2$. Let $x\in V(G)$ be the pendent vertex lying on the pendent path containing $y_2$. Define $G^{\star\star}$ such that $V(G^{\star\star}) = V(G)$ and

Again, by conditions (ⅰ) and (ⅱ), we have

a contradiction.

Case 3. $d_{G}(y_i) = 2$ for every $i\in\{1, 2, \ldots, \xi-1\}$.

Let $r$ be the sum of the lengths of the $\xi-1$ pendent paths (in $G$) having $y$ as the common end vertex. Let $G'$ denote the graph generated from $G$ by replacing these $x-1$ pendent paths with exactly one path of length $r$, attached at the vertex $y$. Certainly, the order and the maximum degree of $G'$ are $n$ and $\triangle$, respectively. Also, we note that $d_{G'}(y) = 2$. By condition (ⅲ), we obtain

a contradiction again.

The topological index $\mathcal{I}_\mathfrak{f}$ corresponds to the ESO (elliptic-Sombor) index ^[29,44], or the ZSO (Zagreb-Sombor) index ^[7], or the ISI (inverse sum indeg) index ^[5,49], if one takes $\mathfrak{f}(a_1, a_2) = (a_1+a_2)\sqrt{a_1^2+a_2^2}$, or $\mathfrak{f}(a_1, a_2) = (a_1a_2)\sqrt{a_1^2+a_2^2}$, or $\mathfrak{f}(a_1, a_2) = (a_1+a_2)^{-1}a_1a_2$, respectively.

Remark 5.1. Since the hypotheses of Lemma 5.1 are satisfied for each of the functions associated with the following indices, Lemma 5.1 holds for these indices: ESO index, ZSO index, ISI index, first Zagreb index, and second Zagreb index (the definitions of the first and second Zagreb indices are given in Remark 3.5).

The next lemma's proof is totally analogous to that of Lemma 5.1, and therefore we omit it.

Lemma 5.2. Let $\mathfrak{f}$ be a real-valued symmetric function defined on the Cartesian square of the set of those real numbers that are greater than or equal to 1, such that

(i) $\mathfrak{f}$ is strictly decreasing in one variable (and hence in both variables because of symmetry),

(ii) the inequality $\mathfrak{f}(x, 1)-\mathfrak{f}(2, 2) < 0$ holds for $x\ge3$, and

(iii) the inequality $(x-1)[\mathfrak{f}(x, 2)-\mathfrak{f}(2, 2)]+ (x-2)[\mathfrak{f}(1, 2)-\mathfrak{f}(2, 2)] < 0$ holds for $x\ge3$.

Over the class of all $n$-order trees with maximum degree $\triangle$, let $G$ be a tree possessing the maximum value of $\mathcal{I}_\mathfrak{f}$, where $3 \leq \triangle \leq n-1$. Then $G$ has no more than one vertex of degree at least $3$.

For $\lfloor \frac{n-1}{2} \rfloor \leq \triangle \leq n-1$ with $\triangle \geq 3$, denote by $S'_{n, \triangle}$ the $n$-order tree having exactly one vertex of degree greater than 2, which is the common end vertex of $n-\triangle-1$ pendent paths of length $2$ and $2\triangle-n+1$ pendent paths of length $1$. For $3 \leq \triangle \leq \lfloor \frac{n-1}{2} \rfloor$, denote by $S_{n, \triangle}^\star$ the $n$-order tree having exactly one vertex of degree greater than 2, which is the common end vertex of $\triangle$ pendent paths of length at least $2$. The graphs $S'_{n, \triangle}$ and $S_{n, \triangle}^\star$ are depicted in Figure 3. We remark here that the graph $S'_{n, \triangle}$ is similar to the one shown in Figure 1.

Theorem 5.1. Let $\mathfrak{f}$ be a real-valued symmetric function defined on the Cartesian square of the set of those real numbers that are greater than or equal to 1, such that

(i) $\mathfrak{f}$ is strictly increasing in one variable (and hence in both variables because of symmetry),

(ii) the inequality $\mathfrak{f}(x, 1)-\mathfrak{f}(2, 2) > 0$ holds for $x\ge3$,

(iii) the inequality $(x-1)[\mathfrak{f}(x, 2)-\mathfrak{f}(2, 2)]+ (x-2)[\mathfrak{f}(1, 2)-\mathfrak{f}(2, 2)] > 0$ holds for $x\ge3$, and

(iv) the inequality $\mathfrak{f}(x, 1)-\mathfrak{f}(x, 2) + \mathfrak{f}(2, 2) - \mathfrak{f}(1, 2) > 0$ holds for $x\ge3$.

Let $G$ be an $n$-order tree of maximum degree $\triangle$, where $3 \le \triangle \le n-1$.

(a) If $\lceil \frac{n-1}{2} \rceil \leq \triangle \leq n-1$, then

with equality iff $G\cong S'_{n, \triangle}$ (see Figure 3).

(b) If $3 \leq \triangle \leq \lfloor \frac{n-1}{2} \rfloor$, then

with equality iff $G\cong S_{n, \triangle}^\star$ (see Figure 3).

Proof. Over the class of all $n$-order trees with maximum degree $\triangle$, let $G^*$ be a tree possessing the minimum value of $\mathcal{I}_\mathfrak{f}$, where $3 \leq \triangle \leq n-1$. Then,

By Lemma 5.1, $G^*$ has no more than one vertex of degree at least $3$. Let $z\in V(G^*)$ be the unique vertex of maximum degree $\triangle$. Let $Z_1, Z_2, \dots, Z_\triangle$ be the pendent paths (in $G^*$) having the common vertex $z$. For $1\le i \le \triangle$, let $|Z_i|$ denote the length of the path $Z_i$.

If $|Z_i| = 1$ and $|Z_j| = t\ge3$ for some $i, j\in \{1, 2, \dots, \triangle\}$, then by condition (iv) the new graph $G^{**}$ constructed from $G^{*}$ by replacing $Z_i$ and $Z_j$ with pendent paths $Z_i'$ and $Z_j'$ (having common end vertex $z$) of lengths $2$ and $t-1$, respectively, satisfies

which is a contradiction to the definition of $G^{*}$. Therefore, we must have either $|Z_i|\ge2$ for every $i\in \{1, 2, \dots, \triangle\}$, or $|Z_i|\le 2$ for every $i\in \{1, 2, \dots, \triangle\}$.

(a) Since $\lceil \frac{n-1}{2} \rceil \leq \triangle \leq n-1$, it holds that $n\leq 2\triangle+1$. We observe that $|Z_i|\le 2$ for every $i\in \{1, 2, \dots, \triangle\}$; otherwise, if $|Z_j|\ge 3$ for some $j\in \{1, 2, \dots, \triangle\}$ then $|Z_i|\ge2$ for every $i\in \{1, 2, \dots, \triangle\}\setminus \{j\}$, and hence $G^*$ would then have at least $2\triangle+2$ vertices, which contradicts $n\leq 2\triangle+1$. Let $k$ denote the number of non-pendent neighbors of $z$. Then $z$ has $\triangle-k$ pendent neighbors. Hence, $n = (\triangle-k)+2k+1$; that is, $k = n-\triangle-1$. Consequently, $G^* \cong S'_{n, \triangle}$ and hence

which, together with (5.1), implies the desired result.

(b) Since $3\leq \triangle \leq \lfloor \frac{n-1}{2}\rfloor$, it holds that $n\geq 2 \triangle+1$. We observe that $|Z_i|\ge 2$ for every $i\in \{1, 2, \dots, \triangle\}$; otherwise, if $|Z_j| = 1$ for some $j\in \{1, 2, \dots, \triangle\}$ then $|Z_i|\le2$ for every $i\in \{1, 2, \dots, \triangle\}\setminus \{j\}$, and hence $G^*$ would then have at most $2\triangle$ vertices, which contradicts $n\ge 2\triangle+1$. Thus, $G^* \cong {S}_{n, \triangle}^\star$ and hence

which together with (5.1) implies the desired result.

Corollary 5.1. Let $G$ be an $n$-order tree of maximum degree $\triangle$, where $3 \le \triangle \le n-1$.

(i) If $\lceil \frac{n-1}{2} \rceil \leq \triangle \leq n-1$, then

with equality iff $G\cong S'_{n, \triangle}$ (see Figure 3).

(ii) If $3 \leq \triangle \leq \lfloor \frac{n-1}{2} \rfloor$, then

with equality iff $G\cong S_{n, \triangle}^\star$ (see Figure 3).

Proof. Let $\mathfrak{f}(x_1, x_2) = \sqrt{x_1^2+x_2^2+x_1x_2}$ with $x_1\ge1$ and $x_2\ge1$. Since $\mathfrak{f}$ is strictly increasing in both $x_1$ and $x_2$, and because $\mathfrak{f}(x, 1)-\mathfrak{f}(2, 2) > 0$, $(x-1)[\mathfrak{f}(x, 2)-\mathfrak{f}(2, 2)]+ (x-2)[\mathfrak{f}(1, 2)-\mathfrak{f}(2, 2)] > 0$ and $\mathfrak{f}(x, 1)-\mathfrak{f}(x, 2)+\mathfrak{f}(2, 2)-\mathfrak{f}(1, 2) > 0$ for $x\ge3$, Theorem 5.1 provides the desired result.

Remark 5.5. Since all the conditions of Theorem 5.1 hold for each of the functions associated with the following topological indices, Theorem 5.1 covers these indices: ABS index (for its definition, see the paragraph right before Remark 4.1), SO index, and RSO index (for the definitions of SO and RSO indices, see Remark 3.4 and the paragraph right before Remark 3.1, respectively).

The next result's proof (which uses Lemma 5.2) is totally analogous to that of Theorem 5.1 and therefore we omit it.

Theorem 5.2. Let $\mathfrak{f}$ be a real-valued symmetric function defined on the Cartesian square of the set of those real numbers that are greater than or equal to 1, such that

(i) $\mathfrak{f}$ is strictly decreasing in one variable (and hence in both variables because of symmetry),

(ii) the inequality $\mathfrak{f}(x, 1)-\mathfrak{f}(2, 2) < 0$ holds for $x\ge3$,

(iii) the inequality $(x-1)[\mathfrak{f}(x, 2)-\mathfrak{f}(2, 2)]+ (x-2)[\mathfrak{f}(1, 2)-\mathfrak{f}(2, 2)] < 0$ holds for $x\ge3$, and

(iv) the inequality $\mathfrak{f}(x, 1)-\mathfrak{f}(x, 2) + \mathfrak{f}(2, 2) - \mathfrak{f}(1, 2) < 0$ holds for $x\ge3$.

Let $G$ be an $n$-order tree of maximum degree $\triangle$, where $3 \le \triangle \le n-1$.

(a) If $\lceil \frac{n-1}{2} \rceil \leq \triangle \leq n-1$, then

with equality iff $G\cong S'_{n, \triangle}$ (see Figure 3).

(b) If $3 \leq \triangle \leq \lfloor \frac{n-1}{2} \rfloor$, then

with equality iff $G\cong S_{n, \triangle}^\star$ (see Figure 3).

Remark 5.3. Since all the conditions of Theorem 5.2 hold for each of the functions associated with the harmonic and sum-connectivity indices, Theorem 5.2 covers both of these indices, where the definitions of the harmonic and sum-connectivity indices are given in the paragraph right before Remark 3.1.

6.   Conclusions

In this paper, we have established the best possible bounds on the topological index $\mathcal{I}_\mathfrak{f}$ of trees in terms of their order and parameter $\mathfrak{p}$, subject to specific constraints applied to the function $\mathfrak{f}$, where $\mathfrak{p}$ is one of the following: (ⅰ) the matching number, (ⅱ) the number of pendent vertices, and (ⅲ) the maximum degree. We have also characterized all the trees that satisfy these bounds. The constraints considered here for the function $\mathfrak{f}$ are satisfied by a considerable number of existing topological indices.

In most of our main results, the text "strictly increasing" and "strictly decreasing" may be replaced with "increasing" and "decreasing", respectively, without affecting their conclusions; for instance, Theorem 3.1. Also, in most of our results, the conditions may be replaced with simpler conditions; for instance, condition (ⅲ) of Theorem 3.3 can be replaced with the following condition in which every sub-condition involves only one variable (and hence this condition may be considered simpler than condition (ⅲ) of Theorem 3.3): "the functions $\phi$ and $\phi_a$ defined as $\phi(t_1) = \mathfrak{f}(t_1, 1)$ and $\phi_a(t_1) = \mathfrak{f}(t_1, a)-\mathfrak{f}(t_1-1, a)$ with $a\in\{1, 2\}$, are differentiable such that

and the inequality

holds, provided that at least one of the inequalities in (6.1) and (6.2) is strict." However, the number of topological indices' associated functions satisfying this simpler condition is strictly less than the number of topological indices' associated functions satisfying the condition (ⅲ) of Theorem 3.3 (for example, the function associated with the sigma index does not satisfy (6.2) for $t_1 = 2$, but the mentioned function satisfies the condition (ⅲ) of Theorem 3.3).

There are a considerable number of existing topological indices that do not generally satisfy the conditions of our results, but the conclusions of these results still hold for such indices; for instance, the conditions of Theorem 3.3 are not fully satisfied by either of the two Zagreb indices, but the conclusion of Theorem 3.3 remains true for these Zagreb indices (see ^[31,46,47]). Therefore, it would be interesting to modify the conditions of our results in such a way that they cover additional indices.

Author contributions

Akbar Ali, Sneha Sekar, Selvaraj Balachandran and Suresh Elumalai: Methodology, Writing–original draft; Akbar Ali: Conceptualization, Writing–review & editing; Sneha Sekar, Selvaraj Balachandran and Suresh Elumalai: Investigation; Abdulaziz M. Alanazi, Taher S. Hassan and Yilun Shang: Validation, Writing–review & editing, Supervision. All authors have read and approved the final version of the manuscript for publication.

Conflict of interest

Dr. Yilun Shang is a Guest Editor of the special issue "Mathematical properties of complex network and graph theory" for AIMS Mathematics. Yilun Shang was not involved in the editorial review and the decision to publish this article. The authors declare that there are no conflicts of interest in this paper.