On the extremal cacti with minimum Sombor index

1.   Introduction

Throughout this paper, we consider simple and undirected graphs. Let $H = (V_H, E_H)$ be a graph, where $V_H$ and $E_H$ be the vertex set and the edge set of $H$, respectively. The $degree$ of a vertex $u\in V_H$, denoted by $d_H(u)$, is the number of edges which connected to $u$ in $H$. A vertex $u$ is called a $pendant \; vertex$ if $d_H(u) = 1$. For an edge $e = xy\in E_H$, $e$ is a $pendant \; edge$ of $H$ if $d_H(x) = 1$ or $d_H(y) = 1$. For a vertex $v \in V_H$ and an edge $xy \in E_H$, $H-v$ and $H-xy$ denote the graphs obtained from $H$ by deleting the vertex $v$ and the edge $xy$, respectively. If $x$ and $y$ are two vertices in $V_H$ and $xy \notin E_H$, $H+xy$ is the graph obtained from $H$ by adding an edge $xy$. For any vertex $u \in V_H$, $N_H(u)$ denoted the neighborhood vertex set in $H$. The symbols $\delta(H)$ and $\Delta(H)$ represent the minimum degree and the maximum degree of $H$, respectively. Denote by $P_n$ and $C_n$ the path and the cycle with $n$ vertices, respectively. One can refer to ^[1] for other notations and terminologies undefined in this paper.

Topological indices of graphs have been widely studied in mathematical chemistry. The topological indices can be used in theoretical, medicinal and organic chemistry for studying the structure and physicochemical properties of chemical molecular. The Wiener index is the most well-known topological index which is introduced by the famous chemist Harry Wiener for investigating boiling points of alkanes ^[2].

Recently, two new degree-based graph topological indices, named Sombor index and reduced Sombor index, are introduced by Gutman ^[3]. The Sombor index and the reduced Sombor index of a graph $H$ are defined, respectively, as

and

Nowdays, the study on the Sombor index and the reduced Sombor index of various graphs has been a hot topic in graph theory. Alidadi et al. ^[4] investigated the minimum Sombor index of the unicyclic graphs with given diameter. Zhou et al. ^[5] characterized the extremal trees and unicyclic graphs with minimum Sombor index among the trees and unicyclic graphs with given order and maximum degree. The lower and upper bounds of the Sombor index of the trees in terms of order, independence number and the number of pendant vertices were given by Das and Gutman in ^[6], and the corresponding extremal trees were characterized. Li et al. ^[7] characterized the extremal graphs with respect to the Sombor index among all the $n$-order trees with a given diameter. The maximum and minimum Sombor indices of trees with fixed domination number were presented by Sun and Du in ^[8]. Cruz et al. ^[9] discussed the Sombor index of chemical graphs, chemical trees and hexagonal systems and characterized the extremal graphs. The upper bound for the Sombor index among all molecular trees with given order was obtained by Deng et al. in ^[10]. Ülker et al. ^[11] studied the relations between energy and Sombor index of a graph in terms of its degrees. Horoldagva and Xu ^[12] investigated the lower and upper bounds for the Sombor index of the the graphs with given girth. Liu et al. ^[13] studied the reduced Sombor index of the graphs with given graph parameters, obtained the expected values of reduced Sombor index in random polyphenyl chain, and applied the reduced Sombor index to graph spectrum and energy problems.

A cactus is a connected graph that any block is either a cut edge or a cycle. It is also a graph in which any two cycles have at most one common vertex. A cycle in a cactus is called $pendant \; cycle$ if all but one vertex of this cycle have degree 2, a cycle $C$ in a cactus is called $interal \; cycle$ if $C$ is not a pendant cycle. Let $\mathcal{C}(n, k)$ be the class of cacti of order $n$ with $k$ cycles.

It is routine to check that $\mathcal{C}(n, 0)$ is the set of trees and $\mathcal{C}(n, 1)$ is the set of unicyclic graphs. Gutman investigated the Sombor index of trees in ^[3] and proved that $SO(H) \geq 2\sqrt{2}n$ for any tree $H$ with $n$ vertices. Cruz and Rada ^[14] proved that $SO(H) \geq 2\sqrt{2}n$ for any unicyclic graph $H$ with $n$ vertices.

Recently, Wu, An and Wu ^[15] established the lower bound for the Sombor index of the cacti in $\mathcal{C}(n, k)$ and characterized the corresponding extremal cacti when $n\geq 6k-4$ and $k \geq 2$. In this paper, the lower bound for the Sombor index of a cactus in $\mathcal{C}(n, k)$ is obtained and the corresponding extremal cacti are characterized when $n\geq 4k-2$ and $k \geq 2$ which improves the result of Wu et al. ^[15]. Moreover, it is also shown that our approach is valid for the reduced Sombor index of the cacti in $\mathcal{C}(n, k)$. The following Theorems 1.1 and 1.2 are our main results.

Theorem 1.1. Let $H$ be a cactus in $\mathcal{C}(n, k)$ with $n\geq4k-2$ and $k\geq 2$. Then,

with equality holds if and only if $H\in\widetilde{\mathcal{C}}(n, k)$ (where $\widetilde{\mathcal{C}}(n, k)$ is a subset of $\mathcal{C}(n, k)$, and the definition of $\widetilde{\mathcal{C}}(n, k)$ is introduced in Section 4).

Theorem 1.2. Let $H$ be a cactus in $\mathcal{C}(n, k)$ with $n\geq4k-2$ and $k\geq 2$. Then,

with equality holds if and only if $H\in\widetilde{\mathcal{C}}(n, k)$ (where $\widetilde{\mathcal{C}}(n, k)$ is a subset of $\mathcal{C}(n, k)$, and the definition of $\widetilde{\mathcal{C}}(n, k)$ is introduced in Section 4).

The rest of this paper is organized as follows. In Sections 2 and 3, it is proved that the minimum and maximum degrees of the cacti in $\mathcal{C}(n, k)$ ($n\geq4k-2$ and $k\geq 2$) with minimum Sombor index (and reduced Sombor index) are 2 and 3, respectively. In Section 4, the proofs of Theorems 1.1 and 1.2 are presented.

2.   The minimum degree of the cacti in $\mathcal{C}(n, k)$ with minimum Sombor index and reduced Sombor index

In this section, the minimum degree of the cacti in $\mathcal{C}(n, k)$ ($n\geq4k-2$ and $k\geq 2$) with minimum Sombor index and reduced Sombor index is discussed. Let $T_H$ be the graph obtained from a graph $H$ in $\mathcal{C}(n, k)$ by contracting each cycle of $H$ into a vertex (called a cyclic vertex). Let $P = v_1v_2\cdots v_l$ be a path in $H$. If $d_H(v_1)\geq3$, $d_H(v_l) = 1$ and $d_H(v_i) = 2$ for $2\leq i\leq l-1$, then we call $P$ is a $pendant \; path$ of $H$.

Lemma 2.1. ^[16] Let $x$ and $y$ be two nonnegative integers and $z$ be a fixed nonnegative integer. Then the function $\sqrt{(x+z)^2+y^2}-\sqrt{x^2+y^2}$ is increasing with $x$ for fixed $y$ and decreasing with $y$ for fixed $x$.

Lemma 2.2. Let $H$ be a cactus in $\mathcal{C}(n, k)$ with $k \geq 2$. If $P = v_1v_2\cdots v_l$ and $P' = u_1u_2\cdots u_s$ are two different pendant paths of $H$ with $d_H(v_1)\geq3$ and $d_H(u_1)\geq3$. Let $H' = H-v_1v_2+u_sv_2$. Then $SO(H) > SO(H')$ and $SO_{red}(H) > SO_{red}(H')$.

Proof. Let $d_H(v_1) = t$ ($t\geq3$) and $N_H(v_1) = \{ v_2, w_1, w_2, \cdots, w_{t-1} \}$. By the conditions, one has $d_{H'}(v_1) = t-1$, $d_{H}(u_s) = 1$, $d_{H'}(u_s) = 2$ and $d_{H}(v) = d_{H'}(v)$ for any vertex $v\in V_H\setminus\{v_1, u_s\}$. We divide this problem into two cases.

Case 1: $l > 2$.

By the definition of Sombor index, one has that

It is routine to check that $d_H(u_{s-1}) \geq d_{H'}(u_{s-1})\geq2$ if $s = 2$ and $d_H(u_{s-1}) = d_{H'}(u_{s-1}) = 2$ if $s > 2$. Thus, by Lemma 2.1, we obtain that

Then $SO(H)-SO(H')\geq \sqrt{13}-\sqrt{8}+\sqrt{5}-\sqrt{8} > 0$.

By a similar calculation method, we get

Case 2: $l = 2$.

According to the definition of Sombor index, we have

In a similar manner, we deduce that

These complete the proof. □

Lemma 2.3. Let $H$ be a cactus in $\mathcal{C}(n, k)$ with $k \geq 2$. If there is at most one pendant path in $H$, then there exists an edge $u_1u_2\in E_H$ on some cycle of $H$ such that $d_H(u_1) = d_H(u_2) = 2$.

Proof. By the fact that $H$ is a cactus, then $T_H$ is a connected tree. Thus there exists at least two pendant vertices in $H$. By the condition that there is at most one pendant path in $H$, then there exists at least one pendant vertex which is cyclic vertex in $T_H$. So there exists at least one pendant cycle in $H$. By the definition of pendant cycle, the result follows. □

Lemma 2.4. Let $H$ be a cactus in $\mathcal{C}(n, k)$ ($k \geq 2$) with an edge $u_1u_2\in E_H$ on some cycle of $H$ such that $d_H(u_1) = d_H(u_2) = 2$. Let $P = v_1v_2\cdots v_l$ be a pendant path of $H$ with $d_H(v_1)\geq3$ and $H' = H-v_1v_2-u_1u_2+u_1v_2+u_2v_l$. Then $SO(H) > SO(H')$ and $SO_{red}(H) > SO_{red}(H')$.

Proof. Let $d_H(v_1) = t$ ($t\geq3$) and $N_H(v_1) = \{ v_2, w_1, w_2, \cdots, w_{t-1} \}$. By the conditions, one has $d_{H'}(v_1) = t-1$, $d_{H}(v_l) = 1$, $d_{H'}(v_l) = 2$ and $d_{H}(v) = d_{H'}(v)$ for any vertex $v\in V_H\setminus\{v_1, v_l\}$. We divide this problem into two cases.

Case 1: $l > 2$.

By the definition of Sombor index, one has that

The corresponding result for reduced Sombor index is the following:

Case 2: $l = 2$.

From the definition of Sombor index, we have

By a similar calculation method, one obtains that

These end the proof. □

Lemma 2.5. Let $H$ be a cactus in $\mathcal{C}(n, k)$ ($k \geq 2$) with minimum Sombor index. Then $\delta(H) = 2$.

Proof. If $H$ contains no pendant edge, by Lemma 2.3, there exists at least one vertex with degree $2$, the result follows.

If $H$ contains pendant edges, from Lemma 2.2, $H$ contains just one pendant edge. By Lemmas 2.3 and 2.4, there exists a cactus $H'$ in $\mathcal{C}(n, k)$ such that $SO(H) > SO(H')$, which contradicts to the condition that $H$ is a cactus with minimum Sombor index.

This ends the proof. □

By a similar proof with Lemma 2.5, the following Corollary 2.6 can be obtained immediately.

Corollary 2.6. Let $H$ be a cactus in $\mathcal{C}(n, k)$ ($k \geq 2$) with minimum reduced Sombor index. Then $\delta(H) = 2$.

3.   The maximum degree of the cacti in $\mathcal{C}(n, k)$ with minimum Sombor index and reduced Sombor index

In this section, the maximum degree of the cacti in $\mathcal{C}(n, k)$ ($n\geq4k-2$ and $k\geq 2$) with minimum Sombor index and reduced Sombor index is discussed.

Lemma 3.1. Let $H$ be a cactus in $\mathcal{C}(n, k)$ ($k \geq 2$) with minimum Sombor index. Then there does not exist a path $u_1u_2\cdots u_l$ ($l\geq3$) in $H$ such that $d_H(u_1)\geq 3, d_H(u_l)\geq 3$ and $d_H(u_i) = 2 \; (i = 2, \cdots, l-1)$, where $u_1$ and $u_l$ are not adjacent.

Proof. Suppose to the contrary that there exists a path $u_1u_2\cdots u_l$ ($l\geq3$) in $H$ such that $d_H(u_1)\geq\; 3, d_H(u_l)\geq 3$ and $d_H(u_i) = 2 \; (i = 2, \cdots, l-1)$, where $u_1$ and $u_l$ are not adjacent. By Lemma 2.5, each end block of $H$ is a cycle and there exists at least one edge $e = v_1v_2$ with $d_H(v_1) = d_H(v_2) = 2$ on some end block of $H$. Let $H' = H-u_1u_2-u_{l-1}u_l-v_1v_2+v_1u_2+v_2u_{l-1}+u_1u_l$. It is routine to check that $d_{H'}(u) = d_H(u)$ for each vertex $u$ of $H$. Therefore,

Note that $d_{H}(u_1)\geq 3$ and $d_{H}(u_l) > 2$, by Lemma 2.1, one has that

Thus, $SO(H)-SO(H') > 0$ which contradicts to the fact that $H$ has minimum Sombor index.

This completes the proof. □

The corresponding result for reduced Sombor index is the following Lemma 3.2.

Lemma 3.2. Let $H$ be a cactus in $\mathcal{C}(n, k)$ ($k \geq 2$) with minimum reduced Sombor index. Then there does not exist a path $u_1u_2\cdots u_l \; (l\geq3)$ in $H$ such that $d_H(u_1)\geq 3, d_H(u_l)\geq 3$ and $d_H(u_i) = 2 \; (i = 2, \cdots, l-1)$, where $u_1$ and $u_l$ are not adjacent.

From Lemmas 3.1 and 3.2, the following Corollary 3.3 can be obtained immediately.

Corollary 3.3. Let $H$ be a cactus in $\mathcal{C}(n, k)$ ($k \geq 2$) with minimum Sombor index or minimum redeced Sombor index. Then, the following results hold.

(i) If $u$ is a vertex of $H$ with $d_H(u) = 2$, then $u$ lies on some cycle of $H$.

(ii) Let $C$ be a cycle of $H$. Then, either $C$ is an end block, or $C$ contains exactly two adjacent vertices whose degrees are not 2, or no vertex of $C$ with degree 2.

Lemma 3.4. Let $H$ be a cactus in $\mathcal{C}(n, k)$ ($n\geq4k-2$ and $k\geq 2$) with minimum Sombor index. If $\Delta(H) \geq 4$, then there exists a path $v_1v_2v_3v_4$ in $H$ such that $d_H(v_2) = d_H(v_3) = 2$ and $v_1\neq v_4$.

Proof. Let $t = \Delta(H)$ and $n_i$ be the number of vertices of $H$ with degree $i$ ($i = 1, 2, \cdots, t$). From Lemma 2.5, $\delta(H) = 2$. Then, we get

and

From (3.1) and (3.2), one obtains that

and

By the condition $\Delta(H) \geq 4$, we have

and

From Corollary 3.3(i), each vertex with degree 2 lies on some cycle of $H$. Since there are exactly $k$ cycles in $H$ and $n_2\geq2k+1$, there exists a cycle $C$ in $H$ which contains at least three vertices with degree $2$. By Corollary 3.3(ii), $C$ is an end block or $C$ contains exactly two adjacent vertices whose degrees are not 2. Combining the fact that $C$ contains at least three vertices with degree $2$, the result holds. □

Lemma 3.5. Let $H$ be a cactus in $\mathcal{C}(n, k)$ ($n\geq4k-2$ and $k\geq 2$) with minimum Sombor index. Then $\Delta(H) = 3$.

Proof. Suppose to the contrary that $\Delta(H) \geq 4$. Let $u\in V_H$ be a vertex with $d_H(u) = \Delta(H) = t$ and $N_H(u) = \{v_1, v_2, \cdots, v_t\}$. It is routine to check that $u$ is a cut vertex of $H$. Let $H_1, H_2, \cdots, H_s$ ($s\leq t$) be the pairwise-vertex-disjoint connected components of $H-u$. By Lemma 3.4 and the condition that $\Delta(H) \geq 4$, there exists a path $P = w_1w_2w_3w_4$ in $H$ such that $d_H(w_2) = d_H(w_3) = 2$ and $w_1\neq w_4$. We divide this discussion into two cases.

Case 1: $u\notin\{w_1, w_4\}$.

Without loss of generality, suppose that $P\subset H_s$. We claim that $|V_{H_i}\cap\{v_1, v_2, \cdots, v_t\}| \leq 2$ for each $i = 1, 2, \cdots, s$. Otherwise, one can suppose to the contrary that there exists some $i$ such that $|V_{H_i}\cap\{v_1, v_2, \cdots, v_t\}| \geq 3$. Without loss of generality, suppose that $\{v_1, v_2, v_3\}\subset V_{H_i}\cap\{v_1, v_2, \cdots, v_t\}$. Then, there exist two different cycles $C_1$ and $C_2$ in $H$ such that $\{v_1, v_2, u\} \subset V_{C_1}$ and $\{v_1, v_3, u\} \subset V_{C_2}$. Which contradicts to the definition of cactus that any two cycles have at most one common vertex.

If $|V_{H_i}\cap\{v_1, v_2, \cdots, v_t\}| = 1$ for each $i = 1, 2, \cdots, s-1$, by $t\geq4$, $s\geq3$ and one can suppose that $v_1\in H_1$, $v_2\in H_2$. If there exists some $j\in 1, 2, \cdots, s-1$ such that $|V_{H_j}\cap\{v_1, v_2, \cdots, v_t\}| = 2$, by $t\geq4$, $s\geq2$ and one can suppose that $v_1, v_2\in H_j$.

Let $H' = H-uv_1-uv_2-w_1w_2-w_2w_3+w_1w_3+v_1w_2+v_2w_2+uw_2$. Then $d_H(u) = t, d_H(w_2) = \; 2, d_{H'}(u) = t-1, d_{H'}(w_2) = 3$ and $d_{H'}(g) = d_H(g)$ for each other vertex $g$ of $H$. Thus,

Set $f(t) = \sqrt{2}t-\frac{1}{2\sqrt{2}}-\sqrt{(t-1)^2+3^2}$. Then $f'(t) = \sqrt{2}-\frac{(t-1)}{\sqrt{(t-1)^2+3^2}} > \sqrt{2}-1 > 0$ for $t\geq4$. This implies that

and

Which contradicts to the condition that $H$ is a cactus with minimum Sombor index. Therefore, $\Delta(H) \leq\; 3$.

Case 2: $u\in\{w_1, w_4\}$.

If $u = w_4$, let $H' = H-uv_1-uv_2-w_1w_2-w_2w_3+w_1w_3+v_1w_2+v_2w_2+uw_2$. If $u = w_1$, let $H' = H-uv_1-uv_2-w_4w_3-w_2w_3+w_4w_2+v_1w_3+v_2w_3+uw_3$. By a similar calculation method with Case 1, one has that $SO(H)-SO(H') > 0$. Which contradicts to the condition that $H$ is a cactus with minimum Sombor index. Thus, $\Delta(H) \leq 3$.

On the other hand, by $k \geq 2$, there exists at least one vertex in $H$ with degree $3$. The result holds. □

By similar proof with Lemmas 3.4 and 3.5, the following Corollary 3.6 can be obtained immediately.

Corollary 3.6. Let $H$ be a cactus in $\mathcal{C}(n, k)$ ($n\geq4k-2$ and $k\geq 2$) with minimum reduced Sombor index. Then $\Delta(H) = 3$.

4.   The proofs of Theorems 1.1 and 1.2

Let $H$ be a cactus in $\mathcal{C}(n, k)$ ($n\geq4k-2$ and $k\geq 2$) with minimum reduced Sombor index. By Corollaries 2.6 and 3.6, we have $2\leq d_{H}(v)\leq 3$ for each vertex $v$ in $H$. Let $E_{i, j} = \{uv\in E_H|d_{H}(u) = i, d_{H}(v) = j\}$ for $i, j\in\{2, 3\}$ and $e_{i, j} = |E_{i, j}|$. Thus

Note that $n_i$ is the number of vertices of $H$ with degree $i$ ($i\in\{2, 3\}$). It can be check that the degree sums of the vertices of degree 2 and degree 3, respectively, are

and

By the fact $n_2+n_3 = n$, one has that

Combining (4.1) and (4.2), we have

and

Lemma 4.1. Let $H$ be a cactus in $\mathcal{C}(n, k)$ ($n\geq4k-2$ and $k\geq 2$) with minimum reduced Sombor index. Then

Proof. By the definition of the reduced Sombor index and the fact that $2\leq d_{H}(v)\leq 3$ for each vertex $v$ in $H$, combining (4.3) and (4.4), we get

This completes the proof. □

By a similar proof with Lemma 4.1, the following Corollary 4.2 can be gotten directly.

Corollary 4.2. Let $H$ be a cactus in $\mathcal{C}(n, k)$ ($n\geq4k-2$ and $k\geq 2$) with minimum Sombor index. Then

In the following, a new set of cacti, named $\widetilde{\mathcal{C}}(n, k)$, is introduced. Let $\widetilde{\mathcal{C}}(n, k)$ denote the set of the element $H$ of $\mathcal{C}(n, k)$ with the following properties:

(i) $\delta(H) = 2$ and $\Delta(H) = 3$.

(ii) A vertex is cut vertex if and only if its degree is 3, and there are exactly $2k-2$ cut vertices.

(iii) If $k$ is even, there are $\frac{k-2}{2}$ internal cycles and every internal cycle is triangle. Moreover, there is no vertex not belong to any cycle and the degree of each vertex on internal cycles is 3.

(iv) If $k$ is odd, there are $\frac{k-3}{2}$ internal cycles, and each internal cycle is one of the following 3 kinds of cycles: (1) a 3-cycle whose vertices are all degree 3; (2) a 4-cycle whose vertices are all degree 3; (3) a cycle which contains exactly two adjacent 3-degree vertices. Moreover, there are $b$ internal 4-cycles whose vertices are all degree 3, $c_2$ cycles each of which contains exactly two adjacent 3-degree vertices, and $t_3$ vertices with degree 3 which not belong to any cycle such that $b+c_2+t_3 = 1$.

One element of $\widetilde{\mathcal{C}}(n, k)$ is shown in Figure 1 where $k$ is even, and three elements of $\widetilde{\mathcal{C}}(n, k)$ are shown in Figure 2 where $k$ is odd. Moreover, the graph of Type I in Figure 2 is an example graph with $c_2 = 1$ and $b = t_3 = 0$; the graph of Type II in Figure 2 is an example graph with $t_3 = 1$ and $c_2 = b = 0$; the graph of Type III in Figure 2 is an example graph with $b = 1$ and $c_2 = t_3 = 0$.

Remark. In ^[15], Wu et al. defined a set of cacti $\mathcal{C}^*(n, k)$ which was different with the set $\widetilde{\mathcal{C}}(n, k)$ in this paper. Actually, when $k$ is odd, the set $\mathcal{C}^*(n, k)$ in ^[15] contains two types of cacti meanwhile the set $\widetilde{\mathcal{C}}(n, k)$ in this paper contains three types of cacti. Furthermore, if $k$ is odd, the two types cacti of $\mathcal{C}^*(n, k)$ in ^[15] are just the cacti of the Types I and II in this paper.

Lemma 4.3. Let $H$ be a cactus in $\mathcal{C}(n, k)$ ($n\geq4k-2$ and $k\geq 2$) with minimum Sombor index. Then, $e_{3, 3}\leq\lfloor\frac{5k}{2}\rfloor-4$ with equality holds if and only if $H\in\widetilde{\mathcal{C}}(n, k)$.

Proof. By Lemmas 2.5 and 3.5, we have $2\leq d_{H}(v)\leq 3$ for each vertex $v$ in $H$. Let $c_1$ be the number of end blocks, $c_2$ be the number of the cycles which contains exactly two adjacent vertices whose degrees are not 2. By Corollary 3.3(ii), there are $c_3 = k-c_1-c_2$ cycles containing no vertex with degree 2, and let them be $C_1, C_2, \cdots, C_{c_3}$. Let $l_i = |V_{C_i}|$ for $i = 1, 2, \cdots, c_3$. Let $t_3$ be the number of vertices which does not lie on any cycle of $H$.

Let $T_H$ be the tree obtained by contracting each cycle of $H$ into a vertex. Then $|V_{T_H}| = k+t_3 = |E_{T_H}|+1$, and the degree sum of all vertices in $T_H$ is

Therefore,

and

Thus,

On the other hand, by Corollary 3.3, one has that

Combining (4.5), (4.6) and (4.7), we get

If $k$ is even, we obtain

with equality holds if and only if $t_3 = c_2 = 0$ and $l_i = 3$ for $i = 1, 2, \cdots, c_3$, that is $H\in\widetilde{\mathcal{C}}(n, k)$.

If $k$ is odd, we have

with equality holds if and only if either $t_3 = 0, c_2 = 1$ and $l_i = 3$ for $i = 1, 2, \cdots, c_3$ (i.e., $H$ is the graph of Type I in Figure 2), or $t_3 = 1, c_2 = 0$ and $l_i = 3$ for $i = 1, 2, \cdots, c_3$ (i.e., $H$ is the graph of Type II in Figure 2), or $t_3 = c_2 = 0$ and $\sum_{i = 1}^{c_3}{(l_i-3)} = 1$ (i.e., $H$ is the graph of Type III in Figure 2), that is $H\in\widetilde{\mathcal{C}}(n, k)$. □

In a similar manner with Lemma 4.3, the following Corollary 4.4 can be deduced.

Corollary 4.4. Let $H$ be a cactus in $\mathcal{C}(n, k)$ ($n\geq4k-2$ and $k\geq 2$) with minimum reduced Sombor index. Then, $e_{3, 3}\leq\lfloor\frac{5k}{2}\rfloor-4$ with equality holds if and only if $H\in\widetilde{\mathcal{C}}(n, k)$.

Proof of Theorem 1.1: From Corollary 4.2 and Lemma 4.3, one obtains that

Moreover, the equality holds if and only if $H\in\widetilde{\mathcal{C}}(n, k)$. □

Proof of Theorem 1.2: From Lemma 4.1 and Corollary 4.4, we get

Moreover, the equality holds if and only if $H\in\widetilde{\mathcal{C}}(n, k)$. □

5.   Conclusions

In this paper, the Sombor index and the reduced Sombor index on cacti with $n$ vertices and $k$ cycles are discussed. The minimum Sombor index on cacti with $n$ vertices and $k$ cycles ($n\geq 4k-2$ and $k\geq 2$) is obtained and the corresponding extremal cacti are characterized which improves the result of Wu et al. ^[15]. Moreover, the minimum reduced Sombor index of cacti with $n$ vertices and $k$ cycles ($n\geq 4k-2$ and $k\geq 2$) is obtained and the corresponding extremal cacti are characterized as well. For further study, it would be interesting to generalize the Theorems 1.1 and 1.2 to the case of $3k+1 \leq n \leq 4k-3$ and $k\geq 2$. Furthermore, it would be meaningful to study the Sombor index and the reduced Sombor index of other kinds of graphs.

Use of AI tools declaration

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

Acknowledgments

This research is supported by Tianjin Education Commission Research Program Project (No.2022KJ007). The authors would like to thank the anonymous reviewers for their valuable and kind suggestions which greatly improved the original manuscript.

Conflict of interest

The authors declare that they have no conflicts of interest.