Open Access Full-Text PDF

Open Journal of Discrete Applied Mathematics

A Note on the Zeroth-order General Randić Index of Polygonal Cacti

Jiachang Ye, Yuedan Yao\(^1\)
Department of Mathematics, South China Agricultural University, Guangzhou, China.; (J.Y & Y.Y)
\(^{1}\)Corresponding Author;  yaoyuedan12@163.com

Copyright © 2018 Jiachang Ye, Yuedan Yao. This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.

Abstract

The zeroth-order general Randić index of a simple connected graph G is defined as \(R_{\alpha}^{0}(G)=\sum_{u\in V(G)} \big(d(u)\big)^{\alpha}\), where \(d(u)\) is the degree of \(u\) and \(\alpha\not\in \{0,1\}\) is a real number. A \(k\)-polygonal cactus is a connected graph in which every edge lies in exactly one cycle of length \(k\). In this paper, we present the extremal \(k\)-polygonal cactus with \(n\) cycles for \(k\geq3\) with respect to the zeroth-order general Randić index.

Keywords:

Cactus; Zeroth-order general Randić index; Extremal graph.

1. Introduction

Throughout this paper, \(G\) denotes a simple connected undirected graph with vertex set \(V(G)\) and edge set \(E(G)\). Let \(d_G(u)\) and \(N_G(u)\) be the degree and neighbor set of vertex \(u\) in \(G\), respectively. \(n_G(j)\) is the number of the vertices with degree \(j\) in \(G\). For a connected graph \(G\) with \(u\in V(G)\), if \(G-u\) is not connected, then \(u\) is called a cut-vertex of \(G\). Let \(X\) be a subset of \(V(G)\), we use \(G[X]\) to denote the subgraph of \(G\) induced by \(X\).

A cactus graph , or cactus for short, is a connected graph in which no edge lies in more than one cycle. Consequently, each block of a cactus is either an edge or a cycle. A cycle of length \(k\) is denoted by \(C_k\), and \(C_k\) is always called a \(k\)-polygon in the sequel. If each block of a cactus \(G\) is a \(k\)-polygon, then \(G\) is called a \(k\)-polygonal cactus . Hereafter, if there is no risk of confusion, we always call a \(k\)-polygon as a polygon, and we always simplify \(d_G(u)\) and \(N_G(u)\) as \(d(u)\) and \(N(u)\), respectively.

Let \(\mathcal {G}_{n,k}\) be the class of \(k\)-polygonal cacti with \(n\geq3\) blocks. Suppose that \(G\in \mathcal {G}_{n,k}\) . If \(C_k\) contains exactly one cut-vertex, then \(C_k\) is called a pendent polygon . While \(C_k\) is called a non-pendent polygon if \(C_k\) contains at least two cut-vertices.

A cactus chain is a special \(k\)-polygonal cactus graph such that each polygon has at most two cut-vertices, and each cut-vertex is shared by exactly two polygons. When \(G\) is a cactus chain, then the number of polygons is called the length of \(G\). For convenience, we use the notation \(\mathcal{T}_{n,k}\) to denote the class of cactus chains of length \(n\) such that each polygon is a \(k\)-polygon. From the definition, each cactus chain of \(\mathcal{T}_{n,k}\) has exactly \(n-2\) non-pendent polygons and two pendent polygons. When \(k=3\) and \(n\geq 3\), it is easy to see that the cactus chain of \(\mathcal{T}_{n,k}\) is unique. However, when \(k\geq4\) and \(n\geq3\), \(\mathcal{T}_{n,k}\) is not unique.

A star-like cactus \(W_{n,k}\) is a special \(k\)-polygonal cactus graph with \(n\) polygons such that all polygons have a common vertex. From the definition, \(W_{n,k}\) is unique and all polygons of \(W_{n,k}\) are pendent polygons and \(W_{n,k}\) contains exactly one vertex with degree being equalto \(2n\) and the degree of all the other vertices of \(W_{n,k}\) is equal to two.

Among all the vertex-degree-based graph invariants, the first Zagreb index \(M_1(G)\) [1] and zeroth-order Randić index \(R^{0}(G)\) [2] are two famous topological indices, where $$M_{1}(G)=\sum_{u\in V(G)} \big(d(u)\big)^{2},\,\,\text{and}\,\,R^{0}(G)=\sum_{u\in V(G)} \big(d(u)\big)^{-\frac{1}{2}}.$$ In what follows, \(\alpha\) always denotes a real number such that \(\alpha\not\in \{0,1\}\). As a generalization of \(M_1(G)\) and \(R^{0}(G)\), Li and Zheng [3] put forward the concept of first general Zagreb index \(R_{\alpha}^{0}(G)\), where $$ R_{\alpha}^{0}(G)=\sum_{u\in V(G)} \big(d(u)\big)^{\alpha}.$$ From the definition, it is easy to see that \(M_1(G)=R_{2}^{0}(G)\) and \(R^{0}(G)=R_{-\frac{1}{2}}^{0}(G)\). In some literature, \(R_{\alpha}^{0}(G)\) is also called the zeroth-order general Randić index of \(G\) [4, 5, 6].

In what follows, denote by $$\Phi(n,k,\alpha)=\big(n-1\big)4^{\alpha}+\big(nk-2n+2\big)2^{\alpha},\,\,\text{and}\,\,\, \Psi(n,k,\alpha)=\big(2n\big)^{\alpha}+n\big(k-1\big)2^{\alpha}.$$ Recently, the research on zeroth-order general Randić index of cacti had attracted more and more attention. For instance, Ali et al. [4] characterized the extremal polyomino chains with respect to the zeroth-order general Randić index, Hua et al. [6] identified the extremal unicycle graphs with maximum and minimum zeroth-order genenral Randić index and Hu et al. [5] determined the extremal connected \((n,m)\)-graphs with minimum and maximum zeroth-order general Randić index. In this paper, we shall determine the extremal \(k\)-polygonal cactus with \(n\geq 3\) cycles for \(k\geq3\) with respect to the zeroth-order general Randić index, that is,

Theorem 1.1. Let \(G\) be a cactus of \(\mathcal{G}_{n,k}\), where \(n\geq3\), \(k\geq3\) and \(\alpha\) is a real number.

\((i)\) If \(\alpha < 0 \) or \(\alpha > 1\), then \(\Phi(n,k,\alpha)\leq R_{\alpha}^{0}(G)\leq \Psi(n,k,\alpha)\), where the left equality holds if \(G\in\mathcal{T}_{n,k}\) and the right equality holds if and only if \(G \cong W_{n,k}\).

\((ii)\) If \(0< \alpha< 1\), then \(\Psi(n,k,\alpha)\leq R_{\alpha}^{0}(G)\leq \Phi(n,k,\alpha)\), where the left equality holds if and only if \(G \cong W_{n,k}\) and the right equality holds if \(G\in\mathcal{T}_{n,k}\).

Remark 1.2. It is easy to see that \(\mathcal{T}_{n,k}\) is unique for \(k=3\) and \(n\geq3\), but not unique for \(k\geq4\) and \(n\geq3\). By Theorem 1.1, \(R_{\alpha}^{0}(G)=\Phi(n,k,\alpha)\) holds for every cactus \(G\in \mathcal{T}_{n,k}\). Furthermore, the cacti of \(\mathcal{T}_{n,k}\) are not all the extremal cacti of Theorem 1.1, to see this, let \(G_1\) and \(G_2\) be the two cacti as shown in Fig.1. By an elementary computation, we have \(R_{\alpha}^{0}(G_1)=R_{\alpha}^{0}(G_2)=\Phi(4,6,\alpha)\), but \(G_2\not\in \mathcal{T}_{4,6}\).

Figure 1. The Graphs   \(G_{1}\) and \(G_{2}\).

2. The proof of Theorem 1.1

This section dedicates to the proof of Theorem 1.1.

Lemma 2.1. Let \(f(x)=x^{\alpha}-(x-2)^{\alpha}\). If \(x>2\), then \(f(x)\) is decreasing for \(0< \alpha< 1 \) and increasing for \(\alpha< 0 \) or \(\alpha>1\).

Proof. By Lagrange's mean value theorem, \(f'(x)=\alpha\left(x^{\alpha-1}-(x-2)^{\alpha-1}\right)=2\alpha(\alpha-1)\Theta^{\alpha-2}\), where \(x>2\) and \(x-2< \Theta < x\). It is easy to see that \(f'(x)\) is negative for \(0 < \alpha < 1\) and \(f'(x)\) is positive for \(\alpha < 0 \) or \(\alpha > 1\). Thus, the result holds.

Recall that \(\mathcal{T}_{n,k}\) is the class of cactus chains of length \(n\) such that each polygon is a \(k\)-polygon. From the definition, if \(k=3\) and \(n\geq3\), then \(\mathcal{T}_{n,k}\) is unique. However, when \(k\geq4\) and \(n\geq3\), \(\mathcal{T}_{n,k}\) is not unique. On the other hand, \( W_{n,k}\) is always unique when \(k\geq3\) and \(n\geq3\). The following result implies that \(R_{\alpha}^{0}(G)\) is a constant for either \(G\in \mathcal{T}_{n,k}\) or \(G\cong W_{n,k}\).

Lemma 2.2. Let \(k\geq3\) and \(n\geq1\) be two integers. \((i)\) If \(G\in \mathcal{T}_{n,k}\), then \(R_{\alpha}^{0}(G)=\big(n-1\big)4^{\alpha}+\big(nk-2n+2\big)2^{\alpha}\). \((ii)\) If \(G\cong W_{n,k}\), then \(R_{\alpha}^{0}(G)=\big(2n\big)^{\alpha}+n\big(k-1\big)2^{\alpha}\).

Proof. \((i)\) If \(G\in \mathcal{T}_{n,k}\), then \(n_G(4)=n-1\) and \(n_G(2)=nk-2n+2\). Thus, we have $$R_{\alpha}^{0}(G)=\sum_{u\in V(G)} (d(u))^{\alpha}=\big(n-1\big)4^{\alpha}+\big(nk-2n+2\big)2^{\alpha}.$$

\((ii)\) If \(G\cong W_{n,k}\), then \(n_G(2n)=1\) and \(n_G(2)=n(k-1)\). Thus, we have $$ R_{\alpha}^{0}(G)=\sum_{u\in V(G)} (d(u))^{\alpha}=\big(2n\big)^{\alpha}+n\big(k-1\big)2^{\alpha}.$$ This completes the proof of this result.

To prove our main results, we need to introduce more definitions, which were raised in [7]:
Suppose that \(G\in \mathcal{G}_{n,k}\) and \(C^{(1)}_{k}\), \(C^{(2)}_{k}\), \(\ldots,\) \(C^{(s)}_{k}\) are \(s\) cycles of length \(k\) in \(G\), where \(k\geq 3\), \(s\geq 1\) and \(n\geq3\). Let \(V_1=V\left(C^{(1)}_{k}\right)\cup V\left(C^{(2)}_{k}\right)\cup \cdots \cup V\left(C^{(s)}_{k}\right)\) and let \(u_1\) be a cut-vertex of \(C^{(1)}_{k}\) in \(G\) such that \(u_1\) is not a cut-vertex of \(G\big[V_1\big]\). If \(G\big[V_1\big]\) is a cactus chain and each \(k\)-polygon of \(\left\{C^{(1)}_{k}, C^{(2)}_{k}, \ldots, C^{(s)}_{k}\right\}\) has at most two cut-vertices in \(G\), \(C^{(s)}_{k}\) is a pendent polygon of \(G\), the degree of each vertex of \(V_1\setminus\{u_{1}\}\) is at most four in \(G\), then \(G\big[V_1\big]\) is called a pendent cactus chain of length \(s\) of \(G\). Furthermore, if \(G\big[V_1\big]\) is a pendent cactus chain of length \(s\geq 2\), then \(C^{(s-1)}_{k}\) is called a neighbor polygon of the pendent cactus chain. Hereafter, we denote \(L_{s,k}\) as a pendent cactus chain of length \(s\) in a \(k\)-polygonal cactus. From the definition, if \(G\big[V_1\big]\) is a pendent cactus chain of length \(s\geq 2\), then for \(1\leq i\leq s-1\) and \(2\leq j\leq s-1\), each \(C^{(i)}_k\) contains exactly two cut-vertices in \(G\) and the degree of every cut-vertex of \(C^{(j)}_k\) is equal to four in \(G\).

Definition 2.3. Let \(G\) be a cactus of \(\mathcal{G}_{n,k}\) and let \(C^{(1)}_{k}\), \(C^{(2)}_{k}\), \(\ldots,\) \(C^{(s+t)}_{k}\) be \(s+t\) cycles of length \(k\) of \(G\) such that \(G\left[V\left(C^{(1)}_{k}\right)\cup V\left(C^{(2)}_{k}\right)\cup \cdots \cup V\left(C^{(s)}_{k}\right)\right]\) and \(G\Big[V\left(C^{(s+1)}_{k}\right)\cup V\left(C^{(s+2)}_{k}\right)\cup \cdots \cup V\left(C^{(s+t)}_{k}\right)\Big]\) are two pendent cactus chains of length \(s\geq 1\) and \(t\geq 1\), respectively.

\((i)\) If \(u_0\in V\left(C^{(1)}_{k}\right)\cap V\left(C^{(s+1)}_{k}\right)\) and \(d_G(u_0)\geq 6\), then \(u_0\) is called a singular vertex of \(G\).

\((ii)\) If \(C^{(0)}_k\) is a \(k\)-polygon of \(G\) with at least three cut vertices in \(G\) such that \(V\left(C^{(1)}_{k}\right)\cap V\left(C^{(0)}_{k}\right)=\{v_0\}\) and \(V\left(C^{(s+1)}_{k}\right)\cap V\left(C^{(0)}_{k}\right)=\{w_0\}\) with \(d_G(w_0)=d_G(v_0)=4\), then \(C^{(0)}_k\) is called a special polygon of \(G\).

Lemma 2.4. Let \(G\) be a cactus of \(\mathcal{G}_{n,k}\), where \(k\geq 3\) and \(n\geq3\). If \(G\) contains a singular vertex, then \(R_{\alpha}^{0}(G)\) is neither minimum for \(\alpha< 0\) or \(\alpha>1\) and not maximum for \(0 < \alpha< 1\) in \( \mathcal{G}_{n,k}\).

Proof. By contradiction, we assume that \(R_{\alpha}^{0}(G)\) is minimum for \(\alpha< 0\) or \(\alpha>1\) and maximum for \(0< \alpha< 1\) in \( \mathcal{G}_{n,k}\). Let \( u_0 \) be a singular vertex of \(G\) with \(d_G(u_0)=2r\), where \(r\geq 3\). For convenience, we suppose that \(u_0\) is a common vertex of two pendent cactus chains \(L_{t,k}\) and \(L_{s,k}\) in \(G\), where \(s\geq t\geq 1\). Suppose that \(C^{(t)}_k=u_1u_2\cdots u_ku_1\) and \(C^{(s)}_k=w_1w_2\cdots w_kw_1\) are the pendent polygons of \(L_{t,k}\) and \(L_{s,k}\), respectively, such that \(u_1\) and \(w_1\) are two cut-vertices of \(G\). Let \(G'=G-u_1u_2-u_1u_k+w_2u_2+w_2u_k\). By the definition of \(G'\), it it easy to see that

Observation 1. If \(t\geq 2\), then \(u_0\) is also a singular vertex of \(G'\) such that \(u_0\) is a common vertex of two pendent cactus chains \(L_{t-1,k}\) and \(L_{s+1,k}\) in \(G'\).
We consider the following two cases:

Case 1. \(t=1\).
From the definition, we have \begin{eqnarray*} \ R_{\alpha}^{0}(G)-R_{\alpha}^{0}(G')=(2r)^\alpha+2^{\alpha}-(2r-2)^\alpha-4^{\alpha} =(2r)^\alpha-(2r-2)^\alpha-(4^{\alpha}-2^{\alpha}). \end{eqnarray*} By lemma 2.1, since \(2r\geq6>4\), it is easy to see that \(R_{\alpha}^{0}(G)>R_{\alpha}^{0}(G')\) for \(\alpha< 0\) or \(\alpha>1\) and \(R_{\alpha}^{0}(G)< R_{ \alpha}^{0}(G') \) for \(0< \alpha< 1\). No matter which case happens, we can reach a contradiction.

Case 2. \(t\geq2\).
If \(t\geq2\), then from the definition, we have \begin{eqnarray*} \ R_{\alpha}^{0}(G)-R_{\alpha}^{0}(G')&=&4^{\alpha}+2^{\alpha}-2^{\alpha}-4^{\alpha}=0 \end{eqnarray*} Now, by Observation 1 and above equality, there exists a cactus \(G'\) of \(\mathcal{G}_{n,k}\) such that \(R_{\alpha}^{0}(G)=R_{\alpha}^{0}(G')\), \(u_0\) is also a singular vertex of \(G'\) and \(u_0\) is a common vertex of two pendent cactus chains \(L_{t-1,k}\) and \(L_{s+1,k}\) in \(G'\). By repeating the above process, we can conclude that there exists a cactus \(G_1\) of \(\mathcal{G}_{n,k}\) such that \(R_{\alpha}^{0}(G)=R_{\alpha}^{0}(G_1)\), \(u_0\) is also a singular vertex of \(G_1\) and \(u_0\) is a common vertex of two pendent cactus chains \(L_{1,k}\) and \(L_{s+t-1,k}\) in \(G_1\). Now, from the above arguments and Case 1, we can conclude that there exists cactus \(G_0\) of \(\mathcal{G}_{n,k}\) such that \(R_{\alpha}^{0}(G)>R_{\alpha}^{0}(G_0)\) for \(\alpha< 0\) or \(\alpha >1\) and \(R_{\alpha}^{0}(G)< R_{\alpha}^{0}(G_0)\) for \(0< \alpha< 1 \), and \(G_0\) contains no singular vertex, a contradiction. Thus, the result holds.

Lemma 2.5. Let \(G\) be a cactus of \(\mathcal{G}_{n,k}\), where \(n\geq4\) and \(k\geq 3\). If \(G\) contains a special polygon, then there exists \(G_0\in \mathcal{G}_{n,k}\) such that \(R_{\alpha}^{0}(G_0)\leq R_{\alpha}^{0}(G)\) for \(\alpha< 0\) or \(\alpha>1\) and \(R_{\alpha}^{0}(G_0)\geq R_{\alpha}^{0}(G)\) for \(0< \alpha< 1\) and \(G_0\) contains no special polygon.

Proof. Let \(C^{(0)}_k\) be a special polygon, and let \(L_{t,k}\) and \(L_{s,k}\) be two pendent cactus chains of \(G\) such that \(V\big(L_{t,k}\big)\cap V\left(C^{(0)}_k\right)=\{u_0\}\) and \(V\big(L_{s,k}\big)\cap V\left(C^{(0)}_k\right)=\{w_0\}\), where \(s\geq t\geq 1\). Suppose that \(C^{(t)}_k=u_1u_2\cdots u_ku_1\) and \(C^{(s)}_k=w_1w_2\cdots w_kw_1\) are the pendent polygons of \(L_{t,k}\) and \(L_{s,k}\), respectively, such that \(u_1\) and \(w_1\) are two cut-vertices of \(G\). Let \(G'=G-u_1u_2-u_1u_k+w_2u_2+w_2u_k\). By the definition of \(G'\), it it easy to see that

Observation 1. If \(t\geq 2\), then \(C^{(0)}_k\) is also a special polygon of \(G'\) and that \(L_{t-1,k}\) and \(L_{s+1,k}\) are two pendent cactus chains of \(G'\) such that \(V\big(L_{t-1,k}\big)\cap V\left(C^{(0)}_k\right)=\{u_0\}\) and \(V\big(L_{s+1,k}\big)\cap V\left(C^{(0)}_k\right)=\{w_0\}\). We consider all cases as follows, by the definition of \(G'\), we have

\begin{equation} R_{\alpha}^{0}(G)-R_{\alpha}^{0}(G')= 4^{\alpha}+2^{\alpha}-2^{\alpha}-4^{\alpha}=0. \end{equation}
(1)

Apparently, if \(t\geq 2\), by observation 1 we can conclude that there exists a cactus \(G'\) of \(\mathcal{G}_{n,k}\) such that \(R_{\alpha}^{0}(G)=R_{\alpha}^{0}(G')\), where \(C^{(0)}_k\) is also a special polygon of \(G'\) such that \(L_{t-1,k}\) and \(L_{s+1,k}\) are two pendent cactus chains of \(G'\), \(V\big(L_{t-1,k}\big)\cap V\left(C^{(0)}_k\right)=\{u_0\}\) and \(V\big(L_{s+1,k}\big)\cap V\left(C^{(0)}_k\right)=\{w_0\}\). By repeating the above process, we can also conclude that there exists a cactus \(G_1\) of \(\mathcal{G}_{n,k}\) such that \(R_{\alpha}^{0}(G)=R_{\alpha}^{0}(G_1)\), where \(C^{(0)}_k\) is also a special polygon of \(G_1\) such that \(L_{1,k}\) and \(L_{s+t-1,k}\) are two pendent cactus chains of \(G_1\), \(V\big(L_{1,k}\big)\cap V\left(C^{(0)}_k\right)=\{u_0\}\) and \(V\big(L_{s+t-1,k}\big)\cap V\left(C^{(0)}_k\right)=\{w_0\}\). And now for \(t=1\), through the operation illustrated before and (1), we can construct the corresponding graph \(G_2\) such that \(G_2\in \mathcal{G}_{n,k}\), \(R_{\alpha}^{0}(G)=R_{\alpha}^{0}(G_2)\) and one pendent chain will disappear in \(G_2\).

By repeating the above arguments, we can conclude that there exists \(G_0\in \mathcal{G}_{n,k}\) such that \(R_{\alpha}^{0}(G_0)\leq R_{\alpha}^{0}(G)\) for \(\alpha< 0\) or \(\alpha>1\) and \(R_{\alpha}^{0}(G_0)\geq R_{\alpha}^{0}(G)\) for \(0< \alpha< 1\) and \(G_0\) contains no special polygon for \(k\geq 3\). Thus, the result holds.

Lemma 2.6. [7] Let \(G\) be a cactus of \(\mathcal{G}_{n,k}\), where \(k\geq 3\) and \(n\geq 3\). If \(G\) contains neither singular vertex nor special polygon, then \(G\) must be a cactus chain.

Lemma 2.7. Let \(G\) be a cactus of \(\mathcal{G}_{n,k}\). If \(k\geq 3\) and \(n\geq 3\), then \(R_{\alpha}^{0}(G)\leq \Psi(n,k,\alpha)\) for \(\alpha< 0\) or \(\alpha>1\) and \(R_{\alpha}^{0}(G)\geq \Psi(n,k,\alpha)\) for \(0< \alpha< 1\), where either equality holds if and only if \(G \cong W_{n,k}\).

Proof. Let \(G\) be a cactus of \(\mathcal{G}_{n,k}\) such that \(G\) is an extremal graph of \(\mathcal{G}_{n,k}\), namely, \(R_{\alpha}^{0}(G)\) is as large as possible for \(\alpha< 0\) or \(\alpha>1\), and \(R_{\alpha}^{0}(G)\) is as small as possible for \(0< \alpha< 1 \). We suppose that the degree of vertex \(u_{0}\) is largest among all vertices in \(G\) and \(d_{G}(u_{0})=2r_{1}\). If \(2r_{1}=2n\), then \(G\cong W_{n,k}\), and hence the result already holds. Otherwise, \(2r_{1}< 2n \). Furthermore, we suppose that \(C_{k}^{(1)}\) is a pendent polygon with \(u_{1}\) being its cut-vertex such that \(N(u_{1})\cap V(C_{k}^{(1)})=\{w_{1},w_{k}\}\) and \(d_{G}(u_{1})=2r_{2}\), where \(u_{1}\neq u_0\). Then it is easy to see that \(2\leq r_{2}\leq r_{1}\leq n\). Now, we let \(G_{1}=G-u_1w_1-u_1w_k+u_0w_1+u_0w_k\). By an elementary computation, it follows that \begin{align*}R_{\alpha}^{0}(G)-R_{\alpha}^{0}(G_1)&=(2r_1)^{\alpha}+(2r_2)^{\alpha}-(2r_1+2)^{\alpha}-(2r_2-2)^{\alpha} \\&=\left(2r_2\right)^{\alpha}-\left(2r_2-2\right)^{\alpha}-\big((2r_1+2)^{\alpha}-(2r_1)^{\alpha}\big).\end{align*} Since \(2r_1\geq2r_2\geq4\), by lemma 2.1 we have \(R_{\alpha}^{0}(G)< R_{\alpha}^{0}(G_1)\) for \(\alpha< 0\) or \(\alpha>1\), and \(R_{\alpha}^{0}(G)>R_{\alpha}^{0}(G_1)\) for \(0< \alpha< 1\), which is contrary with the choice of \(G\). Thus, \(u_0\) is the cut-vertex of any pendent polygon. Since \(G\) is a cactus in \(\mathcal{G}_{n,k}\), we have \(G\cong W_{n,k}.\)

Next, we turn to prove Theorem 1.1.

Proof. By Lemma 2.2, \(R_{\alpha}^{0}(G)=\Phi(n,k,\alpha)\) holds for \(G\in \mathcal{T}_{n,k}\), and \(R_{\alpha}^{0}(G)=\Psi(n,k,\alpha)\) holds for \(G\cong W_{n,k}\). Now, we consider the following two cases:

Case 1. \(\alpha< 0\) or \(\alpha>1\).
Then, Lemmas 2.4--2.6 imply that \(R_{\alpha}^{0}(G)\) is minimum if \(G\in \mathcal{T}_{n,k}\). Combining this with Lemma 2.7, we can conclude that \(R_{\alpha}^{0}(G)\) is maximum if and only if \(G\cong W_{n,k}\). Thus, \((i)\) holds.

Case 1. \(0< \alpha< 1\).
By Lemmas 2.4--2.6, \(R_{\alpha}^{0}(G)\) is maximum if \(G\in \mathcal{T}_{n,k}\). Taking Lemma 2.7 into consideration, we can conclude that \(R_{\alpha}^{0}(G)\) is minimum if and only if \(G\cong W_{n,k}\). Thus, \((ii)\) also holds.

Acknowledgments

The authors would like to thank Professor Muhuo Liu for his valuable comments which lead to an improvement of the original manuscript. This paper is supported by Guangdong Province Ordinary University Characteristic Innovation Project (No.2017KTSCX020) and National Undergraduate Training Programs for Innovation and Entrepreneurship (No. 201810564014).

Competing Interests

The authors declare that they have no competing interests.

References

  1. Gutman, I., & Trinajstić, N. (1972). Graph theory and molecular orbitals. Total φ-electron energy of alternant hydrocarbons. Chemical Physics Letters, 17(4), 535-538. [Google Scholor]
  2. Kier, L. B., & Hall, L. H. (1977). Nature of structure-activity-relationships and their relation to molecular connectivity. European Journal of Medicinal Chemistry, 12(4), 307-312. [Google Scholor]
  3. Li, X., & Zheng, J. (2005). A unified approach to the extremal trees for different indices. MATCH Commun. Math. Comput. Chem, 54(1), 195-208. [Google Scholor]
  4. Ali, A., Bhatti, A. A., & Raza, Z. (2014). A note on the zeroth-order general randić index of cacti and polyomino chains.Iranian Journal of Mathematical Chemistry, 5(2), 143-152. [Google Scholor]
  5. Hu, Y., Li, X., Shi, Y., & Xu, T. (2007). Connected (n,m)-graphs with minimum and maximum zeroth-order general Randić index. Discrete Applied Mathematics, 155(8), 1044-1054. [Google Scholor]
  6. Hua, H., & Deng, H. (2007). On Unicycle Graphs with Maximum and Minimum Zeroth-order Genenal Randić Index. Journal of mathematical chemistry, 41(2), 173-181. [Google Scholor]
  7. Ye. J., Liu. M., & Yao. Y. K.C. Das, Extremal polygonal cactus for vertex-degree-based invariants, paper submitted .