A bipartite graph associated to elements and cosets of subgroups of a finite group

1.   Introduction

Topological indices have become an important research topic associated with the study of their mathematical and computational properties and, fundamentally, for their multiple applications to various areas of knowledge (see, e.g., ^[1,2,3]). Within the study of mathematical properties, we will contribute to the study of inequalities and optimization problems associated with topological indices. Our main goals are the Sombor indices, introduced by Gutman in ^[4].

In what follows, $G = \left(V\left(G\right), E\left(G\right) \right)$ will be a finite undirected graph, and we will assume that each vertex has at least a neighbor. We denote by $d_{w}$ the degree of the vertex $w$, i.e., the number of neighbors of $w$. We denote by $uv$ the edge joining the vertices $u$ and $v$ (or $v$ and $u$). For each graph $G$, its Sombor index is

In the same paper is also defined the reduced Sombor index by

In ^[5] it is shown that these indices have a good predictive potential.

Also, the modified Sombor index of $G$ was proposed in ^[6] as

In addition, two other Sombor indices have been introduced: the first Banhatti-Sombor index ^[7]

and the $\alpha$-Sombor index ^[8]

here $\alpha \in \mathbb{R} \setminus \{0\}$. In fact, there is a general index that includes most Sombor indices listed above: the first $(\alpha, \beta)\,$–$\, KA$ index of $G$ which was introduced in ^[9] as

with $\alpha, \beta \in \mathbb{R}$. Note that ${\it SO}(G) = KA_{2, 1/2}(G)$, $^m {\it SO}(G) = KA_{2, -1/2}(G)$, $B {\it SO}(G) = KA_{-2, 1/2}(G)$, and ${\it SO}_\alpha(G) = KA_{\alpha, 1/\alpha}(G)$. Also, we note that $KA_{1, \beta}(G)$ equals the general sum-connectivity index ^[10] $\chi_\beta(G) = \sum_{uv \in E(G)} (d_u + d_v)^\beta.$ Reduced versions of ${\it SO}(G)$, $^mSO(G)$ and $KA_{\alpha, \beta}(G)$ were also introduced in ^[4,6,11], e.g., the reduced $(\alpha, \beta)\,$–$\, KA$ index is

If $\alpha < 0$, then $_{red}KA_{\alpha, \beta}(G)$ is just defined for graphs without pendant vertices (recall that a vertex is said pendant if its degree is equal to $1$).

Since I. Gutman initiated the study of the mathematical properties of Sombor index in ^[4], many papers have continued this study, see e.g., ^{[12,13,14,15,16,17,18]}.

Our main aim is to obtain new bounds of Sombor indices, and to characterize the graphs where equality occurs. In particular, we have obtained bounds for Sombor indices relating them with the first Zagreb index, the forgotten index and the first variable Zagreb index. Also, we solve some extremal problems for Sombor indices.

2.   Inequalities for the Sombor indices

The following inequalities are known for $x, y > 0$:

and the second, third or fifth equality is attained for each $a$ if and only if $x = y$. These inequalities allow to obtain the following result relating $KA$ indices.

Theorem 1. Let $G$ be any graph and $\alpha, \beta, \lambda \in \mathbb{R} \setminus \{0\}$.Then

and the second, third, fifth or sixth equality is attained for each $\alpha, \beta, \lambda$ if and only if all the connected components of $G$ are regular graphs.

Proof. If $a = \beta/ \lambda$, $x = d_u^{ \alpha}$ and $y = d_v^{ \alpha}$, then the previous inequalities give

and the second, third or fifth equality is attained if and only if $d_u = d_v$.

Hence, we obtain

and the equality in the non-strict inequalities is tight if and only if $d_u = d_v$.

If we sum on $uv \in E(G)$ these inequalities, then we obtain $(1)$.

Remark 2. Note that the excluded case $\beta = \lambda$ in Theorem 1 is not interesting, since $KA_{ \alpha \beta/ \lambda, \, \lambda}(G) = KA_{ \alpha, \beta}(G)$ if $\beta = \lambda$.

The argument in the proof of Theorem 1 also allows to obtain the following result relating reduced $KA$ indices.

Theorem 3. Let $G$ be any graph and $\alpha, \beta, \lambda \in \mathbb{R} \setminus \{0\}$.If $\alpha < 0$ or $\, \alpha \beta \lambda < 0$, we also assume that $G$ does not have pendant vertices.Then

and the second, third, fifth or sixth equality is attained for each $\alpha, \beta, \lambda$ if and only if all the connected components of G are regular graphs.

If we take $\beta = 1/ \alpha$ and $\mu = 1/ \lambda$ in Theorem 1, we obtain the following inequalities for the $\alpha$-Sombor index.

Corollary 4. Let $G$ be any graph and $\alpha, \mu \in \mathbb{R} \setminus \{0\}$.Then

and the second, third or fifth equality is attained for each $\alpha, \mu$ if and only if all the connected components of G are regular graphs.

Recall that one of the most studied topological indices is the first Zagreb index, defined by

If we take $\mu = 1$ in Corollary 4, we obtain the following result.

Corollary 5. Let $G$ be any graph and $\alpha \in \mathbb{R} \setminus \{0\}$.Then

and the second, third or fifth equality is attained for each $\alpha$ if and only if all the connected components of G are regular graphs.

If we take $\alpha = 2$, $\beta = -1/2$ and $\lambda = 1/2$ in Theorem 1, we obtain the following inequality relating the modified Sombor and the first Banhatti-Sombor indices.

Corollary 6. Let $G$ be any graph.Then

and the bound is tight if and only if all the connected components of G are regular graphs

In ^[19,20,21], the first variable Zagreb index is defined by

with $\alpha \in \mathbb{R}$.

Note that $M_1^{ \alpha}$ generalizes numerous degree–based topological indices which earlier have independently been studied. For $\alpha = 2$, $\alpha = 3$, $\alpha = -1/2$, and $\alpha = -1$, $M_1^{ \alpha}$ is, respectively, the ordinary first Zagreb index $M_1$, the forgotten index $F$, the zeroth–order Randić index $^0R$, and the inverse index $ID$ ^[2,22].

The next result relates the $KA_{ \alpha, \beta}$ and $M_1^{ \alpha+1}$ indices.

Theorem 7. Let $G$ be any graph with maximum degree $\Delta$, minimum degree $\delta$ and $m$ edges, and $\alpha \in \mathbb{R} \setminus \{0\}$, $\beta > 0$.Then

and the second equality is attained for some $\alpha, \beta$ if and only if $G$ is a regular graph.

Proof. If $uv \in E(G)$ and $\alpha > 0$, then

If $\alpha < 0$, then the converse inequalities hold. Hence,

Since

If $0 < \beta < 1/2$, then $1/(2 \beta) > 1$ and

Consequently, we obtain

If $\beta \ge 1/2$, then $2 \beta \ge 1$ and Hölder inequality gives

Consequently, we obtain

If $G$ is regular, then

If the second equality is attained for some $\alpha, \beta,$ then we have $d_u^ \alpha+d_v^ \alpha = 2 \delta^ \alpha$ or $d_u^ \alpha+d_v^ \alpha = 2 \Delta^ \alpha$ for each $uv \in E(G)$. Also, the equality in Hölder inequality gives that there exists a constant $c$ such that $d_u^ \alpha+d_v^ \alpha = c$ for every $uv \in E(G)$. Hence, we have either $d_u^ \alpha+d_v^ \alpha = 2 \delta^ \alpha$ for each edge $uv$ or $d_u^ \alpha+d_v^ \alpha = 2 \Delta^ \alpha$ for each edge $uv$, and hence, $G$ is regular.

If we take $\alpha = 2$ and $\beta = 1/2$ in Theorem 7 we obtain:

Corollary 8. Let $G$ be any graph with maximum degree $\Delta$ and minimum degree $\delta$, and $m$ edges.Then

and the bound is tight if and only if $G$ is regular.

In order to prove Theorem 10 below we need an additional technical result. A converse of Hölder inequality appears in [23,Theorem 3], which, in the discrete case, can be stated as follows [23,Corollay 2].

Proposition 9. Consider constants $0 < \alpha \le \beta$ and $1 < p, q < \infty$ with $1/p+1/q = 1$.If $w_k, z_k\ge 0$ satisfy $\alpha z_k^q \le w_k^p \le \beta z_k^q$ for $1\le k \le n$, then

where

If $(w_1, \dots, w_n) \neq 0$, then the bound is tight if and only if $w_k^p = \alpha z_k^q$for each $1\le k \le n$ and $\alpha = \beta$.

Recall that a bipartite graph with $X$ and $Y$ partitions is called $(a, b)$-biregular if all vertices of $X$ have degree $a$ and all vertices of $Y$ have degree $b$.

The next result relates several $KA$ indices.

Theorem 10. Let $G$ be any graph, $\alpha, \beta, \mu \in \mathbb{R}$ and $p > 1$.Then

where

and $C_p$ is the constant in Proposition 9. The equality in the upper(lower) bound is tight for each $\alpha, \beta, \mu, p$ if $G$ is a biregular graph (with $\alpha (\beta-\mu \frac{p }{p-1}\, ) \neq 0$ if and only if $G$ is a regular graph.)

Proof. Hölder inequality gives

If $G$ is a biregular graph with $m$ edges, we obtain

Since

if $\alpha p(\beta-\mu \frac{p }{p-1}\, ) \ge 0$, then

and if $\alpha p(\beta-\mu \frac{p }{p-1}\, ) < 0$, then

Proposition 9 gives

Proposition 9 gives that the equality is tight in this last bound for some $\alpha, \beta, \mu, p$ with $\alpha (\beta-\mu \frac{p }{p-1}\, ) \neq 0$ if and only if

i.e., $G$ is regular.

If we take $\beta = 0$ in Theorem 10 we obtain the following result.

Corollary 11. Let $G$ be any graph with $m$ edges, $\alpha, \mu \in \mathbb{R}$ and $p > 1$.Then

The equality in the bound is tight for each $\alpha, \mu, p$ if $G$ is a biregular graph.

If we take $\alpha = 2$, $\beta = 0$, $p = 2$ and $\mu = 1/4$ in Theorem 10 we obtain the following result.

Corollary 12. Let $G$ be any graph with maximum degree $\Delta$, minimum degree $\delta$ and $m$ edges, then

The equality in the upper bound is tight if and only if $G$ is regular.The equality in the lower bound is tight if $G$ is a biregular graph.

Note that the following result improves the upper bound in Corollary 5 when $\alpha > 1$.

Theorem 13. Let $G$ be any graph with minimum degree $\delta$, and $\alpha \ge 1$.Then

and the equality holds for some $\alpha > 1$ in each bound if and only if $G$ is regular.

Proof. The lower bound follows from Corollary 5. Let us prove the upper bound.

First of all, we are going to prove that

for every $\alpha \ge 1$ and $x \ge y \ge 0$. Since (2.1) is direct for $\alpha = 1$, it suffices to consider the case $\alpha > 1$.

We want to compute the minimum value of the function

with the restrictions $g(x, y) = x^{ \alpha} +y^{ \alpha} = 1$, $x \ge y \ge 0$. If $(x, y)$ is a critical point, then there exists $\lambda \in \mathbb{R}$ such that

and so, $(y/x)^{ \alpha-1} = 2^{1/ \alpha} - 1$ and $y = (2^{1/ \alpha} - 1)^{1/(\alpha-1)}x$; this fact and the equality $x^{ \alpha} +y^{ \alpha} = 1$ imply

If $y = 0$, then $x = 1$ and $f(x, y) = 1$.

If $y = x$, then $x = 2^{-1/ \alpha} = y$ and

Hence, $f(x, y) \ge 1$ and the bound is tight if and only if $y = 0$ or $y = x$. By homogeneity, we have $f(x, y) \ge 1$ for every $x \ge y \ge 0$ and the bound is tight if and only if $y = 0$ or $y = x$. This finishes the proof of (2.1).

Consequently,

for each $\alpha \ge 1$ and $d_u \ge d_v$. Thus,

for each $\alpha \ge 1$ and $uv \in E(G)$, and the equality holds for some $\alpha > 1$ if and only if $d_u = d_v = \delta$. Therefore,

and the equality holds for some $\alpha > 1$ if and only if $d_u = d_v = \delta$ for every $uv \in E(G)$, i.e., $G$ is regular.

Corollary 14. Let $G$ be any graph with minimum degree $\delta$.Then

and the equality holds in each bound if and only if $G$ is regular.

The upper bound in Corollary 14 appears in [14,Theorem 7]. Hence, Theorem 13 generalizes [14,Theorem 7].

A family of topological indices, named Adriatic indices, was put forward in ^[24,25]. Twenty of them were selected as significant predictors in Mathematical Chemistry. One of them, the inverse sum indeg index, ${\it ISI}$, was singled out in ^[25] as a significant predictor of total surface area of octane isomers. This index is defined as

In the last years there has been an increasing interest in the mathematical properties of this index. We finish this section with two inequalities relating the Sombor, the first Zagreb and the inverse sum indeg indices.

Theorem 15. Let $G$ be any graph, then

and the upper bound is tight if and only if all the connected components of G are regular graphs.

Proof. It is well-known that for $x, y > 0,$ we have

and the equality

give

In a similar way, we obtain

The equality in this last inequality is tight if and only if $2(d_u^2 + d_v^2) = (d_u + d_v)^2$ for each edge $uv$, i.e., $d_u = d_v$ for every $uv \in E(G)$, and this happens if and only if all the connected components of G are regular graphs.

3.   Optimization problems

We start this section with a technical result.

Proposition 16. Let $G$ be any graph, $u, v \in V(G)$ with $uv \notin E(G)$, and $\alpha, \beta \in \mathbb{R} \setminus \{0\}$ with $\alpha \beta > 0$.Then $KA_{ \alpha, \beta}(G \cup \{uv\}) > KA_{ \alpha, \beta}(G)$.If $\alpha > 0$, then ${}_{red}KA_{ \alpha, \beta}(G \cup \{uv\}) > {}_{red}KA_{ \alpha, \beta}(G)$.Furthermore, if $\alpha < 0$ and $G$ does not have pendant vertices, then ${}_{red}KA_{ \alpha, \beta}(G \cup \{uv\}) > {}_{red}KA_{ \alpha, \beta}(G)$.

Proof. Let $\{w_1, \dots, w_{d_u}\}$ and $\{w^1, \dots, w^{d_v}\}$ be the sets of neighbors of $u$ and $v$ in $G$, respectively. Since $\alpha \beta > 0$, the function

is strictly increasing in each variable if $x, y > 0$. Hence,

The same argument gives the results for the ${}_{red}KA_{ \alpha, \beta}$ index.

Given an integer number $n\ge 2$, let $\Gamma(n)$ (respectively, $\Gamma_{\!\!c}(n)$) be the set of graphs (respectively, connected graphs) with $n$ vertices.

We study in this section the extremal graphs for the $KA_{ \alpha, \beta}$ index on $\Gamma_{\!\!c}(n)$ and $\Gamma(n)$.

Theorem 17. Consider $\alpha, \beta \in \mathbb{R} \setminus \{0\}$ with $\alpha \beta > 0$, and an integer $n\ge 2$.

$(1)$ The complete graph $K_n$ is the unique graph that maximizes $KA_{ \alpha, \beta}$ on $\Gamma_{\!\!c}(n)$ or $\Gamma(n)$.

$(2)$ Any graph that minimizes $KA_{ \alpha, \beta}$ on $\Gamma_{\!\!c}(n)$ is a path.

$(3)$ If $n$ is even, then the union of $n/2$ paths $P_2$ is the unique graph that minimizes $KA_{ \alpha, \beta}$ on $\Gamma(n)$.If $n$ is odd, then the union of $(n-3)/2$ paths $P_2$ with a path $P_3$ isthe unique graph that minimizes $KA_{ \alpha, \beta}$ on $\Gamma(n)$.

$(4)$ Furthermore, if $\alpha, \beta > 0$, then the three previous statements hold if we replace $KA_{ \alpha, \beta}$ with $_{red}KA_{ \alpha, \beta}$.

Proof. Let $G$ be a graph with order $n$, minimum degree $\delta$ and $m$ edges.

Items $(1)$ and $(2)$ follow directly from Proposition 16.

$(3)$ Assume that $n$ is even. It is well known that the sum of the degrees of a graph is equal to twice the number of edges of the graph (handshaking lemma). Thus, $2m \ge n \delta \ge n$. Since $\alpha \beta > 0$, the function

is strictly increasing in each variable if $x, y > 0$. Hence, for any graph $G \in \Gamma(n)$, we have

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

Finally, assume that $n$ is odd. Fix a graph $G \in \Gamma(n)$. If $d_u = 1$ for every $u \in V(G)$, then handshaking lemma gives $2m = n$, a contradiction (recall that $n$ is odd). Therefore, there exists a vertex $w$ with $d_w \ge 2$. By handshaking lemma we have $2m \ge (n-1) \delta+2 \ge n +1$. Recall that the set of neighbors of the vertex $w$ is denoted by $N(w)$. Since $U(x, y)$ is a strictly increasing function in each variable, we obtain

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

$(4)$ If $\alpha, \beta > 0$, then the same argument gives the results for the $_{red}KA_{ \alpha, \beta}$ index.

We deal now with the optimization problem for $_{red}KA_{ \alpha, \beta}$ when $\alpha, \beta < 0$.

Given an integer number $n\ge 3$, we denote by $\Gamma^{wp}(n)$ (respectively, $\Gamma_{\!\!c}^{wp}(n)$) the set of graphs (respectively, connected graphs) with $n$ vertices and without pendant vertices.

Theorem 18. Consider $\alpha, \beta < 0$, and an integer $n\ge 3$.

$(1)$ The cycle graph $C_n$ is the unique graph that minimizes $_{red}KA_{ \alpha, \beta}$ on $\Gamma_{\!\!c}^{wp}(n)$.

$(2)$ The union of cycle graphs are the only graphs that minimize $_{red}KA_{ \alpha, \beta}$ on $\Gamma^{wp}(n)$.

$(3)$ The complete graph $K_n$ is the unique graph that maximizes $_{red}KA_{ \alpha, \beta}$ on $\Gamma_{\!\!c}^{wp}(n)$ or $\Gamma^{wp}(n)$.

Proof. Let $G$ be a graph with order $n$, minimum degree $\delta$ and $m$ edges. Since a graph without pendant vertices satisfies $\delta \ge 2$, handshaking lemma gives $2m \ge n \delta \ge 2n$. Since $\alpha, \beta < 0$, the function

is strictly increasing in each variable if $x, y > 0$. Hence, for any graph $G \in \Gamma^{wp}(n)$, we have

and the inequality is tight if and only if $d_u = 2$ for all $u \in V(G)$, i.e., the graph $G$ is the union of cycle graphs. If $G$ is connected, then it is the cycle graph $C_n$.

Item $(3)$ follows from Proposition 16.

4.   Conclusions

In this paper, we contributed to the study of inequalities and optimization problems associated with topological indices. In particular, we obtained new lower and upper optimal bounds of general Sombor indices, and we characterized the graphs where equality occurs.

Specifically, we have obtained inequalities for these indices relating them with other indices: the first Zagreb index, the forgotten index and the first variable Zagreb index. Finally, we solve some extremal problems for general Sombor indices

Acknowledgments

We would like to thank the reviewers by their careful reading of the manuscript and their suggestions which have improved the presentation of this work. The research of José M. Rodríguez and José M. Sigarreta was supported by a grant from Agencia Estatal de Investigación (PID2019-106433GB- ´ I00/AEI/10.13039/501100011033), Spain. The research of Jose M. Rodríguez is supported by the Madrid Government (Comunidad de Madrid-Spain) under the Multiannual Agreement with UC3M in the line of Excellence of University Professors (EPUC3M23), and in the context of the V PRICIT (Regional Programme of Research and Technological Innovation).

Conflict of interest

All authors declare no conflicts of interest in this paper.