Degree-based graphical indices of $k$-cyclic graphs

1.   Introduction

This paper considers only connected and simple graphs. For the basic terminology regarding graph theory, we refer the reader to the books ^[7,8,13].

Real-valued graph invariants are sometimes called graphical indices (or more frequently, topological indices) in chemical graph theory ^[35,38]. By utilizing some concepts from geometry, Gutman ^[16] put forward a novel perspective on vertex-degree-based graphical indices and introduced the Sombor index. For any graph $G$, its Sombor index is given as follows:

where $E(G)$ consists of edges of $G$ and $d_u$ is the degree of vertex $u\in V(G)$. When two or more graphs are under consideration, we write $d_u(G)$ to denote the degree of vertex $u\in V(G)$ in $G$. We refer the reader to the articles ^[24,29] for some applications of the SO index and to review articles ^[15,26] for various properties associated with this index.

Quite recently, Gutman, Furtula, and Oz ^[18] proposed a new geometric method for designing graphical indices and introduced the elliptic Sombor (ESO) index. The ESO index of $G$ is defined as

Information on some of the known mathematical properties of the ESO index can be found in the recent papers ^[27,28,34].

Another graphical index designed by the method outlined in ^[18] is the Euler-Sombor (EU) index ^[17,33], which is generated using Euler's formula for approximating the perimeter of an ellipse. The mathematical form of the EU index is

Several existing mathematical aspects of the EU index can be found in ^[1,20,32].

In the definition of the ESO index, if one replaces the sum "$d_u+d_v$" of the degrees of the end vertices of the edge $uv$ with the product "$d_u\, d_v$" of the aforementioned degrees, then the so-called Zagreb-Sombor (ZSO) index ^[5,6] is obtained:

The SO, ESO, EU, and ZSO indices are special cases of the following general form ^[14,19,37] of certain graphical indices:

where $\Psi$ is a symmetric function (defined on the degree set of $G$) whose outputs are real numbers. (The degree set of a graph is the set of all different degrees of its vertices.) Vukičević and Đurđević ^[36] coined the name "bond incident degree indices", say BID indices in short, for the indices of the form (1.1). Many existing results associated with BID indices were reported in the papers ^[9,39,40].

A connected graph having order $n$ and size $n+\mu-1$ is named as an $n$-order $\mu$-cyclic graph, where $\mu$ is a nonnegative integer. A graph whose maximum degree does not exceed $4$ is known as a molecular graph. In this paper, we study the problem of characterizing graphs minimizing or maximizing $\mathcal{BID}_{\Psi}$ (defined via (1.1)) among all $k$-cyclic graphs, with a given order, under certain constraints on $\Psi$. The obtained results help in solving similar problems for many particular BID indices.

2.   Extremal graphs possessing degree set $\{2, 3\}$

Let $G$ be a given graph. Let $G'$ be a graph obtained from $G$ by applying a transformation such that $V(G) = V(G')$. Throughout this section, whenever such two graphs are under consideration, $d_v$ denotes the degree of vertex $v\in V(G')$ in $G$.

The known result presented below is due to Hu et al. ^[21].

Theorem 1. ^[21] Let $G$ be an $n$-order non-trivial graph of size $m\ge1$. If $\Psi(x_1, x_2)$ is a real-valued convex symmetric function such that the partial derivative $\partial\Psi/\partial x_1$ of $\Psi$ with respect to $x_1$ exists and is non-negative, then

The equality in (2.1) is attained if $G$ is regular.

Although Theorem 1 yields a nice lower bound on $\mathcal{BID}_{\Psi}$ for $n$-order graphs of size $m$, we are not able to deduce from it graphs minimizing $\mathcal{BID}_{\Psi}$ in the set of $n$-order $\mu$-cyclic graphs, except for the case $\mu = 1$.

Define $m_{\alpha, \beta} = |\{xy\in E(G):d_x = \alpha, \; d_y = \beta\}|$. Now, we recall a result of Liu et al. ^[25], which is applicable in characterizing graphs minimizing many BID indices, including the EU index (see ^[1]), among $n$-order $\mu$-cyclic graphs for $n\ge 5(\mu-1)$ and $\mu\ge3$.

Theorem 2. ^[25] Let $\Psi(x_1, x_2)$, with $x_1\ge1$ and $x_2\ge1$, be a real-valued symmetric function satisfying the following:

(ⅰ) $\Psi$ is increasing in $x_1$ (and hence in $x_2$).

(ⅱ) $f$ defined as $f(x) = \Psi(a, x) - \Psi(b, x)$, with $x\ge1$ and $a > b \ge 0$, is strictly decreasing.

(ⅲ) If $a > b + 1 \ge 2$, then

Indicate by $\mathcal{G}_{n, \mu}$ the collection of $n$-order $\mu$-cyclic graphs having degree set $\{2, 3\}$ and satisfying $m_{2, 3} = 2$, $m_{2, 2} = n - 2\mu + 1, \; m_{3, 3} = 3\mu - 4$. Among $n$-order $\mu$-cyclic graphs, with $\mu\ge3$ and $n\ge 5(\mu-1)$, only the member(s) of $\mathcal{G}_{n, \mu}$ minimize(s) $\mathcal{BID}_{\Psi}$.

If we take $\Psi(x_1, x_2) = (x_1+x_2)\sqrt{x_1^2+x_2^2}$ or $\Psi(x_1, x_2) = (x_1\, x_2)\sqrt{x_1^2+x_2^2}$, or $\Psi(x_1, x_2) = (x_1\, x_2)^{3/2}$, with $x_2\ge1$ and $x_1\ge1$, then constraint number (ⅱ) of Theorem 2 does not hold for any of these choices of $\Psi$. Hence, Theorem 2 does not cover any of the three BID indices corresponding to the aforementioned choices of $\Psi$.

The above-mentioned observations motivated us to establish the rest of the results of the present section.

A nontrivial path $P:x_1x_2...x_t$ in a graph $G$ is said to be pendent path if $\min\{d_{x_1}(G), d_{x_t}(G)\} = 1$, $\max\{d_{x_1}(G), d_{x_t}(G)\}\ge3$, and $d_{x_i}(G) = 2$ whenever $2\le i\le t-1$. Let $\mathbb{R}_{\ge1}$ be the set of all real numbers greater than or equal to $1$.

Lemma 1. Let $\Psi$ be a real-valued symmetric function defined on $\mathbb{R}_{\ge1}\times \mathbb{R}_{\ge1}$ such that the following two conditions hold:

(ⅰ) $f$ defined as $f(x) = \Psi(c_1, x)-\Psi(c_2, x)$ with $x\ge1$ is increasing, where $c_1$ and $c_2$ are integers satisfying $c_1 > c_2\ge2$.

(ⅱ) The following inequalities hold for every integer $c\ge3$:

If a graph $G$ minimizes $\mathcal{BID}_\Psi$ among $n$-order $\mu$-cyclic graphs, then $G$ does not contain any pendent path.

Proof. Contrarily, assume that the conclusion of the lemma does not hold. Let $zx_1x_2...x_t$ be a pendent path of $G$, with $d_z \ge 3$. Take $y\in V(G)\setminus\{x_1\}$ in such a way that $yz\in E(G)$. Let $G'$ denote the graph constructed from $G$ by inserting edge $x_ty$ and dropping the edge $zy$. The case $t = 1$ yields a contradiction because, by condition (ⅰ) and inequality (2.2), we have

If $t \ge 2$, then by condition (ⅰ) and inequality (2.3), we have

a contradiction again. □

The proof of the subsequent result is very similar to that of Lemma 1, and so we omit it.

Lemma 2. Let $\Psi$ be a real-valued symmetric function defined on $\mathbb{R}_{\ge1}\times \mathbb{R}_{\ge1}$ such that the following two conditions hold:

(ⅰ) $f$ defined as $f(x) = \Psi(c_1, x)-\Psi(c_2, x)$ with $x\ge1$ is decreasing, where $c_1$ and $c_2$ are integers satisfying $c_1 > c_2\ge2$.

(ⅱ) The following inequalities hold for every integer $c\ge3$:

If a graph $G$ maximizes $\mathcal{BID}_\Psi$ among $n$-order $\mu$-cyclic graphs, then $G$ does not contain any pendent path.

Lemma 1 provides the following.

Corollary 1. If $\Psi$ is the function defined in Lemma 1 such that $\Psi$ meets the constraints listed therein, then the path/cycle graph uniquely minimizes $\mathcal{BID}_\Psi$ among $n$-order trees/unicyclic graphs, respectively, for every $n\ge4$.

Corollary 1 covers the EU index; the corresponding results regarding the EU index have recently been derived in ^[1,22,32].

Lemma 2 provides the following.

Corollary 2. If $\Psi$ is the function defined in Lemma 2 such that $\Psi$ meets the constraints listed therein, then the path/cycle graph uniquely maximizes $\mathcal{BID}_\Psi$ among $n$-order trees/unicyclic graphs, respectively, for every $n\ge4$.

For a graph $G$ and its vertex $v$, define $n_{r} = |\{x\in V(G): d_x = r\}|$ and $N(v) = \{w\in V(G): wv\in E(G)\}$. The members of $N(v)$ are called neighbors of $v$. Corollaries 1 and 2 provide extremal results concerning $\mathcal{BID}_{\Psi}$ under certain constraints on $\Psi$ for fixed-order $\mu$-cyclic graphs when $\mu\in\{0, 1\}$. Next, we establish similar results for $\mu\ge2$.

Lemma 3. Let $\Psi$ be the function defined in Lemma 1 such that $\Psi$ meets the constraints listed therein. Additionally, let

and

for every integer $c\ge4$. If a graph $G$ minimizes $\mathcal{BID}_{\Psi}$ among $n$-order $\mu$-cyclic graphs, with $\mu\ge2$, $n\ge5$, and $n\ge 2(\mu-1)$, then the maximum degree of $G$ is $3$.

Proof. By Lemma 1, $G$ contains no pendent vertex. Let $\Delta$ denote $G$'s maximum degree. The inequality $\mu\ge2$ forces that $\Delta\ge3$. Contrarily, we assume that $\Delta\ge4$. Let $m = |E(G)|$. Then, $\mu-1 = m-n$, and thus

which implies that

Inequality (2.6) ensures that $n_2\ge1$. Let $u\in V(G)$ be a vertex of degree $\Delta$.

Case 1. $u$ possesses a neighbor, say $w$, with degree $2$.

Certainly, the vertex $w$ is not a neighbor of at least one neighbor, say $v$, of $u$. Let $G'$ denote the graph constructed from $G$ by inserting the edge $vw$ and dropping the edge $vu$. Let $t(\ne u)$ denote the other neighbor of $w$. By condition (i) of Lemma 1 and inequality (2.4), we have

a contradiction.

Case 2. No neighbor of $u$ has degree $2$.

In this case, every neighbor of $u$ has degree greater than $2$. Note that there exists at least one vertex $w'\in V(G)\setminus N(u)$ having degree $2$ that is not a neighbor of at least two neighbors of $u$. Among these neighbors of $u$, we pick $v'$ provided that the graph $G"$ is connected, where $G"$ is the graph constructed from $G$ by inserting the edge $v'w'$ and dropping the edge $v'u$. By condition (ⅰ) of Lemma 1 and inequality (2.5), we have

a contradiction again. □

Since the following lemma can be proved in a fully analogous way to that of Lemma 3, we omit its proof.

Lemma 4. Let $\Psi$ be the function defined in Lemma 2 such that $\Psi$ meets the constraints listed therein. Additionally, let

and

for every integer $c\ge4$. If a graph $G$ maximizes $\mathcal{BID}_{\Psi}$ among $n$-order $\mu$-cyclic graphs, with $\mu\ge2$, $n\ge5$, and $n\ge 2(\mu-1)$, then the maximum degree of $G$ is $3$.

Theorem 3. Let $\Psi$ be the function defined in Lemma 1 such that $\Psi$ satisfies the constraints listed therein, and that inequalities (2.4) and (2.5) hold. If a graph $G$ minimzes $\mathcal{BID}_\Psi$ among $n$-order $\mu$-cyclic graphs, with $\mu\ge2$, $n\ge5$ and $n\ge 2(\mu-1)$, then the degree sequence of $G$ is

Proof. By Lemmas 1 and 3, the degree set of $G$ is either $\{2, 3\}$ or $\{3\}$. Now, the equations $n_2+n_3 = n$ and $2n_2+3n_3 = 2(n+\mu-1)$ yield $n_2 = n-2(\mu-1)$ and $n_3 = 2(\mu-1)$. □

Remark 1. Since each of the functions associated with the elliptic Sombor index and Zagreb-Sombor index satisfies both the constraints listed in Lemma 1 as well as inequalities (2.4) and (2.5), Theorem 3 holds for both of these indices. Also, we have verified that each of the functions associated with the first ten indices given in Table 5.1 of ^[10] satisfies both the constraints listed in Lemma 1 as well as inequalities (2.4) and (2.5). Hence, Theorem 3 also covers these ten indices. (We provide a few comments concerning the main results derived in ^[10] at the end of the present section.)

Using Lemmas 2 and 4, we establish the next result.

Theorem 4. Let $\Psi$ be the function defined in Lemma 2 such that $\Psi$ satisfies the constraints listed therein, and that inequalities (2.7) and (2.8) hold. If a graph $G$ maximzes $\mathcal{BID}_\Psi$ among $n$-order $\mu$-cyclic graphs, with $\mu\ge2$, $n\ge5$, and $n\ge 2(\mu-1)$, then the degree sequence of $G$ is

If $n = 2(\mu-1)$, then one obtains the exact structure of the extremal graphs given Theorems 3 and 4. Particularly, such graphs are $3$-regular when $n = 2(\mu-1)$. In what follows, we study the structure of the mentioned extremal graphs for the case $n > 2(\mu-1)$.

Lemma 5. Let $G$ be an $n$-order $\mu$-cyclic graph having degree set $\{2, 3\}$, where $\mu\ge2$, $n\ge5$, and $n > 2(\mu-1)$.

(a) If $2(\mu-1) < n < 5(\mu-1)$, then $m_{3, 3}\ne0$.

(b) If $n > 5(\mu-1)$, then $m_{2, 2}\ne0$.

(c) If $n = 5(\mu-1)$, then $m_{3, 3} = m_{2, 2}$.

Proof. (a) Note that $n_2 = n-2(\mu-1)$ and $n_3 = 2(\mu-1)$, which yield $2n_2 < 3n_3$ because $n < 5(\mu-1)$. If $m_{3, 3} = 0$, then we obtain $3n_3\le 2m_{2, 2}+3n_3 = 2n_2$, a contradiction. For the proofs of parts (b) and (c), see the proof of Lemma 15 in ^[4]. □

Lemma 6. Let $\Psi$ be the function defined in Lemma 1 such that $\Psi$ satisfies the constraints listed therein, and that inequalities (2.4) and (2.5) hold. Additionally, assume that $\Psi(3, 3)+\Psi(2, 2)-2\Psi(2, 3) > 0$. If a graph $G$ minimizes $\mathcal{BID}_\Psi$ among $n$-order $\mu$-cyclic graphs, with $\mu\ge2$ and $n > 5(\mu-1)$, then either $d_x = 2$ or $d_y = 2$ for every $xy\in E(G)$.

Proof. By Lemmas 1, 3, and 5, $G$ possesses degree set $\{2, 3\}$, and it holds that $m_{2, 2}\ne0$. Consider $uv\in E(G)$ provided that $2 = d_v = d_u$. Contrarily, assume that there exists $wt\in E(G)$ such that $d_w = d_t = 3$. Take $N(v) = \{u, x\}$. One may have that $x\in\{w, t\}$; however, in this scenario, we assume that $x = t$, without loss of generality.

Case 1. $u$ and $v$ do not lie on a triangle.

In this case, we have $ux\not\in E(G)$. If $G'$ denotes the graph constructed from $G$ by dropping the edges $vu, vx, wt$ and inserting the edges $ux, wv, tv,$ then

which contradicts the definition of $G$.

Case 2. $u$ and $v$ lie on a triangle.

In this case, we have $ux\in E(G)$ and $d_x = 3$. If the vertices $x$ and $t$ are distinct, then the graph $G"$ constructed from $G$ by dropping the edges $tw, vx$ and inserting the edges $xw, tv,$ satisfies $\mathcal{BID}_\Psi(G") = \mathcal{BID}_\Psi(G)$. Since $u$ and $v$ do not lie on a triangle in $G"$, by Case 1, we arrive at a contradiction. If the vertices $x$ and $t$ are the same, then the graph $G"'$ constructed from $G$ by dropping the edges $ww_1, vt$ and inserting the edges $tw_1, wv,$ satisfies $\mathcal{BID}_\Psi(G"') = \mathcal{BID}_\Psi(G)$, where $w_1\ne t$ is a neighbor of $w$. Since $u$ and $v$ do not lie on a triangle in $G"'$, by Case 1, we arrive at a contradiction. □

Since the subsequent lemma may be proved in a completely analogous way to that of Lemma 6, we omit its proof.

Lemma 7. Let $\Psi$ be the function defined in Lemma 2 such that $\Psi$ satisfies the constraints listed therein, and that inequalities (2.7) and (2.8) hold. Additionally, assume that $\Psi(3, 3)+\Psi(2, 2)-2\Psi(2, 3) < 0$. If a graph $G$ maximizes $\mathcal{BID}_\Psi$ among $n$-order $\mu$-cyclic graphs, with $\mu\ge2$ and $n > 5(\mu-1)$, then either $d_x = 2$ or $d_y = 2$ for every $xy\in E(G)$.

Lemma 8. Let $\Psi$ be the function defined in Lemma 1 such that $\Psi$ satisfies the constraints listed therein, and that inequalities (2.4) and (2.5) hold. Additionally, assume that $\Psi(3, 3)+\Psi(2, 2)-2\Psi(2, 3) > 0$. If a graph $G$ minimizes $\mathcal{BID}_\Psi$ among $n$-order $\mu$-cyclic graphs, with $\mu\ge2$ and $n = 5(\mu-1)$, then $\{2, 3\} = \{d_x, d_y\}$ for every $xy\in E(G)$.

Proof. By Lemmas 1, 3, and 5, the degree set of $G$ is $\{2, 3\}$, and it holds that $m_{3, 3} = m_{2, 2}$. If $m_{2, 2}\ne0\ne m_{3, 3}$, then by the proof of Lemma 6, we find a graph $G'$ that is $\mu$-cyclic $n$-order such that $\mathcal{BID}_{\Psi}(G) > \mathcal{BID}_{\Psi}(G')$, which yields a contradiction. □

Since the subsequent lemma may be proved in a completely analogous way to that of Lemma 8, we omit its proof.

Lemma 9. Let $\Psi$ be the function defined in Lemma 2 such that $\Psi$ satisfies the constraints listed therein, and that inequalities (2.7) and (2.8) hold. Additionally, assume that $\Psi(3, 3)+\Psi(2, 2)-2\Psi(2, 3) < 0$. If a graph $G$ maximizes $\mathcal{BID}_\Psi$ among $n$-order $\mu$-cyclic graphs, with $\mu\ge2$ and $n = 5(\mu-1)$, then $\{2, 3\} = \{d_x, d_y\}$ for every $xy\in E(G)$.

Lemma 10. Let $\Psi$ be the function defined in Lemma 1 such that $\Psi$ satisfies the constraints listed therein, and that inequalities (2.4) and (2.5) hold. Additionally, assume that $\Psi(3, 3)+\Psi(2, 2)-2\Psi(2, 3) > 0$. If a graph $G$ minimizes $\mathcal{BID}_\Psi$ among $n$-order $\mu$-cyclic graphs, with $\mu\ge3$ and $2(\mu-1) < n < 5(\mu-1)$, then $m_{2, 2} = 0$.

Proof. By Lemmas 1, 3, and 5, the degree set of $G$ is $\{2, 3\}$, and it holds that $m_{3, 3}\ne0$. If $m_{2, 2}\ne0$, then, by the proof of Lemma 6, we find an $n$-order $\mu$-cyclic graph $G'$ such that $\mathcal{BID}_{\Psi}(G) > \mathcal{BID}_{\Psi}(G')$, which yields a contradiction. □

Since the proof of the subsequent lemma is completely analogous to that of Lemma 10, we omit it.

Lemma 11. Let $\Psi$ be the function defined in Lemma 2 such that $\Psi$ satisfies the constraints listed therein, and that inequalities (2.7) and (2.8) hold. Additionally, assume that $\Psi(3, 3)+\Psi(2, 2)-2\Psi(2, 3) < 0$. If a graph $G$ maximizes $\mathcal{BID}_\Psi$ among $n$-order $\mu$-cyclic graphs, with $\mu\ge3$ and $2(\mu-1) < n < 5(\mu-1)$, then $m_{2, 2} = 0$.

Theorem 5. Let $\Psi$ be the function defined in Lemma 1 such that $\Psi$ satisfies the constraints listed therein, and that inequalities (2.4) and (2.5) hold. Additionally, assume that $\Psi(3, 3)+\Psi(2, 2)-2\Psi(2, 3) > 0$. Then, among $n$-order $\mu$-cyclic graphs,

(a) only the graphs with degree set $\{2, 3\}$ such that $m_{2, 2} = 0$ minimize $\mathcal{BID}_\Psi$ for $2(\mu-1) < n < 5(\mu-1)$ and $\mu\ge3$;

(b) only the graphs with degree set $\{2, 3\}$ such that $m_{2, 2} = 0 = m_{3, 3}$ minimize $\mathcal{BID}_\Psi$ for $n = 5(\mu-1)$ and $\mu\ge2$;

(c) only the graphs with degree set $\{2, 3\}$ such that $m_{3, 3} = 0$ minimize $\mathcal{BID}_\Psi$ for $n > 5(\mu-1)$ and $\mu\ge2$.

Proof. Assume that $G$ is a graph minimizing $\mathcal{BID}_\Psi$ among $\mu$-cyclic $n$-order graphs, with $n > 2(\mu-1)$, $\mu\ge2$, and $n\ge5$. Thanks to Lemmas 1 and 3, the degree set of $G$ is $\{2, 3\}$.

(a) This part follows from Lemma 10.

(b) This part follows from Lemma 8.

(c) This part follows from Lemma 6. □

Since the subsequent theorem may be proved in a completely analogous way to that of Theorem 5, we omit its proof.

Theorem 6. Let $\Psi$ be the function defined in Lemma 2 such that $\Psi$ satisfies the constraints listed therein, and that inequalities (2.7) and (2.8) hold. Additionally, assume that $\Psi(3, 3)+\Psi(2, 2)-2\Psi(2, 3) < 0$. Then, among $n$-order $\mu$-cyclic graphs,

(a) only the graphs with degree set $\{2, 3\}$ such that $m_{2, 2} = 0$ maximize $\mathcal{BID}_\Psi$ for $2(\mu-1) < n < 5(\mu-1)$ and $\mu\ge3$;

(b) only the graphs with degree set $\{2, 3\}$ such that $m_{2, 2} = 0 = m_{3, 3}$ maximize $\mathcal{BID}_\Psi$ for $n = 5(\mu-1)$ and $\mu\ge2$;

(c) only the graphs with degree set $\{2, 3\}$ such that $m_{3, 3} = 0$ maximize $\mathcal{BID}_\Psi$ for $n > 5(\mu-1)$ and $\mu\ge2$.

Remark 2. Recall that a graph in which every vertex has a degree smaller than $5$ is called a molecular graph. If we replace the text "$\mu$-cyclic graphs" with "$\mu$-cyclic molecular graphs" in the statements of Theorems 5 and 6, then the modified results are also valid.

Remark 3. If an $n$-order $\mu$-cyclic graph has size $m$, then $\mu = m -n +1$, and thus Theorems 5 and 6 can be stated in terms of order and size of graphs.

Remark 4. Since each of the functions associated with the elliptic Sombor index and Zagreb-Sombor index meets all the constraints mentioned in Theorem 5, this result holds for both of these indices.

Remark 5. In the definition of the ESO index, by replacing the degrees $d_u$ and $d_v$ of the end vertices of the edge $uv$ with $d_u-1$ and $d_v-1$, respectively, we obtain

Using the existing terminology of reduced graphical indices, we refer to the index $\mathcal{RES}$ as the reduced elliptic Sombor (RES) index. We note that the function $\Psi(x_1, x_2) = (x_1+x_2-2)\sqrt{(x_1-1)^2+(x_2-1)^2}$ satisfies all the constraints of Theorem 5, and hence this theorem covers the RES index.

Here, we point out that the recent paper ^[10] contains several general results similar to Theorems 3–6. In order to demonstrate the difference between the main results of this section and the main results established in ^[10], we consider the following index, which is not covered by any of the aforementioned results of ^[10]:

Since the function $\Psi(x_1, x_2) = (x_1\, x_2)^{3/2}$ satisfies all the constraints of Theorems 3 and 5, the conclusions of these theorems hold for the index $R_{3/2}$. On the other hand, it is interesting to note that none of the theorems of the present section covers any of the last five indices of Table 5.1 of ^[10].

In the same way as we defined the RES index in Remark 5, we now define the reduced Zagreb-Sombor (RZS) index:

It seems that none of the main results of ^[10,25] and the present section covers the RZS index. Actually, there are many well-known graphical indices (for instance, the reduced second Zagreb index ^[11] and the irregularity ^[12]) that are not covered by any of the main results of the aforementioned papers and section. Hence, it would be interesting to extend the results of ^[10,25] and the present section in such a way that the extended result(s) cover(s) such indices.

3.   Extremal graphs possessing universal vertices

In an $n$-order graph, a vertex of degree $n-1$ is called a universal vertex. The following two lemmas are obtained by utilizing Lemma 2.1 of ^[3].

Lemma 12. Let $\Psi$ be a real-valued symmetric function defined on $\mathbb{R}_{\ge1}\times \mathbb{R}_{\ge1}$ such that its partial derivative function $\Psi_{x_i}$ with respect to $x_i$ exists for $i = 1, 2$, $\Psi$ as well as $\Psi_{x_i}$ are increasing in $x_i$ for $i = 1, 2$, and the inequality $\Psi(x_1+k, x_2-k)-\Psi(x_1, x_2)\ge 0$ holds for $x_1\ge x_2\ge k+1\ge2$. Also, assume that at least one of the following constraints holds:

(ⅰ) $\Psi(x_1, x_2)$ is strictly increasing in $x_i$ for $i = 1, 2$.

(ⅱ) $\Psi_{x_i}$ is strictly increasing in $x_i$ for $i = 1, 2$.

(ⅲ) $\Psi(x_1+k, x_2-k)-\Psi(x_1, x_2) > 0$ for $x_1\ge x_2\ge k+1\ge2$.

If a graph $G$ maximizes $\mathcal{BID}_\Psi$ among $\mu$-cyclic $n$-order graphs, then $G$ has at least one universal vertex.

Lemma 13. Let $\Psi$ be a real-valued symmetric function defined on $\mathbb{R}_{\ge1}\times \mathbb{R}_{\ge1}$ such that its partial derivative function $\Psi_{x_i}$ with respect to $x_i$ exists for $i = 1, 2$, and $\Psi$ as well as $\Psi_{x_i}$ are decreasing in $x_i$ for $i = 1, 2$, and the inequality $\Psi(x_1+k, x_2-k)-\Psi(x_1, x_2)\le 0$ holds for $x_1\ge x_2\ge k+1\ge2$. Also, assume that at least one of the following constraints holds:

(ⅰ) $\Psi(x_1, x_2)$ is strictly decreasing in $x_i$ for $i = 1, 2$.

(ⅱ) $\Psi_{x_i}$ is strictly decreasing in $x_i$ for $i = 1, 2$.

(ⅲ) $\Psi(x_1+k, x_2-k)-\Psi(x_1, x_2) < 0$ for $x_1\ge x_2\ge k+1\ge2$.

If a graph $G$ minimizes $\mathcal{BID}_\Psi$ among $\mu$-cyclic $n$-order graphs, then $G$ has at least one universal vertex.

Lemmas 12 and 13 provide the next result.

Corollary 3. Let $\Psi$ be the function defined in Lemma 12 (Lemma 13, respectively) such that it meets all the constraints given therein. Then, the star $S_n$ uniquely maximizes (minimizes, respectively) $\mathcal{BID}_\Psi$ among $n$-order trees for every $n\ge4$. Also, the unicyclic graph generated by putting a single edge in $S_n$ uniquely maximizes (minimizes, respectively) $\mathcal{BID}_\Psi$ among $n$-order unicyclic graphs for $n\ge4$.

For a vertex $w$ in a graph $G$, we take $N(w)\cup\{w\} = N[w]$.

Lemma 14. Let $\Psi$ be the function defined in Lemma 12 such that it meets all the constraints given therein. Let $G$ be a graph maximizing $\mathcal{BID}_\Psi$ over the class of $n$-order $\mu$-cyclic graphs, where $2\le\mu\le n-2$. If the vertices $u, v$ are non-pendent in $G$ such that $d_u \le d_v$, then every neighbor of $u$ distinct from $v$ is a neighbor of $v$.

Proof. (Note that $N(u)\ne N[v]$ for every two vertices $u$ and $v$ in any $G$.) Because of the constraints of Lemma 12, the proof of the present result is almost the same as that of Lemma 2.3 reported in ^[30]; the second summation in Equation (3) of the mentioned proof should be taken over $N(v)\setminus N[u]$ instead of $N(v)\setminus N(u)$. □

The subsequent lemma's proof is completely analogous to that of the previous result, and so we omit it.

Lemma 15. Let $\Psi$ be the function defined in Lemma 13 such that it meets all the constraints given therein. Let $G$ be a graph minimizing $\mathcal{BID}_\Psi$ over the class of $n$-order $\mu$-cyclic graphs, where $2\le \mu\le n-2$. If the vertices $u, v$ are non-pendent in $G$ such that $d_u \le d_v$, then every neighbor of $u$ distinct from $v$ is a neighbor of $v$.

Lemma 16. Let $\Psi$ be the function defined in Lemma 12 such that it meets all the constraints given therein. Let $G$ satisfy the constraints mentioned in the 2nd sentence of Lemma 14. If $V(G) = \{x_1, x_2, \dots, x_n \}$ and $d_{x_n}\leq \cdots \le d_{x_2}\leq d_{x_1}$, then every non-pendent vertex (different from $x_2$) of $G$ is a neighbor of $x_2$.

Proof. By Lemma 12, $d_{x_1} = n-1$. Suppose, contrarily, that $x_k$ is a non-pendent vertex that is not a neighbor of $x_2$ for some $k\in\{3, 4, \dots, n\}$. Then, $d_{x_2}\le n-2$. Since every pendent vertex (if it exists) is a neighbor of $x_1$, the vertex $x_k$ has a non-pendent neighbor $x_r$ for some $r\in\{3, 4, \dots, n\}\setminus\{k\}$. Since $d_{x_2}\ge d_{x_r}$, by Lemma 14, the vertex $x_k$ is a neighbor of $x_2$, which is a contradiction. □

The subsequent lemma's proof is completely analogous to that of the previous result (that is, Lemma 16), and so we omit it.

Lemma 17. Let $\Psi$ be the function defined in Lemma 13 such that it meets all the constraints given therein. Let $G$ satisfy constraints mentioned in the 2nd sentence of Lemma 15. If $V(G) = \{x_1, x_2, \dots, x_n \}$ and $d_{x_n}\leq \cdots \le d_{x_2}\leq d_{x_1}$, then every non-pendent vertex (different from $x_2$) of $G$ is a neighbor of $x_2$.

For $\mu\ge1$, let $H_{n, \mu}$ be the $n$-order graph formed by putting $\mu$ edge(s) to the star graph $S_n$ between a certain vertex with degree one and $\mu$ other vertex/vertices with degree one. For $\mu\ge3$, let $H_{n, \mu}'$ indicate the graph generated by putting a single edge to $H_{n, \mu-1}$ betwixt two vertices of degree $2$.

Theorem 7. Let $\Psi$ be the function defined in Lemma 12 such that it meets all the constraints given therein. In the graph class mentioned in Lemma 14, let $G$ be a graph maximizing $\mathcal{BID}_\Psi$ such that $n\ge \mu+2$ and $\mu\in\{2, 3, 4, 5\}$.

(i) If $\mu = 2$, then $G = H_{n, \mu}$.

(ii) If $\mu \in\{3, 4\}$, then either $G = H_{n, \mu}$ or $G = H_{n, \mu}'$.

(iii) If $\mu = 5$, then $G\in\{H_{n, 5}', H_{n, 5}, H_{n, 5}"\}$, where $H_{n, 5}"$ is the graph generated from $H_{n, 4}'$ by putting a single edge betwixt a vertex with degree $3$ and another vertex with degree $2$.

Proof. Let the vertices of $G$ be $u_1, u_2, \dots, u_n$ such that $d_{u_1}\geq d_{u_2}\geq \dots \geq d_{u_n}$. By Lemma 12, $d_{u_1} = n-1$. For every $\mu\in \{2, 3, 4\}$, all $n$-order $\mu$-cyclic graphs of maximum degree $n-1$ can be found in ^[3]. Also, all $n$-order $5$-cyclic graphs of maximum degree $n-1$ can be found in ^[2]. By Lemma 16, every non-pendent vertex (different from $u_2$) of $G$ is a neighbor of $u_2$; applying this fact on all aforementioned graphs of maximum degree $n-1$ yields the required conclusions for every $\mu\in\{2, 3, 4, 5\}$. □

In the same way as we defined the RES index in Remark 5, we now define the reduced Euler-Sombor (REU) index:

We note that each of the functions associated with the SO index, reduced Sombor (RSO) index, EU index, and REU index satisfies all the constraints of Lemma 12, and hence the conclusions of Corollary 3 (corresponding to Lemma 12) and Theorem 7 hold for these indices, where the RSO index is defined ^[16] as

If $\mathcal{BID}_\Psi$ is any of the SO, EU, RSO, and REU indices, then we obtain $\mathcal{BID}_\Psi(H_{n, \mu}) > \mathcal{BID}_\Psi(H_{n, \mu}')$ for $n\ge \mu+2$ and $\mu\in\{3, 4, 5\}$, and also $\mathcal{BID}_\Psi(H_{n, 5}) > \mathcal{BID}_\Psi(H_{n, 5}")$ for $n\ge 7$. Therefore, by Corollary 3 and Theorem 7, we have the following result.

Corollary 4. If $\mathcal{BID}_\Psi$ is any of the SO, EU, RSO and REU indices, then $H_{n, \mu}$ uniquely maximizes $\mathcal{BID}_\Psi$ among $n$-order $\mu$-cyclic graphs for $\mu\in\{0, 1, 2, 3, 4, 5\}$, $n\ge\mu+2$, and $n\ge4$, where $H_{n, 0}$ is the $n$-order star graph.

Corollary 4 covers some results regarding the EU index reported in ^[23,31].

The subsequent theorem's proof is completely analogous to that of the previous result (that is, Theorem 7), and so we omit it.

Theorem 8. Let $\Psi$ be the function defined in Lemma 13 such that it meets all the constraints given therein. In the graph class mentioned in Lemma 15, let $G$ be a graph minimizing $\mathcal{BID}_\Psi$, such that $n\ge \mu+2$ and $\mu\in\{2, 3, 4, 5\}$.

(i) If $\mu = 2$, then $G = H_{n, \mu}$.

(ii) If $\mu \in\{3, 4\}$, then either $G = H_{n, \mu}$ or $G = H_{n, \mu}'$.

(iii) If $\mu = 5$, then $G\in\{H_{n, 5}', H_{n, 5}, H_{n, 5}"\}$.

Author contributions

Investigation: Abdulaziz M. Alanazi, Abdulaziz Mutlaq Alotaibi, Taher S. Hassan; Methodology: Akbar Ali, Darko Dimitrov, Tamás Réti; Writing – original draft: Akbar Ali, Darko Dimitrov, Tamás Réti; Validation: Abdulaziz M. Alanazi, Abdulaziz Mutlaq Alotaibi, Taher S. Hassan; Writing – review & editing: Akbar Ali, Darko Dimitrov, Tamás Réti. All authors have read and approved the final version of the manuscript for publication.

Use of Generative-AI tools declaration

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

Acknowledgments

This study is supported via funding from Prince Sattam bin Abdulaziz University, Saudi Arabia (project number PSAU/2025/R/1446).

Conflict of interest

The authors have no conflicts of interest to declare.