Sharp bounds for the general Randić index of graphs with fixed number of vertices and cyclomatic number

1.   Introduction

We only consider finite and undirected graphs throughout this paper. Let $G = (V(G), E(G))$ be a graph with $n = |V(G)|$ vertices and $m = |E(G)|$ edges. For any vertex $u\in V(G)$, we use $d_{G}(u)$ (or $d_{u}$ when no confusion can arise) to denote the degree of $u$ in $G$, which is the number of edges incident to $u$. Such a maximal number (resp. minimal number) is called the maximal degree $\Delta(G)$ (resp. minimal degree $\delta(G)$). For any vertex $u$ in $G$, we use $N_{G}(u)$ to denote the set of all vertices adjacent with $u$, and the elements of $N_{G}(u)$ are called neighbors of $u$. A sequence of positive integers $\pi = (d_{1}, d_{2}, \ldots, d_{n})$ is called the degree sequence of $G$ if $d_{i} = d_{v_{i}}$ for any vertex $v_{i}\in V(G)$, where $i = 1, 2, \ldots, n$.

The join of two graphs $G_{1}$ and $G_{2}$, denoted by $G_{1}+G_{2}$, is the graph with the vertex set $V(G_{1})\cup V (G_{2})$ and edge set $E(G_{1})\cup E(G_{2})\cup \{xy|x\in V(G_{1}), y\in V(G_{2})\}$. The cyclomatic number of $G$ is the minimum number of edges in it whose removal makes it acyclic, denoted by $\gamma = \gamma(G)$. Let $\mathscr{G}_{n}^{\gamma}$ be the set of $n$-vertex graphs with cyclomatic number $\gamma$. We use $K_n$ and $P_{n}$ to denote the complete graph and path of $n$ vertices, respectively. As usual, we use the symbol $\ell(P_{n})$ to denote the length of the path $P_{n}$, which equals to the number of edges in $P_{n}$. The cyclomatic number, denoted by $\gamma$, of a graph $G$ is the minimum number of edges of $G$ whose removal makes $G$ acyclic. Let $\mathscr{G}_{n}^{\gamma}$ be the class of all connected graphs with order $n$ and cyclomatic number $\gamma$. We use ^[4] for terminology and notation not defined here.

The topological index is a real number that can be used to characterize the properties of the molecule graph. Nowadays, hundreds of topological indices have been considered and used in quantitative structure-activity and quantitative structure-property relationships. One of the well-known topological indices is the general Randić index, which was defined by Bollobás and Erdös ^[5] and Amic ^[1] independently:

where $\alpha$ is a nonzero real number. This topological index has been extensively investigated. We encourage interested readers to consult ^{[3,6,7,10,11,13]} for more mathematical properties and their applications.

Even though the mathematical and chemical theory of the general Randić index has been well considered, some extremal graph-theoretical problems concerning this graph invariant are still open. In this paper, we focus on exploring the extremal graphs in $\mathscr{G}_{n}^{\gamma}$ with respect to the general Randić index.

2.   Graphs in $\mathscr{G}_{n}^{\gamma}$ with minimum general Randić index

It is interesting to explore the extremal graphs for some topological indices in the class of graphs with a given cyclomatic number. In this section, we focus on determining the extremal graphs in $\mathscr{G}_{n}^{\gamma}$ with the minimum general Randić index. Before proceeding, we shall prove or list several facts as preliminaries.

Lemma 2.1. The function $P(x, \alpha) = 2^{\alpha}x^{\alpha+1}-\left(x-1\right)^{\alpha}[2^{\alpha}({x-2}) +3^{\alpha}]+ x^{\alpha}\left(2^{\alpha}-3^{\alpha}\right)-6^{\alpha} > 0$ for $x\geq 4$ and $1\leq\alpha \leq\frac{39}{25}.$

Proof. It is routine to check that

Note that $\rho(t) = t^{\alpha}-\left(t-1\right)^{\alpha}$ is an increasing function for $t\in[4, +\infty)$, and $2\cdot2^{\alpha} > 3^{\alpha}$ if, and only if, $\alpha < \frac{\ln2}{\ln3-\ln2}\approx 1.709$, then we have

For simplicity, let $H(\alpha) = 5\cdot8^{\alpha}-3\cdot 6^{\alpha}-9^{\alpha}-12^{\alpha}$. To continue our proof, we first verify the following fact. □

Claim 1. The function $\varrho(t) = k_{1}a^{t}-k_{2}b^{t}-k_{3}c^{t}$ has a unique zero point in the interval $[0, +\infty)$ for any positive real numbers $k_{1}, k_{2}, k_{3}, a, b, c$ such that $k_{1}-k_{2}-k_{3} > 0$ and $1 < a < b < c$.

Proof of Claim 1. It is routine to check that $\varrho'(t) = k_{1}\ln a \cdot a^{t}-k_{2}\ln b \cdot b^{t}-k_{3}\ln c \cdot c^{t}$. Note that $\varrho(0) = k_{1}-k_{2}-k_{3} > 0$ and $\varrho(M) = a^{t}\left[k_{1}-k_{2}\left(\frac{b}{a}\right)^{t}-k_{3}\left(\frac{c}{a}\right)^{t}\right]_{t = M}\rightarrow -\infty$, and it follows that $\varrho(t)$ has zero points in the interval $[0, +\infty)$. Without loss of generality, we assume that $t_{1}, t_{2} = t_{1}+h\in [0, +\infty)$ are the two distinct zero points of $\varrho(t)$ for $h > 0$, which is equivalent to $k_{1}a^{t_{1}}-k_{2}b^{t_{1}}-k_{3}c^{t_{1}} = 0$ and $k_{1}a^{t_{2}}-k_{2}b^{t_{2}}-k_{3}c^{t_{2}} = 0$. Besides, we know that $\varrho'(t) = k_{1}\ln a\cdot a^{t}-k_{2}\ln b\cdot b^{t}-k_{3}\ln c\cdot c^{t}$, which implies that

In addition, we have

which contradicts to the fact that $\varrho(t_{2}) = 0$. Hence, there must exist a unique number $t_{0}\in [0, +\infty)$ such that $\varrho(t_{0}) = 0$. As desired, we have completed the proof of Claim 1. □

Claim 2. The function $H(\alpha) = 5\cdot8^{\alpha}-3\cdot 6^{\alpha}-9^{\alpha}-12^{\alpha}$ has a unique zero point in the interval $(1, 2)$.

Proof of Claim 2. It is routine to check that $H'(\alpha) = 5\ln 8 \cdot 8^{\alpha}-3\ln 6 \cdot 6^{\alpha}-\ln 9 \cdot 9^{\alpha}-\ln 12\cdot 12^{\alpha}$. Note that $H(1) = 1 > 0$ and $H(2) = -13 < 0$, and it follows that $H(\alpha)$ has zero points in the interval $(1, 2)$. Without loss of generality, we assume that $\alpha_{0}, \alpha_{1}, \ldots, \alpha_{l}$ are the zero points of $H(\alpha)$ such that $1 < \alpha_{0} < \alpha_{1} < \ldots < \alpha_{l}$. Hence, $H(\alpha_{0}) = 5\cdot8^{\alpha_{0}}-3\cdot 6^{\alpha_{0}}-9^{\alpha_{0}}-12^{\alpha_{0}} = 0$. Furthermore,

It follows from Claim 1 that $\varrho(t)|_{a = 6, b = 9, c = 12}$ has a unique zero point in the interval $t_{0}\in[0, +\infty)$. Consequently, we know that the unique zero point of $\varrho(t)|_{a = 6, b = 9, c = 12}$ must lie in the interval $(0, 1)$ since $\varrho(0)|_{a = 6, b = 9, c = 12} > 0$ and $\varrho(1)|_{a = 6, b = 9, c = 12} = -0.7473 < 0$. Hence, $\varrho(t)|_{a = 6, b = 9, c = 12} < 0$ always holds for any real number $t\geq 1$. This implies that $H'(\alpha_{i}) = \varrho(\alpha_{i})|_{a = 6, b = 9, c = 12} < 0$ for $\alpha_{i} > 1$ and $i = 0, 1, \ldots, l$, which contradicts to the continuity of the function $H(\alpha)$. As desired, we have completed the proof of Claim 2. □

Now, we continue to our proof. Note that $H(\frac{39}{25}) = 5\cdot8^{\frac{39}{25}}-3\cdot 6^{\frac{39}{25}}-9^{\frac{39}{25}}-12^{\frac{39}{25}}\approx0.01857 > 0$ and $H(1.57) = 5\cdot8^{1.57}-3\cdot 6^{1.57}-9^{1.57}-12^{1.57}\approx -0.07428 < 0$. Hence, $P(x, \alpha)\geq H(\alpha) > 0$ for $\alpha\in [1, \frac{39}{25}]$. As desired, we have completed the proof of Lemma 2.1.

Lemma 2.2. The function $Q(x, \alpha) = 3^{\alpha}\big(x^{\alpha+1}-(x-1)^{\alpha+1}\big) -9^{\alpha}+2x^{\alpha}(2^{\alpha}-3^{\alpha}) > 0$ for $x\geq 4$ and $\alpha\geq 1.$

Proof. For simplicity, we distinguish the following two cases.

Case 1. $\alpha\in [1, 3)$.

Note that $h(t) = t^{\alpha}$ is an increasing function in the interval $[1-\frac{1}{x}, 1]$ for $\alpha\geq 1$, and it follows from Lagrange's mean value formula that $h(1)-h\left(1-\frac{1}{x}\right) = \left[1-\left(1-\frac{1}{x}\right)\right]h'(\xi) = \frac{1}{x}h'(\xi) = \frac{1}{x}\alpha \xi^{\alpha-1} > 0$, where $\xi\in (1-\frac{1}{x}, 1)$. Hence, $x\left[1-\left(1-\frac{1}{x}\right)^{\alpha}\right] = x\left[h(1)-h\left(1-\frac{1}{x}\right)\right] = \alpha \xi^{\alpha-1}$. Thus, we have

By our initial hypothesis, it is routine to check that $\xi^{\alpha-1} > (1-\frac{1}{x})^{\alpha-1}$, then we have

Let $p(\alpha) = \frac{9}{32}(\alpha+1)+\left(\frac{2}{3}\right)^{\alpha}-1$, then we have $p'(\alpha) = \frac{9}{32}+\left(\frac{2}{3}\right)^{\alpha}\ln\frac{2}{3}$ and $p''(\alpha) = \left(\frac{2}{3}\right)^{\alpha}\left(\ln\frac{2}{3}\right)^{2} > 0$. Hence, $p'(\alpha)\geq p'(1) = \frac{9}{32}+\frac{2}{3}\ln\left(\frac{2}{3}\right)\geq\frac{1}{100} > 0$, which implies that $p(\alpha)$ is increasing in the interval $[1, +\infty)$. Hence, $p(\alpha)\geq p(1) = \frac{11}{48} > 0$. It immediately yields that $Q_{x}(x, \alpha) > 2\alpha 3^{\alpha}x^{\alpha-1}p(\alpha) > 0$. Therefore, we have

as desired, and we have completed the proof.

Case 2. $\alpha\in [3, +\infty)$.

Note that

Let $g(\alpha) = 1-\frac{2}{x}-\left(1-\frac{1}{x}\right)^{\alpha}$ be a function defined in the interval $[3, +\infty)$, then we have $g'(\alpha) = \left(1-\frac{1}{x}\right)^{\alpha}\ln\left(1+\frac{1}{x-1}\right) > 0$. Hence, $g(\alpha)\geq g(3) = 1-\frac{2}{x}-\left(1-\frac{1}{x}\right)^{3} = \frac{x^{2}-3x+1}{x^{3}} > 0$, implying that $1-\left(1-\frac{1}{x}\right)^{\alpha} > \frac{2}{x}$. Thus, we have

Let $l(\alpha) = \left(\frac{12}{9}\right)^{\alpha}+\left(\frac{8}{9}\right)^{\alpha}-2$. It is routine to check that $l'(\alpha) = \left(\frac{8}{9}\right)^{\alpha}\left[\left(\frac{12}{8}\right)^{\alpha}\ln\left(\frac{12}{9}\right)+\ln\left(\frac{8}{9}\right)\right] > \left(\frac{8}{9}\right)^{\alpha}\left[\ln\left(\frac{12}{9}\right)+\ln\left(\frac{8}{9}\right)\right] = \left(\frac{8}{9}\right)^{\alpha}\ln15 > 0$. Hence, $l(\alpha)\geq l(3) = \frac{782}{729} > 0.$ It then follows that

as desired, and we have completed the proof. □

Proposition 2.3. Let $G\in\mathscr{G}_{n}^{\gamma}$ be a graph with $\gamma\geq 3$ and $n\geq 2(\gamma-1)$, then there is no pendent vertex in $G$ if it has a minimum general Randić index for $\alpha\geq 1$.

Proof. Suppose to the contrary that there exists a pendent vertex in $G$. Let $u$ be a vertex of degree at least three and $N_{G}(u) = \{u_{1}, u_{2}, \ldots, u_{k}\}$. In what follows, we use $P = uu_{1}\widehat{u_{2}}\ldots \widehat{u_{r}}$ to denote a pendent path in $G$. Assume that $u_{2}\neq u_{1}$ is another neighbor of $u$ with $d_{u_{2}}\geq 2$. We consider the graph $\widehat{G_{1}} = G-uu_{2}+u_{2}\widehat{u_{r}}$ (depicted in Figure 2), which is an element of $\mathscr{G}_{n}^{\gamma}$. Let $l-2$ be the number of vertices in $\{u_{3}, u_{4}, \ldots, u_{k}\}$, whose degree is greater than or equal to two. Clearly, $l\geq 2$ and $\sum\limits_{i = 3}^{k}d^{\alpha}_{u_{i}}\geq 2^{\alpha}(l-2)$. For simplicity, we distinguish the following two cases:

Case 1. $\ell(P) = 1$.

Direct calculations show that

It is not difficult to find the first term of the previous equality $\mathscr{A}_{1} = \left[(d^{\alpha}_{u_{2}}-2^{\alpha}+1)\left(d^{\alpha}_{u}-2^{\alpha}\right)\right] > 0$ for $\alpha\geq 1$, $d_{u}\geq 3$ and $d_{u_{2}}\geq 2$. To continue the proof, it remains to verify that $\mathscr{A}_{2} > 0$. For simplicity, we let $H({x}) = (l-1)[x^{\alpha}-(x-1)^{\alpha}]-(2^{\alpha}-1)$ for $\alpha\geq 1$ and $x\geq 3$. It is routine to check that $H({x}) > [(x^{\alpha}-(x-1)^{\alpha})-(3^{\alpha}-2^{\alpha})]+[(3^{\alpha}-2^{\alpha})-(2^{\alpha}-1)]$ since $l\geq 3$. Note that $f_{1}(x) = x^{\alpha}-(x-1)^{\alpha}$ is increasing in the interval $[3, \triangle]$, then we have $x^{\alpha}-(x-1)^{\alpha}\geq 3^{\alpha}-2^{\alpha}$. In addition, we know that $3^{\alpha}-2^{\alpha}\geq2^{\alpha}-1$ always holds for $\alpha\geq 1$. Hence, $H({x}) > 0$ and, consequently, we have ${\mathscr{A}_{2}} > 0$. It then immediately deduces that $R_{\alpha}(G)-R_{\alpha}(\widehat{G_{1}}) > 0$, a contradiction. This implies that there is no pendent vertex in $G$.

Case 2. $\ell(P)\geq 2$.

Direct calculations show that

Note that ${\mathscr{A}_{3}} > 0$ and ${\mathscr{A}_{4}} > 0$, and it is also not difficult to find that ${\mathscr{A}_{5}} = \frac{1}{l-1}{\mathscr{A}_{2}}$ is positive under the initial assumptions. Hence, $R_{\alpha}(G)-R_{\alpha}(\widehat{G_{1}}) > 0$. Again a contradiction. This implies that there is no pendent vertex in $G$.

As desired, we complete the proof of Proposition 2.3. □

Proposition 2.4. Let $G\in\mathscr{G}_{n}^{\gamma}$ be a graph with $\gamma\geq 3$ and $n\geq 2(\gamma-1)$, then the maximum vertex degree is three in $G$ if it has minimum general Randić index for $1\leq\alpha \leq\frac{39}{25}$.

Proof. It follows from Proposition 2.3 that $G$ contains at least one cycle as its induced subgraph, and the $n$-vertex cycle is the only connected graph for the which minimum and maximum vertex degree is two. Hence, in conjunction with the assumption $\gamma\geq3$, we have $\Delta = \Delta(G)\geq3$. To complete the proof, it suffices to show that $\Delta = 3$. If $\Delta > 3$, then it is routine to check that

which is equivalent to

Hence, there at least exists a vertex of degree two. For simplicity, we suppose that $u$ is the vertex in $G$ with maximum degree and $N_{G}(u) = \{u_{1}, u_{2}, \ldots, u_{\Delta}\}$. We distinguish the following two cases.

Case 1. $\exists i\in \{1, 2, \ldots, \Delta\}$ such that $d_{u_{i}} = 2$.

For convenience, we suppose that $u_{1}$ is the neighbor of $u$ with degree two and $d_{u_2}\geq d_{u_3}\geq \ldots\geq 2$.

Subcase 1.1. $d_{u_2} = 2$ and ${u_1}$ is not adjacent to ${u_2}$.

Let $\widehat{G_{2}} = G-uu_{2}+u_{1}u_{2}\in \mathscr{G}_{n}^{\gamma}$. $t$ is the neighbor of ${u_1}$, different from $u$, depicted in Figure 3. Hence, we have

For simplicity, we let $f_2{(x)} = 2^{\alpha}x^{\alpha+1}-\left(x-1\right)^{\alpha}[2^{\alpha}({x-2}) +3^{\alpha}]+ x^{\alpha}\left(2^{\alpha}-3^{\alpha}\right)-6^{\alpha}$. It follows from Lemma 2.1 that $f_{2}(x) = P(x, \alpha) > 0$ for $x\geq 4$ and $1\leq \alpha\leq \frac{39}{25}$. Hence, $R_{\alpha}(G)-R_{\alpha}(\widehat{G_{2}}) > 0$, which contradicts to the choice of $G$. Hence, the maximum vertex degree of $G$ is three.

Subcase 1.2. $d_{u_2} = 2$ and ${u_1}$ is adjacent to ${u_2}$.

Let $\widehat{G_{3}} = G-uu_{3}+u_{1}u_{3}\in \mathscr{G}_{n}^{\gamma}$, depicted in Figure 4. Hence, we have

Let $f_3{(x)} = 2^{\alpha}x^{\alpha+1}+4^{\alpha}-\left(x-1\right)^{\alpha}[2^{\alpha}({x-2}) +3^{\alpha}]-2\times 6^{\alpha}$, and then we have $f_3{(x)} = f_2{(x)}+(3^{\alpha}-2^{\alpha})(x^{\alpha}-2^{\alpha}) > 0$. Hence, $R_{\alpha}(G)-R_{\alpha}(\widehat{G_{3}}) > 0$ for $x\geq 4$ and $1\leq \alpha\leq \frac{39}{25}$, which contradicts to the choice of $G$. Hence, the maximum vertex degree of $G$ is three.

Subcase 1.3. $d_{u_2} > 2$ and ${u_1}$ is adjacent to ${u_2}$ and $d_{u_3} > 2$.

Let $\widehat{G_{4}} = G-uu_{3}+u_{1}u_{3}\in \mathscr{G}_{n}^{\gamma}$, depicted in Figure 5. Hence, we have

and the last inequality holds because $f_{2}(x) > 0$ for $x\geq 4$ and $1\leq \alpha\leq \frac{39}{25}$. Hence, $R_{\alpha}(G)-R_{\alpha}(\widehat{G_{4}}) > 0$. Again, a contradiction. Hence, the maximum vertex degree of $G$ is three.

Subcase 1.4. $d_{u_2} > 2$, ${u_1}$ is adjacent to ${u_2}$ and $d_{u_3} = 2$.

Let $\widehat{G_{5}} = G-uu_{3}+u_{1}u_{3}\in \mathscr{G}_{n}^{\gamma}$, depicted in Figure 6. Hence, we have

and the last inequality holds because $f_{3}(x) > 0$ for $x\geq 4$ and $1\leq \alpha\leq \frac{39}{25}$. Hence, $R_{\alpha}(G)-R_{\alpha}(\widehat{G_{5}}) > 0$. Again, a contradiction. Thus, we have completed that the maximum vertex degree of $G$ is three.

Subcase 1.5. $d_{u_2} > 2$, ${u_1}$ is not adjacent to ${u_2}$.

Let $\widehat{G_{6}} = G-uu_{2}+u_{1}u_{2}\in \mathscr{G}_{n}^{\gamma}$, depicted in Figure 7. Hence, we have

and the last inequality holds because $f_{2}(x) > 0$ for $x\geq 4$ and $1\leq \alpha\leq \frac{39}{25}$. Hence, $R_{\alpha}(G)-R_{\alpha}(\widehat{G_{6}}) > 0$, a contradiction to the choice of $G$. Hence, the maximum vertex degree of $G$ is three.

Case 2. $\forall i\in \{1, 2, \ldots, \Delta\}$ such that $d_{u_{i}} > 2$.

Note that there is a vertex $u_{0}\in V(G)\setminus N_{G}(u)$ of degree two, which is not adjacent to at least one neighbor, say $u_{1}$, of $u$. Let $\widehat{G_{7}} = G-uu_{1}+u_{0}u_{1}\in \mathscr{G}_{n}^{\gamma}$ (depicted in Figure 8). Hence,

For simplicity, we let $f_4{(x)} = 3^{\alpha}[x^{\alpha+1}-(x-1)^{\alpha+1}] -9^{\alpha}+2x^{\alpha}(2^{\alpha}-3^{\alpha}) = Q(x, \alpha)$, which is positive for $x\geq 4$ and $\alpha\geq 1$ by Lemma 2.2. Hence, we have $R_{\alpha}(G)-R_{\alpha}(\widehat{G_{7}}) > 0$. Thus, there would be a contradiction to the choice of $G$, and the maximum vertex degree of $G$ is three.

This completes the proof of Proposition 2.4. □

Let $\varphi_{ij}$ be the number of edges in $G$ joining the vertices of degree $i$ and $j$, and we use $n_{i}$ and $n_{j}$ to denote the number of vertices of degree $i$ and $j$, respectively.

Proposition 2.5.. (^[2]) Let $G\in \mathscr{G}_{n}^{\gamma}$, $\gamma\geq 3$, be a graph such that it contains only vertices of degrees two and three, then the following holds:

(i) at least two vertices of degree two are adjacent if $n > 5(\gamma-1)$.

(ii) $\varphi_{22} = 0$ implies $\varphi_{33} = 0$ (or $\varphi_{33} = 0$ implies $\varphi_{22} = 0$) if $n = 5(\gamma-1)$.

(iii) at least two vertices of degree three are adjacent if $2(\gamma-1)\leq n\leq 5(\gamma-1)$.

Proposition 2.6. Let $G\in\mathscr{G}_{n}^{\gamma}$ be a graph with $\gamma\geq 3$ and $n > 5(\gamma-1)$, then at least one of the vertices $x$ and $y$ for any edge $e = xy$ has the degree two in $G$ if it has a minimum general Randić index for $1\leq\alpha\leq \frac{39}{25}$.

Proof. By Proposition 2.3 and Proposition 2.4, we know $2\leq d_{u}\leq 3$ holds for any vertex $u$ in $G$. Simultaneously, it follows from Proposition 2.5 that there at least exist two vertices, say $u_{1}$ and $u_{2}$, such that $\varphi_{22} > 0$. Suppose to the contrary that there exists two adjacent vertices $v_{1}$ and $v_{2}$ of degree three (i.e., $\varphi_{33} > 0$). Let $u_{0}\neq u_{1}$ be the vertex adjacent with $u_{2}$, which may coincide with $v_{1}$ or $v_{2}$. For convenience, we distinguish the following two cases.

Case 1. $N_{G}(u_{1})\cap N_{G}(u_{2}) = \emptyset$.

Let $\widehat{G_{8}} = G-\{u_{1}u_{2}, u_{2}u_{0}, v_{1}v_{2}\}+\{u_{1}u_{0}, v_{1}u_{2}, v_{2}u_{2}\}$ (depicted in Figure 9), which is an element in $\mathscr{G}_{n}^{\gamma}$. By direct calculations, we have $R_{\alpha}(G)-R_{\alpha}(\widehat{G_{8}}) = 4^{\alpha}+9^{\alpha}-2\times 6^{\alpha} > 0$. This contradicts to the assumption of $G$. Hence, $\varphi_{33} = 0$. As desired, we have completed the proof.

Case 2. $N_{G}(u_{1})\cap N_{G}(u_{2})\neq\emptyset$.

Without loss of generality, we let $u_{0}\in N_{G}(u_{1})\cap N_{G}(u_{2})\neq\emptyset$. In what follows, we consider the following three subcases.

If $u_{0}\neq \{v_{1}, v_{2}\}$ and $u_{0}$ is not adjacent to $v_{1}$ and $v_{2}$, we let $\widehat{G_{9}} = G-\{u_{2}u_{0}, v_{1}v_{2}\}+\{u_{2}v_{2}, v_{1}u_{0}\}$ (depicted in Figure 10), which is an element in $\mathscr{G}_{n}^{\gamma}$. By direct calculations, we have $R_{\alpha}(G)-R_{\alpha}(\widehat{G_{9}}) = 0$. Note that $N_{\widehat{G_{9}}}(u_{1})\cap N_{\widehat{G_{9}}}(u_{2}) = \emptyset$, by the analogous method as in Case 1, and there exists a new graph $\widetilde{G_{1}}$ such that $R_{\alpha}(G)-R_{\alpha}(\widetilde{G_{1}}) = R_{\alpha}(\widehat{G_{9}})-R_{\alpha}(\widetilde{G_{1}}) > 0$. This contradicts to the assumption of $G$. As desired, we have completed the proof.

If $u_{0}\neq \{v_{1}, v_{2}\}$ and $u_{0}$ is adjacent to $v_{1}$, we let $\widehat{G_{10}} = G-\{u_{1}u_{2}, v_{1}v_{2}\}+\{u_{1}v_{1}, u_{2}v_{2}\}$, which is an element in $\mathscr{G}_{n}^{\gamma}$. By direct calculations, we have $R_{\alpha}(G)-R_{\alpha}(\widehat{G_{10}}) = 4^{\alpha}+9^{\alpha}-2\cdot 6^{\alpha} > 0$. This contradicts to the assumption of $G$. As desired, we have completed the proof.

If $u_{0} = v_{2}$, then we consider a neighbor $\widetilde{v}$ of $v_{1}$ different from $v_{2}$. Let $\widehat{G_{11}} = G-\{u_{2}v_{2}, \widetilde{v}v_{1}\}+\{v_{1}u_{2}, \widetilde{v}v_{2}\}\in \mathscr{G}_{n}^{\gamma}$, and again we obtain that $R_{\alpha}(G)-R_{\alpha}(\widehat{G_{11}}) = 0$. Note that $N_{\widehat{G_{11}}}(u_{1})\cap N_{\widehat{G_{11}}}(u_{2}) = \emptyset$, by the analogous method as in Case 1, and there exists a new graph $\widetilde{G_{2}}$ such that $R_{\alpha}(G)-R_{\alpha}(\widetilde{G_{2}}) = R_{\alpha}(\widehat{G_{11}})-R_{\alpha}(\widetilde{G_{2}}) > 0$. This contradicts to the assumption of $G$. We have completed the proof. □

Proposition 2.7. Let $G\in\mathscr{G}_{n}^{\gamma}$ be a graph with $\gamma\geq 3$ and $n = 5(\gamma-1)$, then one of the vertices $x$ and $y$ for any edge $e = xy$ has the degree two and the other has the degree three in $G$ if it has the minimum general Randić index for $1\leq\alpha\leq \frac{39}{25}$.

Proof. It follows from Propositions 2.3 and 2.4 that $2\leq d_{u}\leq 3$ holds for any vertex $u$ in $G$. If $\varphi_{22} = 0$ and $\varphi_{33}\neq 0$, then one can find that $\varphi_{23} = 0$ by Proposition 2.5, a contradiction. If $\varphi_{22}\neq0$ and $\varphi_{33}\neq 0$, then from the proof of Proposition 2.6 we conclude that there exists a graph $\widehat{G_{12}}\in \mathscr{G}_{n}^{\gamma}$ such that $R_{\alpha}(G)-R_{\alpha}(\widehat{G_{12}}) > 0$. This contradicts to the initial assumption of $G$. Hence, $\varphi_{22} = \varphi_{33} = 0$. As desired, we complete the proof of Proposition 2.7. □

In a similar way, we obtain the following fact.

Proposition 2.8. Let $G\in\mathscr{G}_{n}^{\gamma}$ be a graph with $\gamma\geq 3$ and $2(\gamma-1) < n < 5(\gamma-1)$, then $G$ does not contain any edge connecting the vertices of degree two if it has a minimum general Randić index for $1\leq\alpha\leq \frac{39}{25}$.

Denote by $\overline{G_{ij}[\varphi_{ij}\neq 0]}$ that the graphs contain only vertices of degree $i$ and $j$, such that for every edge in a one end-vertex has the degree $i$ and the other end-vertex has the degree $j$, and we use $\overline{G_{ij}[\varphi_{ii} = 0]}$ (resp. $\overline{G_{ij}[\varphi_{jj} = 0]}$) to denote the graphs containing only vertices of degree $i$ and $j$, such that no vertices of degree $i$ (resp. $j$) are adjacent.

Theorem 2.9. Let $G\in\mathscr{G}_{n}^{\gamma}$ be a graph with $\gamma\geq 3$ and $n$ vertices, then the following holds for $1\leq\alpha\leq \frac{39}{25}$:

(i) $R_{\alpha}(G)\geq 9^{\alpha}(n+\gamma-1)$ for $n = 2(\gamma-1)$, with equality if, and only if, $G$ is isomophic to cubic graphs.

(ii) $R_{\alpha}(G)\geq 6^{\alpha}(2n-4\gamma+4)-9^{\alpha}(n-5\gamma+5)$ for $2(\gamma-1) < n < 5(\gamma-1)$, with equality if, and only if, $G$ is isomophic to $\overline{G_{23}[\varphi_{22} = 0]}$.

(iii) $R_{\alpha}(G)\geq 6^{\alpha}(n+\gamma-1)$ for $n = 5(\gamma-1)$, with equality if, and only if, $G$ is isomophic to $\overline{G_{23}[\varphi_{23}\neq0]}$.

(iv) $R_{\alpha}(G)\geq 4^{\alpha}(n-5\gamma+5)+6^{\alpha}(6\gamma-6)$ for $n > 5(\gamma-1)$, with equality if, and only if, $G$ is isomophic to $\overline{G_{23}[\varphi_{33} = 0]}$.

Proof. Let $\widehat{G_{13}}\in\mathscr{G}_{n}^{\gamma}$ be a graph that achieves the minimum general Randić index. We only give the proof of $(ii)$; the rest could be proved in a similar way. It follows from Propositions 2.3 and 2.4 that $2\leq d_{u}\leq 3$ holds for any vertex $u$ in $\widehat{G_{13}}$. Hence, we have $n_{2}+n_{3} = n$ and $2n_{2}+3n_{3} = 2(n+\gamma-1)$ by the Handshaking Theorem. Besides, by Proposition 2.8, it is easily seen that $\varphi_{22} = 0$. Hence, $\varphi_{23} = 2n_{2}$ and $\varphi_{23}+2\varphi_{33} = 3n_{3}$. Direct calculations show that $\varphi_{23} = 2n-4\gamma+4$ and $\varphi_{33} = 5\gamma-n-5$. Thus, $R_{\alpha}(G)\geq R_{\alpha}(\widehat{G_{13}}) = 6^{\alpha}(2n-4\gamma+4)-9^{\alpha}(n-5\gamma+5)$. The corresponding extremal graph is $\overline{G_{23}[\varphi_{22} = 0]}$. □

The second Zagreb index is another well-known vertex degree-based graph invariant in chemical graph theory, which was introduced in 1972 by Gutman and Trinajstić ^[8]. We encourage the interested reader to consult ^[9,12] for more information for this graph invariant. Undoubtedly, the second Zagreb index is the special case of the general Randić index when $\alpha = 1$. It is easily seen that Theorem 2.9 extends one of the main results proved by Ali et al. ^[2].

3.   Graphs in $\mathscr{G}_{n}^{\gamma}$ with maximum general Randić index

We begin with the following auxiliary result, which plays an important part in our proofs.

Proposition 3.1. Let $G\in\mathscr{G}_{n}^{\gamma}$ be a graph with a maximum general Randić index for $\alpha\geq 1$, then $\Delta(G) = n-1$.

Proof. Suppose to the contrary that there exists a vertex $u$ in $G$ with $\Delta(G) = d_{u} < n-1.$ Note that there exists $v\in V(G)$ such that $u\neq v$, $d_{u}\geq d_{v}$ and $N_{G}(v)\backslash N_{G}(u) = \{v_{1}, v_{2}, \ldots, v_{p}\}\neq \emptyset$. We can construct a new graph $\widehat{G_{14}}$ the following way

It is routine to check that

Note that $H(t) = t^{\alpha}$ is an increasing function for $\alpha\geq 1$, and the first and second terms of the previous equality are nonnegative. By the Lagrange mean value theorem, we have $\left(d_{u}+p\right)^{\alpha}-d_{u}^{\alpha} = \alpha p\xi^{\alpha-1}$ (resp. $d_{v}^{\alpha}-\left(d_{v}-p\right)^{\alpha} = \alpha p\eta^{\alpha-1}$) for $\xi\in(d_{u}, d_{u}+p)$ (resp. $\eta\in(d_{v}-p, d_{v})$). Hence, $\mathscr{A}_{6} = \left(d_{u}+p\right)^{\alpha}+\left(d_{v}-p\right)^{\alpha}-d_{u}^{\alpha}-d_{v}^{\alpha} > 0$, and, consequently, we have $R_{\alpha}(\widehat{G_{14}}) > R_{\alpha}(G)$, a contradiction. This completes the proof. □

Proposition 3.2. (^[14]) Let $x_{1}, x_{2}, \ldots, x_{n}, p, t\geq 1$ be integers, $\alpha$ be any real number such that $\alpha\notin \{0, 1\}$ and $x_{1}+x_{2}+\ldots+x_{n} = p$.

(1) The function $f(x_{1}, x_{2}, \ldots, x_{n}) = \sum_{i = 1}^{n}x_{i}^{\alpha}$ is the minimum for $\alpha < 0$ or $\alpha > 1$ (maximum for $0 < \alpha < 1$, respectively) if, and only if, $x_{1}, x_{2}, \ldots, x_{n}$ are almost equal, or $|x_{i}-x_{j}|\leq 1$ for every $i, j = 1, 2, \ldots, n$.

(2) If $x_{1}\geq x_{2}\geq t$, the maximum of the function $f(x_{1}, x_{2}, \ldots, x_{n})$ is reached for $\alpha < 0$ or $\alpha > 1$ (minimum for $0 < \alpha < 1, respectively$) only for $x_{1} = p-t-n+2, x_{2} = t, x_{3} = x_{4} = \ldots = x_{n} = 1$. The second maximum (the second minimum, respectively) is attained only for $x_{1} = p-t-n+1, x_{2} = t+1, x_{3} = x_{4} = \ldots = x_{n} = 1.$

Theorem 3.3. Let $G\in\mathscr{G}_{n}^{\gamma}$ be a graph with $\gamma = {k-1\choose 2}$ and $k\geq 4$, then for $\alpha\geq 1$ we have

with equality if, and only if, $G\cong(K_{1}^{\gamma}\cup (n-2)K_{1})+K_{1}\cong K_{n}^{\gamma}$, depicted in Figure 11.

Proof. It follows from Proposition 3.1 that there at least exists one vertex with a maximum degree $n-1$. Hence, we have $G = \widehat{G_{15}}+K_{1}$, which contains $|V(\widehat{G_{15}})| = n-1$ vertices and $m(\widehat{G_{15}}) = {k-1\choose 2}$ edges. For simplicity, let $\pi = (d_{1}, d_{2}, \ldots, d_{n})$ and $\widehat{\pi} = (\widehat{d_{1}}, \widehat{d_{2}}, \ldots, \widehat{d_{n-1}})$ be the nonincreasing degree sequence of $G$ and $\widehat{G_{15}}$, respectively. Hence, $d_{i} = \widehat{d_{i-1}}+1$ for $i = 2, 3, \ldots, n$ and $d_{1} = n-1.$ Thus, we have

By Proposition 3.2 for $\alpha\geq 1$, we have

where $d_{1} = n-1 = 2m-t-n+2, d_{2} = t = 2\gamma+1$ and $d_{3} = d_{4} = \ldots = d_{n} = 1$. In addition, we find the maximum value of

with equality if, and only if, $\widehat{G_{15}}\cong K_{1}^{\gamma}\cup (n-2)K_{1}$.

It follows from the previous that

Hence, $G = (K_{1}^{\gamma}\cup (n-2)K_{1})+K_{1}\cong K_{n}^{\gamma}$. This completes the proof of Theorem 3.3. □

Use of AI tools declaration

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

Acknowledgments

We would like to show our great gratitude to the anonymous referees for carefully reading the manuscript and improving its presentation and accuracy. The first author is supported by the Natural Science Foundation of Beijing (No.1222012) and National Key Research and Development Project (No.2019YFB2006602).

Conflict of interest

The authors declare that they have no conflicts of interest.