Extremal problems on exponential vertex-degree-based topological indices

1.   Introduction

A topological descriptor is a single number that represents a chemical structure in graph-theoretical terms via the molecular graph, they play a significant role in mathematical chemistry, especially in the QSPR/QSAR investigations. A topological descriptor is called a topological index if it correlates with a molecular property.

Topological indices are used to understand physico-chemical properties of chemical compounds, since they capture the essence of some properties of a molecule in a single number. Several of the well-known topological indices based its computing as a sum of terms which correspond to edges where each term is obtained by a symmetric expression of the degree of both end points, e.g., harmonic, Randić connectivity, first and second Zagreb, atom-bound connectivity and Platt indices. Lately, researchers in chemistry and pharmacology have focused in topological indices based on degrees of vertices obtaining good results and showing that a number of these indices has turned out to be a useful tool, see ^[1] and references therein. Probably, Randić connectivity index ($R$) ^[2] is the most known. In fact, there exist hundreds of works about this molecular descriptor (see, e.g., ^{[3,4,5,6,7,8]} and the references therein). Trying to improve the predictive power of this index during many years, scientists proposed a great number of new topological descriptors based on degrees of vertices, similar to the Randić index. There are a lot of works showing the interest on these indices, see e.g., ^{[9,10,11,12,13,14,15,16,17]}.

The study of the exponential vertex-degree-based topological indices was initiated in ^[18] and has been successfully studied in ^{[19,20,21,22,23,24,25]}. The study of topological indices associated to exponential representations has been successfully studied in ^{[12,14,20,22,26,27]}. Cruz et al. mentioned in 2020 some open problems on the exponential vertex-degree-based topological indices of trees ^[28] and Das et al. show in 2021 the solution of two of those problems in ^[23]. In this sense, we work with generic exponential topological indices described below that allows us to improve some of the bounds given in ^[23] as well as obtain some new results.

Along this work, given a graph $G = \big(V(G), E(G)\big)$ and a symmetric function $f:[1, \infty) \times [1, \infty) \rightarrow \mathbb{R}$, we consider the general topological indices

As usual, $uv$ denotes an edge of the graph $G$ connecting the vertices $u$ and $v$, and $d_x$ denotes the degree of the vertex $x$. The family of the topological indices like the one to the right above are called exponential for obvious reasons.

Two examples of those topological indices that have been extended to its exponential indices are the generalized atom-bound connectivity index, $ABC_\alpha$, and the generalized second Zagreb index, $M_2^\alpha$, defined respectively as

Then, their corresponding exponential indices are

The study of topological indices is often formalized mathematically as optimization problems on graphs. In general, those problems have been proven to be useful and quite difficult. Indeed, to obtain quasi-minimizing or quasi-maximizing graphs is a good strategy that is commonly used. Therefore, frequently, it is needed to find bounds on them which involve several parameters.

Topological indices have been successfully applied to different branches of knowledge, such as chemistry, physics, biology, social sciences, etc. see ^{[29,30,31,32,33]}. In this direction, two of the most important theoretical and practical problems facing the study of topological indices are the following: the study of the extremal problems associated with topological indices and obtaining new inequalities relating different indices. This research has as fundamental contribution to face the above mentioned problems associated with the study of exponential vertex-degree-based topological indices. In particular, we solve some extremal problems related with the exponential vertex-degree-based topological indices $e^{M_2^{\alpha}}$ and $e^{ABC_\alpha}$. Also, we obtain new lower and upper optimal bounds for these general exponential indices.

2.   Optimization problems on the exponential index $e^{M_2^ \alpha}$

Throughout this work, $G = (V (G), E (G))$ denotes a (non-oriented) finite simple graph without isolated vertices. Given a graph $G$ and $v\in V(G)$, we denote by $N(v)$ the set of neighbors of $v$, i.e., $N(v) = \{u\in V(G)|\, uv\in E(G) \}$. We denote by $\Delta, \delta, n, m$ the maximum degree, the minimum degree and the cardinality of the set of vertices and edges of $G$, respectively; thus, $1 \le \delta \le \Delta < n$.

We study in this section some optimization problems on the exponential index $e^{M_2^ \alpha}$.

Recall that we denote by $N(w)$ the set of neighbors of $w$.

Proposition 2.1. Let $G$ be a graph with nonadjacent vertices $u$ and $v$. If $f$ is a symmetric function which is increasing in each variable, then $e^F(G+uv) > e^F(G)$.

Proof. Since $f$ is increasing in each variable, we have $e^{f(d_u+1, d_w)} \ge e^{f(d_u, d_w)}$, $e^{f(d_v+1, d_w)} \ge e^{f(d_v, d_w)}$ and

Hence,

For example, if we take $\alpha > 0$, $f(x, y) = (xy)^ \alpha$, the cycle $C_n$ with $n > 2$ and remove one edge we obtain the path $P_n$, and we have $e^{M_2^a}(C_n) = ne^{4^ \alpha}$, $e^{M_2^a}(P_n) = (n-3)e^{4^ \alpha}+2e^{2^ \alpha}$ and $e^{M_2^a}(C_n)-e^{M_2^a}(P_n) = 3e^{4^ \alpha}-2e^{2^ \alpha} > 0$. Now if we take the complete graph $K_n$ with $n > 2$ and $H$ is the graph obtained by removing an edge from $K_n$, we have $e^{M_2^a}(K_n) = \frac{n(n-1)}{2}e^{(n-1)^{2 \alpha}}$, $e^{M_2^a}(H) = \left(\frac{(n-2)(n-3)}{2} \right) e^{(n-1)^{2 \alpha}} + 2(n-2)e^{[(n-1)(n-2)]^{ \alpha}}$ and $e^{M_2^a}(K_n)-e^{M_2^a}(H) = (2n-3)e^{(n-1)^{2 \alpha}}-2(n-2)e^{[(n-1)(n-2)]^{ \alpha}} > 0$. Thus, we have $e^{(n-1)^{ \alpha}-(n-2)^{ \alpha}} > 1 > \frac{2n-4}{2n-3}$.

Given an integer $n\ge 2$, let $\mathcal{G}(n)$ be the set of graphs with $n$ vertices.

Given integers $1\le \delta < n$, let $\mathcal{H}(n, \delta)$ be the set of graphs with $n$ vertices and minimum degree $\delta$

We consider the optimization problem for the exponential index $e^{M_2^ \alpha}$ on $\mathcal{G}(n)$.

Theorem 2.2. Consider $\alpha > 0$ and an integer $n\ge 2$.

$(1)$ The unique graph that maximizes the $e^{M_2^{ \alpha}}$ index on $\mathcal{G}(n)$ is the complete graph $K_n$.

$(2)$ If $n$ is even, then the unique graph that minimizes the $e^{M_2^{ \alpha}}$ index on $\mathcal{G}(n)$ is the disjoint union of $n/2$ paths $P_2$. If $n$ is odd, then the unique graph that minimizes the $e^{M_2^{ \alpha}}$ index on $\mathcal{G}(n)$ is the disjoint union of $(n-3)/2$ paths $P_2$ and a path $P_3$.

Proof. Since $\alpha > 0$ we have that $f(x, y) = (xy)^ \alpha$ is an increasing function in each variable and so, we can apply Proposition 2.1. The first item is a direct consequence of Proposition 2.1.

Assume first that $n$ is even. Handshaking lemma gives $2m \ge n \delta \ge n$. We have for any graph $G \in \mathcal{G}(n)$

and the equality in the bound is attained if and only if $d_u = 1$ for every $u \in V(G)$, i.e., $G$ is the disjoint union of $n/2$ path graphs $P_2$.

Assume now that $n$ is odd, and consider a graph $G \in \mathcal{G}(n)$. If $d_u = 1$ for every $u \in V(G)$, then handshaking lemma gives $2m = n$, a contradiction since $n$ is odd. Thus, there exists a vertex $w$ with $d_w \ge 2$. Handshaking lemma gives $2m \ge (n-1) \delta+2 \ge n +1$. We have

and the equality in the bound is attained if and only if $d_u = 1$ for every $u \in V(G)\setminus \{w\}$, and $d_w = 2$, i.e., $G$ is the disjoint union of $(n-3)/2$ path graphs $P_2$ and a path graph $P_3$.

Note that for $\alpha = 1$, the result in Theorem 2.2 was obtained in [20,Theorem 2.2].

If $1 \le \delta < \Delta$ are integers, we say that a graph $G$ is $(\Delta, \delta)$-pseudo-regular if there exists $v \in V(G)$ with $d_v = \Delta$ and $d_u = \delta$ for every $u \in V(G) \setminus \{v\}$.

In ^[34] appears the following result.

Lemma 2.3. Consider integers $2 \le k < n$.

$(1)$ If $k n$ is even, then there is a connected $k$-regular graph with $n$ vertices.

$(2)$ If $k n$ is odd, then there is a connected $(k+1, k)$-pseudo-regular graph with $n$ vertices.

Given integers $1\le \delta < n$, denote by $K_n^ \delta$ the $n$-vertex graph with maximum degree $n-1$ and minimum degree $\delta$, obtained from the complete graph $K_{n-1}$ and an additional vertex $v$ in the following way: Fix $\delta$ vertices $u_1, \dots, u_ \delta \in V(K_{n-1})$ and let $V(K_n^ \delta) = V(K_{n-1}) \cup \{v\}$ and $E(K_n^ \delta) = E(K_{n-1}) \cup \{u_1v, \dots, u_ \delta v\}$.

Figure 1 illustrates this construction by showing the graphs $K_6^2$ and $K_6^3$.

We consider now the optimization problem for the exponential index $e^{M_2^{ \alpha}}$ on $\mathcal{H}(n, \delta)$.

Theorem 2.4. Consider $\alpha > 0$ and integers $1\le \delta < n$.

$(1)$ Then the unique graph in $\mathcal{H}(n, \delta)$ that maximizes the $e^{M_2^{ \alpha}}$ index is $K_n^ \delta$.

$(2)$ If $\delta \ge 2$ and $\delta n$ is even, then the unique graphs in $\mathcal{H}(n, \delta)$ that minimize the $e^{M_2^{ \alpha}}$ index are the $\delta$-regular graphs.

$(3)$ If $\delta \ge 2$ and $\delta n$ is odd, then the unique graphs in $\mathcal{H}(n, \delta)$ that minimize the $e^{M_2^{ \alpha}}$ index are the $(\delta+1, \delta)$-pseudo-regular graphs.

Proof. Given a graph $G \in \mathcal{H}(n, \delta)\setminus \{K_n^ \delta\}$, fix any vertex $u \in V(G)$ with $d_u = \delta$. Since

Proposition 2.1 gives $e^{M_2^{ \alpha}}(K_n^ \delta) > e^{M_2^{ \alpha}}(G)$. This proves item $(1)$.

Handshaking lemma gives $2m \ge n \delta$.

Since $d_u \ge \delta$ for every $u \in V(G)$, we obtain

and the equality in the bound is attained if and only if $d_u = \delta$ for every $u \in V(G)$.

If $\delta n$ is even, then Lemma 2.3 gives that there is a $\delta$-regular graph with $n$ vertices. Hence, the unique graphs in $\mathcal{H}(n, \delta)$ that minimize the $e^{M_2^{ \alpha}}$ index are the $\delta$-regular graphs.

If $\delta n$ is odd, then handshaking lemma gives that there is no regular graph. Hence, there exists a vertex $w$ with $d_w \ge \delta+1$. Since $d_u \ge \delta$ for every $u \in V(G)$, handshaking lemma gives $2m \ge (n-1) \delta+ \delta+1 = n \delta+1$. We have

From the above and since $w$ has at least $\delta+1$ neighbors we have

now using $2m \ge n \delta+1$, we have

and equality in the bound is attained if and only if $d_u = \delta$ for every $u \in V(G)\setminus \{w\}$, and $d_w = \delta+1$. Lemma 2.3 gives that there is a $(\delta+1, \delta)$-pseudo-regular graph with $n$ vertices. Therefore, the unique graphs in $\mathcal{H}(n, \delta)$ that minimize the $e^{M_2^{ \alpha}}$ index are the $(\delta+1, \delta)$-pseudo-regular graphs.

3.   Optimal inequalities for exponential generalized atom-bound connectivity indices

In [23,Theorem 2.1] appears the inequality

The equality holds in this bound if and only if $G$ is a disjoint union of isolated edges or each connected component of $G$ is a path graph $P_k$ $(k \ge 3)$ or a cycle graph $C_k$ $(k \ge 3)$.

Proposition 3.1. If $G$ is a graph with size $m$, then

The equality holds if every edge of $G$ is incident to a vertex of degree $2$, or $G$ is regular or biregular.

Proof. $ABC(G) = \sum\limits_{uv\in E(G)} \Big(\frac{d_u+d_v-2}{d_u\, d_v}\Big).$ Note that the exponential function $\exp(x) = e^x$ is a strictly convex function, and Jensen's inequality gives

and the equality in this bound is attained if and only if $\frac{d_u+d_v-2}{d_u\, d_v} = \frac{d_w+d_z-2}{d_w\, d_z}$ for every $uv, wz\in E(G)$.

If every edge of $G$ is incident to a vertex of degree $2$, then $\frac{d_u+d_v-2}{d_u\, d_v} = \frac12$ for every $uv \in E(G)$. If $G$ is a regular or biregular graph, then $\frac{d_u+d_v-2}{d_u\, d_v} = \frac{ \Delta+ \delta-2}{ \Delta \delta}$ for every $uv \in E(G)$.

Since $\frac{\sqrt{2(\Delta-1)}}{ \Delta} < \sqrt{1-\frac1 \Delta}\,$ if $\Delta > 2$, Propostion 3.1 improves [23,Theorem 2.1].

The following result relates the exponential generalized atom-bound connectivity indices with positive and negative parameters.

Theorem 3.2. Let $G$ be a graph with $m$ edges, minimum degree $\delta$, maximum degree $\Delta > 2$, and without isolated edges, and let $\alpha, \beta \in \mathbb{R}$ with $\alpha > 0 > \beta$. Then

and the equality holds if and only if $G$ is regular.

If $\delta = 1$, then

and the equality holds if and only if $G$ is the disjoint union of star graphs $K_{1, \Delta}$.

If $\delta\ge 2$, then

If $\delta > 2$, then the equality holds if and only if $G$ is regular. If $\delta = 2$, then the equality holds if and only if each edge in $G$ is incident to a vertex with degree two.

Proof. For each fixed $\alpha$ and $\beta$ with $\alpha > 0 > \beta$, we are going to compute the extremal values of the function $g:[ \delta, \Delta] \times [\max{}\{ 2, \delta \}, \Delta]$ (with $\Delta\ge 3$) given by

We have

Then the function $g(x, y)$ is decreasing on $x\in[ \delta, \Delta ]$ for each fixed $y\in [\max\{2, \delta \}, \Delta]$ and consequently

Let us define

We have

Then $g_1(y)$ is strictly decreasing, and consequently $g_1(\Delta)\le g_1(y)$. Therefore, for each $uv\in E(G)$ we have

and the equality in the last inequality holds if and only if $d_u = d_v = \Delta$ for each $uv\in E(G)$, i.e., $G$ is a regular graph.

Let us define

We have

If $\delta = 1$, then $g_2^\prime(y) > 0$ and so, $g_2(y)$ is strictly increasing. Consequently, $g_2(y) \le g_2(\Delta)$, and we have for each $uv\in E(G)$

and the equality in the last inequality holds if and only if $d_u = 1$ and $d_v = \Delta$ o viceversa for each $uv\in E(G)$, i.e., $G$ is the disjoint union of star graphs $K_{1, \Delta}$.

If $\delta = 2$, then $g_2^\prime(y) = 0$ and so, $g_2(y)$ is a constant function. We have

and the equality in the last inequality holds if and only if each edge in $G$ is incident to a vertex with degree two.

If $\delta > 2$, then $g_2^\prime(y) < 0$ and so, $g_2(y)$ is strictly decreasing. Consequently, $g_2(y) \le g_2(\delta)$, and we have for each $uv\in E(G)$

and the equality in the last inequality holds if and only if $d_u = d_v = \delta$ for each $uv\in E(G)$, i.e., $G$ is a regular graph.

The hypothesis $\Delta > 2$ in Theorem 3.2 is not an important restriction: If $\Delta = 2$, then $G$ is is the disjoint union of path and cycle graphs with three or more vertices, and we have $e^{ABC_ \alpha(G)} = me^{\left(\frac{1}{2} \right)^ \alpha }$. Hence,

4.   Conclusions

We have studied some properties of the generalized exponential indices. For the exponential index $e^{M_2^\alpha}$ with $\alpha > 0$, we characterize the graphs with extreme values in the class of graphs with a fixed number of vertices and in the class of graphs with a fixed minimum degree and a fixed number of vertices.

In addition, we found some optimal inequalities involving the exponential atom-bound connectivity index. In particular, we found a bound that improves a result in ^[23]. Also, we obtained an inequality concerning the indices $e^{ABC_ \alpha}$ for different values of the parameter.

As an open problem it remains to find the extremal graphs and to obtain optimal bounds for other generalized exponential vertex-degree-based topological indices. In particular, for the index $e^{M_2^a}$ to find the extremal graphs in other classes, for example the class of graphs with $n$ vertices and fixed maximum degree.

Acknowledgments

This research is supported by a grant from Agencia Estatal de Investigación (PID2019-106433GB-I00 / AEI / 10.13039/501100011033), Spain.

Conflict of interest

The author declare there is no conflict of interest.