The chemical graphs are graphs that have no vertex with degree greater than 4. The sigma index of a graph \(G\) is defined by \(\sum_{uv\in E(G)} (deg_{G}(u)-deg_{G}(v))^{2}\), where \(deg_{G}(u)\) stands for the degree of vertex \(u\) in \(G\). In this work, we present lower and upper bounds on the sigma index for chemical trees with a given order and number of pendent vertices. Furthermore, we solve the problem of minimizing sigma index for chemical graphs of order \(n\) having \(m\) edges and \(p\) pendent vertices.
In graph theory, irregularity measures of graphs are useful tools in network theory [6, 8, 9, 16] and chemistry [11, 15]. One of the famous irregularity measures is the Albertson irregularity index[3], and for a graph \(G\), it is defined as: \[\begin{aligned} A(G)=\sum_{uv\in E(G)}|deg_{G}(u)-deg_{G}(v)|, \end{aligned}\] where \(deg_{G}(u)\) represents the degree of vertex \(u\) in \(G\). To avoid certain shortcomings of the Albertson irregularity index, Abdo et al. [1] proposed a new measure of the irregularity of a graph which is called the total irregularity index, and it is defined as \[\begin{aligned} irr_{t}(G)=\frac{1}{2}\sum_{x,y\in V(G)}|deg_{G}(x)-deg_{G}(y)|. \end{aligned}\]
The sigma index \(\sigma(G)\) introduced in [10, 12] is one of variants of the famous Albertson irregularity index, and it is defined as \[\begin{aligned} \label{eq1} \sigma(G)=\sum_{xy\in E(G)}(deg_{G}(x)-deg_{G}(y))^{2}. \end{aligned} \tag{1}\]
Gutman et al. [12] explicitly initiated the research of the sigma index and they obtained some basic characteristics of the sigma index. Recently, Lin et al. [13] found some additional mathematical properties of the sigma index and proposed the general Albertson index. Réti [14] compared the sigma index with the Bell¡¯s degree-variance and the Collatz-Sinogowitz irregularity index, and he also gave an equality of sigma index on the complete split-like graphs. One can see [, 4, 17, 18] for other recent studies on sigma index. Motivated by these works, we continue to study the properties of sigma index. In this paper, the lower and upper bounds on the sigma index for chemical trees with a given order and number of pendent vertices are determined. Furthermore, the problem of minimizing sigma index for chemical graphs of order \(n\) having \(m\) edges and \(p\) pendent vertices is solved.
In this study, just simple connected graphs are taken into account. For such a graph \(G\), we represent the sets of vertices and edges by \(V(G)\) and \(E(G)\), respectively. Define \(m=|E(G)|\) and \(n=|V(G)|\). For \(m=n-1\), \(m=n\) and \(m=n+1\), \(G\) is a tree, unicyclic graph and bicycle graph, respectively. Recall that the chemical graphs are graphs that have no vertex with degree greater than 4. A vertex of degree one is called a pendent vertex. Let \(G-xy\) and \(G+xy\) be the graphs gotten from \(G\) by deleting the edge \(xy \in E(G)\) and by adding an edge \(xy \notin E(G)\) \((x, y \in V(G))\), respectively. Denoted by \(n_{i}\) the number of vertices of degree \(i\). We use \(S_{n}\) and \(P_{n}\) to represent the star and path on \(n\) vertices, respectively. Let \(P_{s+1}=z_{0}z_{1}\cdots z_{s}\) be the path in \(G\) with \(deg_{G}(z_{1})=deg_{G}(z_{2})=\cdots =deg_{G}(z_{s-1})=2\) (unless \(s=1\)). If \(deg_{G}(z_{0})\geq 3\) and \(deg_{G}(z_{s}) =1\), then \(P_{s+1}\) is said to be a pendent path in \(G\).
Suppose an \((n,m,p)\)-graph is an \(n\)-vertex graph with \(m\) edges and \(p\) pendent vertices. Let us define \(E_{1}=\{uv\in E(G)| deg_{G}(u)=1, deg_{G}(v)=2\}\), \(E_{2}=\{uv\in E(G)| deg_{G}(u)=1, deg_{G}(v)\geq 3\}\), \(E_{3}=\{uv\in E(G)| deg_{G}(u)=deg_{G}(v)=2\}\), \(E_{4}=\{uv\in E(G)| deg_{G}(u)=2, deg_{G}(v)\geq 3\}\) and \(E_{5}=\{uv\in E(G)| deg_{G}(u)\geq 3, deg_{G}(v)\geq 3\}\) for an \((n,m,p)\)-graph \(G\). For terminologies and notations without providing here, we refer the readers to the relevant standard book [5].
Let us use \(\pmb{\mathscr{T}}^{(1)}_{n,p}\) and \(\pmb{\mathscr{T}}^{(2)}_{n,p}\) (\(p\) is even) to denote two special types of chemical trees on \(n\) vertices and \(p\) pendent vertices (also see [7]).
Chemical trees \(\pmb{\mathscr{T}}^{(1)}_{n,p}\) (\(n\geq7\), \(3\leq p\leq \lfloor\frac{n+2}{3}\rfloor\)) and \(\pmb{\mathscr{T}}^{(2)}_{n,p}\) (\(n\geq9\), \(6\leq p\leq \lfloor\frac{n+3}{2}\rfloor\) is even) are depicted in Figure 1 and Figure 2, respectively. The chemical trees \(\pmb{\mathscr{T}}^{(1)}_{n,p}\) contain \(p-2\) vertices with maximum degree 3, which induce a tree and everyone of these vertices is adjacent to either a 2-degree vertex or another 3-degree vertex. The chemical trees \(\pmb{\mathscr{T}}^{(2)}_{n,p}\) are composed of \(\frac{p}{2}-1\) stars \(S_{5}\) which are joined together by paths whose lengths may be 0.
For an \(n\)-vertex tree \(T\) with \(p\) pendent vertices, if \(p=2\) or \(p=n-1\), \(T\) is a path or a star of order \(n\). So in what follows, the case of \(3\leq p\leq n-2\) is considered. Let \(\pmb{\mathcal{T}}_{n,p}\) be an \(n\)-vertex trees with \(p\) pendent vertices obtained from a path \(P_{n-p+1}\) of order \(n-p+1\) by attaching \(p-1\) pendent vertices to a pendent vertex of \(P_{n-p+1}\).
Lemma 2.1. Let \(T\) be a tree of order \(n\geq 5\) with \(p\) pendent vertices, where \(3\leq p\leq n-2\). Then \[\begin{aligned} \sigma(T)\leq (p-1)^{3}+(p-2)^{2}+1. \end{aligned}\]
The equality holds if and only if \(T\cong \pmb{\mathcal{T}}_{n,p}\).
Proof. We prove the lemma by induction on \(n\). For \(n =5\), we have \(p=3\), \(T\cong\pmb{\mathcal{T}}_{5,3}\) and the conclusion is true. Next, we assume that \(n\geq 6\) and the lemma holds for any tree with \(n-1\) vertices. Let \(u_{1}u_{2}\cdots u_{d+1}\) be a diameter with length \(d\) in \(T\). Since \(T\cong S_{n}\) for \(d=2\), then \(d\geq 3\). Let \(T'=T-u_{1}\).
Case 1. \(deg_{T}(u_{2})=2\).
Now, \(T'\) is an \((n-1)\)-vertex tree with \(p\) pendent vertices. By induction hypothesis, it follows that \[\begin{aligned} \sigma(T)=&\sigma(T')+(2-1)^{2}+(deg_{T}(u_{3})-2)^{2}-(deg_{T}(u_{3})-1)^{2}\\ \leq&(p-1)^{3}+(p-2)^{2}+2-2deg_{T}(u_{3})+3\\ \leq&(p-1)^{3}+(p-2)^{2}+2-4+3\\ =&(p-1)^{3}+(p-2)^{2}+1. \end{aligned}\]
With equality only when \(deg_{T}(u_{3})=2\) and \(T'\cong \pmb{\mathcal{T}}_{n-1,p}\). These imply that \(T\cong \pmb{\mathcal{T}}_{n,p}\).
Case 2. \(deg_{T}(u_{2})\geq 3\).
Let \(x_{1},x_{2},\cdots,x_{t}\), except \(u_{1}\) and \(u_{3}\), be the neighbors of \(u_{2}\), where \(t\geq 1\). Then \(x_{1},x_{2},\cdots,x_{t}\) are pendent vertices and \(T'\) is a tree of order \(n-1\) having \(p-1\) pendent vertices. Since \(t\leq p-2\), by induction hypothesis, it follows that \[\begin{aligned} \sigma(T)=&\sigma(T')+(t+2-1)^{2}+\sum_{i=1}^{t}[(t+2-deg_{T}(x_{i}))^{2}-(t+1-deg_{T}(x_{i}))^{2}]\\ &+(t+2-deg_{T}(u_{3}))^{2}-(t+1-deg_{T}(u_{3}))^{2}\\ =&\sigma(T')+(t+1)^{2}+t(2t+1)+(2t+3-2deg_{T}(u_{3}))\\ \leq&\sigma(T')+(t+1)^{2}+t(2t+1)+(2t-1)\\ \leq&(p-2)^{3}+(p-3)^{2}+1+(p-1)^{2}+2(p-2)^{2}+3(p-2)-1\\ =&(p-1)^{3}+(p-2)^{2}+1. \end{aligned}\]
The equality holds only if \(deg_{T}(u_{3})=2\) and \(T'\cong \pmb{\mathcal{T}}_{n-1,p-1}\). These mean that \(T\cong \pmb{\mathcal{T}}_{n,p}\). ◻
According to Lemma 2.1, we deduce that the extremal tree with maximum sigma index for any chemical tree with \(n\)-vertex and \(p\leq 4\) pendent vertices is \(\pmb{\mathcal{T}}_{n,p}\). In the following, one considers the case of \(p\geq5\) when one finds the maximum sigma index for any \(n\)-vertex chemical tree with \(p\) pendent vertices. For a chemical tree \(T\), bond incident degree (\(BID\) for short) index [7] is defined as \[\begin{aligned} \label{eq2} BID(T)=\sum_{xy\in E(T)}\varphi_{deg_{T}(x),deg_{T}(y)}, \end{aligned} \tag{2}\] where \(\varphi_{deg_{T}(x),deg_{T}(y)}\) is a real-valued symmetric function that relies on \(deg_{T}(x)\) and \(deg_{T}(y)\). The choices of the function \(\varphi_{deg_{T}(x),deg_{T}(y)}\) give the sigma index: \(\varphi_{deg_{T}(x),deg_{T}(y)}=(deg_{T}(x)-deg_{T}(y))^{2}\). We denote \[\begin{aligned} \label{eq3} \begin{cases} A_{1,3}&=\!-\!\varphi_{1,2}\!+\!\varphi_{1,3}\!+\!\varphi_{2,2}\!-\!\varphi_{2,3},\\ A_{1,4}&=\!-\!\varphi_{1,2}\!+ \!\varphi_{1,4}\!+\!\frac{5}{4}\varphi_{2,2}\!-\!\frac{1}{4}\varphi_{3,3}\!-\!\varphi_{2,3},\\ A_{2,4}&=\frac{1}{4}\varphi_{2,2}-\varphi_{2,3}+\varphi_{2,4}-\frac{1}{4}\varphi_{3,3},\\ A_{3,4}&=\frac{1}{4}\varphi_{2,2}- \frac{5}{4}\varphi_{3,3}+\varphi_{3,4},\\ A_{4,4}&=\frac{1}{2}\varphi_{2,2}- \frac{3}{2}\varphi_{3,3}+\varphi_{4,4},\end{cases} \end{aligned} \tag{3}\] and \[\begin{aligned} \label{eq4} \begin{cases} B_{1,2}&=\varphi_{1,2}-\varphi_{1,4}- \varphi_{2,2}+\varphi_{2,4}, \\ B_{1,3}&=\varphi_{1,3}- \varphi_{1,4}-\frac{1}{3}\varphi_{2,2}+\frac{1}{3}\varphi_{2,4},\\ B_{2,3}&=-\frac{1}{3}\varphi_{2,2}+ \varphi_{2,3}-\frac{2}{3}\varphi_{2,4}, \\ B_{3,4}&=\frac{2}{3}\varphi_{2,2}- \frac{5}{3}\varphi_{2,4}+\varphi_{3,4},\\ B_{3,3}&=\frac{1}{3}\varphi_{2,2}-\frac{4}{3}\varphi_{2,4}+\varphi_{3,3}, \\ B_{4,4}&=\varphi_{2,2}- 2\varphi_{2,4}+\varphi_{4,4}.\end{cases} \end{aligned} \tag{4}\]
Lemma 2.2. [7] Let \(T\) be a chemical trees of order \(n\) with \(p\) pendent vertices, where \(n\geq 7,\ p\geq3\). If \(BID\) index defined in (2) satisfy: (i) \(\varphi_{a,x}-\varphi_{b,x}\) is decreasing for \(x\), where \(x, a,b\ (a>b, x\geq2)\) are positive integers; (ii) \(\varphi_{2,2}+\varphi_{3,3}-2\varphi_{2,3}<0\) and (iii) \(\min\{A_{1,3},A_{1,4},A_{2,4},A_{3,4}\}>0\), \(A_{4,4}\geq 0\), where \(A_{1,3},A_{1,4},A_{2,4},A_{3,4},A_{4,4}\) are defined in (3), then \[\begin{aligned} BID(T)\geq n\cdot \varphi_{2,2}+p(\varphi_{1,2}+\varphi_{2,3}+ \varphi_{3,3}-3\varphi_{2,2})+ 2\varphi_{2,2}- 3\varphi_{3,3}. \end{aligned}\] Equality is attained only if \(T\in \pmb{\mathscr{T}}^{(1)}_{n,p}\).
Lemma 2.3. [7] Let \(T\) be a chemical trees of order \(n\) with \(p\) pendent vertices, where \(n\geq 9, p\geq6\) and the \(BID\) index defined in (2) satisfy \(\max\{B_{1,2},B_{1,3},B_{3,3},B_{3,4},B_{4,4}\}<0\) and \(B_{2,3}\leq 0\), where \(B_{1,2},B_{1,3},B_{3,4},B_{3,3},B_{4,4}\) and \(B_{2,3}\) are defined in \((4)\). Then \[\begin{aligned} BID(T)\leq n\cdot \varphi_{2,2}+p( \varphi_{1,4}-2 \varphi_{2,2}+ \varphi_{2,4})+ 3\varphi_{2,2}- 4\varphi_{2,4}, \end{aligned}\] equality is attained only if \(T\in \pmb{\mathscr{T}}^{(2)}_{n,p}\) \((6\leq k\leq \lfloor\frac{n+3}{2}\rfloor\) is even\()\).
By Lemmas 2.2 and 2.3, we can derive the following two theorems.
Theorem 2.4. Let \({MT}\) be a chemical tree with \(n\) vertices and \(p\) pendent vertices, where \(n\geq 7\) and \(p\geq3\). Then \[\begin{aligned} \sigma({MT})\geq 2p. \end{aligned}\]
Equality holds if and only if \({MT}\in \pmb{\mathscr{T}}^{(1)}_{n,p}\).
Theorem 2.5. Let \({MT}\) be an \(n\)-vertex chemical tree with \(p\) pendent vertices, where \(n\geq 7\) and \(p\geq5\). Then \[\begin{aligned} \sigma({MT})\leq13p-16, \end{aligned}\] with equality if and only if \({MT}\in \pmb{\mathscr{T}}^{(2)}_{n,p}\) (\(p\) is even and \(6\leq p\leq \lfloor\frac{n+3}{2}\rfloor\)).
Note that \(m\geq n-1\) and \(p\geq0\) for all chemical \((n,m,p)\)-graphs. When \(p=0\), by the definition of sigma index, the chemical \((n,m,0)\)-graph with minimal value of sigma index is an \(l\)-regular (\(l=2,3,4\)) graph. Furthermore, a chemical \((n,n-1,2)\)-graph is a path, the minimum sigma index of chemical \((n,n-1,p)\)-graphs is obtained in Section 2. So in what follows, for any chemical \((n,m,p)\)-graph, we shall suppose that \(m\geq n\) and \(p\geq1\).
First, let us seek the minimal sigma index of \((n,m,p)\)-graphs with \(m\geq n\) and \(p\geq1\). Let us denote the set of all \((n,m,p)\)-graphs (resp. chemical \((n,m,p)\)-graphs) with \(m\geq n\) and \(p\geq1\) by \({G}_{n,m,p}\) (resp. \({MG}_{n,m,p}\)).
Assume that \(m', n'\) and \(p\) are three positive integers with \(m'=\frac{3n'-2p}{2}\geq n'\), where \(n'\geq 6\). Let \(H\) be an \((n',m',p)\)-graph in which every non-pendent vertex is degree 3. Then we call \(H\) an \((n',m',p,3)\)-semi-regular graph. one can easily see that for any \((n',m',p,3)\)-semi-regular graph, \(p\geq 1\) for \(m'\geq n'+2\), \(p\geq 2\) for \(m'=n'+1\) and \(p\geq 3\) for \(m'=n'\).
Let \( {\mathbb{G}}_{n,m,p}\) be a collection of \((n,m,p)\)-graphs arising from \((n',m',p,3)\)-semi-regular graphs by adding several new vertices on each pendent edge. Since \(p+n_{2}+n_{3}=n\) and \(p+2n_{2}+3n_{3}=2m\) for \( {\mathbb{G}}_{n,m,p}\), it shows that \(n_{2}=3n-2m-2p\) and the number of new vertices added is \(3n-2m-2p\). One can easily see that \( {\mathbb{G}}_{n,m,p}\subseteq {G}_{n,m,p}\) (resp. \( {MG}_{n,m,p}\)). For instance, in Figure 3 and Figure 4, four \((10, 10, 5, 3)\)-semi-regular graphs and (15,15,5)-graphs in \( {\mathbb{G}}_{15,15,5}\) are depicted, respectively.
The graphs of \(U_{n}^{1}\), \(U_{n}^{2}\), \(U_{n}^{3}\) and \(B_{n}\) used in the following contents are
depicted in Figure 5.
Theorem 3.1. Let \(G\in {G}_{n,n,1}\) or \( {G}_{n,n+1,1}\). Then \[\begin{aligned} \sigma(G)\geq 4. \end{aligned}\]
Equality occurs if and only if \(G\in U_{n}^{1}\), \(n\geq 5, 3\leq s\leq n-2\), or \(G\in B_{n}\), \(n\geq 6, 4\leq s\leq n-2\) (see Figure 5).
Proof. For \(G\in {G}_{n,n,1}\) or \( {G}_{n,n+1,1}\), one gets \(E(G)=\bigcup\limits_{i=1}^{5} E_{i}\) and \(|E_{1}|+|E_{2}|=1\). By using (1), it follows that \[\begin{aligned} \sigma(G)=&\sum_{uv\in E(G)}(deg_{G}(u)-deg_{G}(v))^{2}\notag\\ =&|E_{1}|+\sum_{uv\in E_{2}}(deg_{G}(v)-1)^{2}+\sum_{uv\in E_{4}}(deg_{G}(v)-2)^{2}+\sum_{uv\in E_{5}}(deg_{G}(u)-deg_{G}(v))^{2}\notag\\ \geq& |E_{1}|+\sum_{uv\in E_{2}}(deg_{G}(v)-1)^{2}+\sum_{uv\in E_{4}}(deg_{G}(v)-2)^{2}\notag\\ \geq& |E_{1}|+4|E_{2}|+|E_{4}|\notag\\ =& 1+3|E_{2}|+|E_{4}|.\label{eq2a} \end{aligned} \tag{5}\]
Case 1. \(G\in {G}_{n,n,1} (n\geq 5)\) is a unicyclic graph.
Now, \(|E_{5}|=0\). For \(|E_{1}|=1, |E_{2}|=0\), one has \(|E_{4}|=3\). From (5), we get \(\sigma(G)\geq 4\). If \(\sigma(G)= 4\), then (I) \(|E_{1}|=1, |E_{2}|=0\); (II) \(deg_{G}(u)=2, deg_{G}(v)=3\) for \(uv\in E_{4}\) and \(|E_{4}|=3\). That is \(G\in U_{n}^{1}\) (\(3\leq s\leq n-2\)).
For \(|E_{1}|=0, |E_{2}|=1\), one has \(|E_{4}|=2\). From (5), we get \(\sigma(G)\geq 6>4\).
Case 2. \(G\in {G}_{n,n+1,1} (n\geq 6)\) is a bicyclic graph.
For \(|E_{1}|=1, |E_{2}|=0\), one has \(|E_{4}|\geq 3\). From (5), we derive \(\sigma(G)\geq 4\). If \(\sigma(G)= 4\), then (I) \(|E_{1}|=1, |E_{2}|=0\); (II) \(deg_{G}(u)=2, deg_{G}(v)=3\) for \(uv\in E_{4}\) and \(|E_{4}|=3\); (III) \(deg_{G}(u)=deg_{G}(v)=3\) for \(uv\in E_{5}\) since every edge of \(E_{4}\) is associated with an edge of \(E_{5}\) and a 2-degree vertex. This means that \(G\in B_{n}\) (\(4\leq s\leq n-2\)).
For \(|E_{1}|=0, |E_{2}|=1\), one has \(|E_{4}|\geq 2\). From (5), we derive \(\sigma(G)\geq 6>4\). ◻
Theorem 3.2. Let \(G\in {G}_{n,n,2}\). Then \[\begin{aligned} \sigma(G)\geq 6, \end{aligned}\] where equality holds only if \(G\in U_{n}^{2}\), \(n\geq 8\), \(t\geq3,\ 3\leq s\leq n-5\) or \(G\in U_{n}^{3}\), \(n\geq 7\), \(t\geq2,\ 3\leq s\leq n-4\) (see Figure 5).
Proof. For \(G\in {G}_{n,n,2}\), \(E(G)=\bigcup\limits_{i=1}^{5} E_{i}\) and \(|E_{1}|+|E_{2}|=2\). By using (1), we derive \[\begin{aligned} \sigma(G)=&\sum_{uv\in E(G)}(deg_{G}(u)-deg_{G}(v))^{2}\notag\\ =&|E_{1}|+\sum_{uv\in E_{2}}(deg_{G}(v)-1)^{2}+\sum_{uv\in E_{4}}(deg_{G}(v)-2)^{2}+\sum_{uv\in E_{5}}(deg_{G}(u)-deg_{G}(v))^{2}\notag\\ \geq& |E_{1}|+4|E_{2}|+|E_{4}|\notag\\ =& 2+3|E_{2}|+|E_{4}|.\label{eq3a} \end{aligned} \tag{6}\]
If \(|E_{1}|=2, |E_{2}|=0\), then \(|E_{4}|\geq4\). From (6), one has \(\sigma(G)\geq 6\). If \(\sigma(G)=6\), then (I) \(|E_{1}|=2, |E_{2}|=0\); (II) When \(uv\in E_{4}\), \(deg_{G}(u)=2, deg_{G}(v)=3\) and \(|E_{4}|=4\); (III) For \(uv\in E_{5}\), \(deg_{G}(u)=deg_{G}(v)\). Moreover, since every edge of \(E_{4}\) is associated with an edge of \(E_{5}\) and a 2-degree vertex, respectively, then \(deg_{G}(u)=deg_{G}(v)=3\) for \(uv\in E_{5}\). These mean that \(G\in U_{n}^{2}\) (\(t\geq 3,\ 3\leq s\leq n-5\)) or \(G\in U_{n}^{3}\) (\(t\geq 2,\ 3\leq s\leq n-4\)).
If \(|E_{1}|=1, |E_{2}|=1\), then \(|E_{4}|\geq 3\). From (6), one has \(\sigma(G)\geq 8> 6\).
If \(|E_{1}|=0, |E_{2}|=2\), then \(|E_{4}|\geq 2\). From (6), one has\(\sigma(G)\geq 10> 6\). ◻
Lemma 3.3. Let \(G\in {G}_{n,m,p}\). Suppose \(x\in V(G)\) is a 2-degree vertex that is not contained in any 3-length cycle and any pendent path. Then there exists a graph \(G'\in {G}_{n,m,p}\) satisfying one of the following properties:
1) \(\sigma(G')<\sigma(G)\);
2) \(\sigma(G')=\sigma(G)\) and \(G'\) contains more 2-degree vertices in pendent paths than \(G\).
Proof. Assume that the neighbors of \(x\) are \(y\) and \(z\) with \(deg_{G}(y)=a\geq deg_{G}(z)=b\geq 2\). Let \(u\) be a pendent vertex in \(G\) and \(v\) be the adjacent vertex of \(u\) with \(deg_{G}(v)=c\geq 2\). Set \(G'=G-xy-xz-uv+yz+ux+vx\). Then \(G'\in {G}_{n,m,p}\). Note that \[\begin{aligned} \sigma(G)-\sigma(G')=&(a-2)^{2}+(b-2)^{2}+(c-1)^{2}-(c-2)^{2}-(a-b)^{2}-(2-1)^{2}\\ =&2(a-2)(b-2)+2(c-2). \end{aligned}\]
For \(a\geq b>2\) or \(c>2\), one gets \(\sigma(G)>\sigma(G')\). On the other hand, only when \(b=2\) (\(a=2\) implies that \(b=2\)) and \(c=2\), \(\sigma(G)=\sigma(G')\). Now, obviously, \(G'\) contains more 2-degree vertices in pendent paths than \(G\). ◻
Theorem 3.4. Let \(G\in {G}_{n,m,p}\), where \(p\geq1\) for \(m\geq n+2\), or \(p\geq 2\) for \(m=n+1\), or \(p\geq3\) for \(m=n\). Then \[\begin{aligned} \sigma(G)\geq 2p, \end{aligned}\] with equality holding if and only if \(G\in {\mathbb{G}}_{n,m,p}\) with \(3n\geq 2m+3p\).
Proof. Pick \(G\in {G}_{n,m,p}\) such that \(G\) has the minimum sigma index. By this supposition and Lemma 3.3, without loss of generality, we assume that all 2-degree vertices, except the 2-degree vertices on the 3-length cycles, lie on the pendent paths in \(G\). In what follows, we differentiate the following two cases.
Case 1. \(G\) does not contain the 2-degree vertices on the 3-length cycle.
Clearly, \(E(G)=\bigcup\limits_{i=1}^{5} E_{i}\), \(|E_{1}|+|E_{2}|=p\) and \(|E_{1}|=|E_{4}|\). By using (1), one has \[\begin{aligned} \sigma(G) =&|E_{1}|+\sum_{uv\in E_{2}}(deg_{G}(v)-1)^{2}+\sum_{uv\in E_{4}}(deg_{G}(v)-2)^{2}+\sum_{uv\in E_{5}}(deg_{G}(u)-deg_{G}(v))^{2}\notag\\ \geq& |E_{1}|+4|E_{2}|+|E_{4}|\notag\\ =& 2p+2|E_{2}|\notag\\ \geq& 2p.\label{eq4a} \end{aligned} \tag{7}\]
All inequalities in the above argument have to be equalities if the equality in (7) holds. Thus we have (I) \(deg_{G}(u)=2, deg_{G}(v)=3\) for \(uv\in E_{4}\); (II) \(|E_{1}|=p\), \(|E_{2}|=0\); (III) \(deg_{G}(u)=deg_{G}(v)=3\) for \(uv\in E_{5}\) and \(n_{2}\geq p\) since an edge of \(E_{4}\) is incident to one edge of \(E_{5}\) and a 2-degree vertex, respectively. Hence, the maximal degree of \(G\) is 3 and \(p+n_{2}+n_{3}=n\), \(p+2n_{2}+3n_{3}=2m\) for \(G\in {G}_{n,m,p}\). It follows that \(n_{2}= 3n-2m-2p\), and thus \(3n\geq 2m+3p\), \(G\in {\mathbb{G}}_{n,m,p}\).
Case 2. \(G\) contains at least a 2-degree vertex on the 3-length cycles.
Let us use \(r\) to denote the number of the 3-length cycles having 2-degree vertices in \(G\). In this case, \(E(G)=\bigcup\limits_{i=1}^{5} E_{i}\), \(|E_{1}|+|E_{2}|=p\) and \(|E_{4}|=|E_{1}|+2r\), where \(r>0\). By using (1), we have \[\begin{aligned} \sigma(G) =&|E_{1}|+\sum_{uv\in E_{2}}(deg_{G}(v)-1)^{2}+\sum_{uv\in E_{4}}(deg_{G}(v)-2)^{2}+\sum_{uv\in E_{5}}(deg_{G}(u)-deg_{G}(v))^{2}\\ \geq& |E_{1}|+4|E_{2}|+|E_{4}|\\ =& 2p+2|E_{2}|+2r\\ >& 2p. \end{aligned}\] The proof is completed. ◻
For any graph in \(U_{n}^{1}\), \(U_{n}^{2}\), \(U_{n}^{3}\), \(B_{n}\) and \({\mathbb{G}}_{n,m,p}\), the maximum degree of this graph is less than 4, hence, for \(G\in {MG}_{n,m,p}\), Theorems 3,1, 3.2 and 3.4 also hold. Therefore, the following corollaries can be obtained immediately.
Corollary 3.5. Let \(G\in {MG}_{n,n,p}\), that is \(G\) is an \(n\)-vertex chemical unicyclic graph with \(p\) pendent vertices. Then for \(p=1\), \[\begin{aligned} \sigma(G)\geq 4, \end{aligned}\] where equality occurs if and only if \(G\in U_{n}^{1}\), \(n\geq 5, 3\leq s\leq n-2\); for \(p=2\), \[\begin{aligned} \sigma(G)\geq 6, \end{aligned}\] where equality holds if and only if \(G\in U_{n}^{2}\), \(n\geq 8\), \(t\geq3,\ 3\leq s\leq n-5\) or \(G\in U_{n}^{3}\), \(n\geq 7\), \(t\geq2,\ 3\leq s\leq n-4\); and for \(p\geq 3\), \[\begin{aligned} \sigma(G)\geq 2p, \end{aligned}\] where equality holds only if \(G\in {\mathbb{G}}_{n,n,p}\) with \(n\geq 3p\).
Corollary 3.6. Let \(G\in {MG}_{n,n+1,p}\), that is \(G\) is an \(n\)-vertex chemical bicyclic graph with \(p\) pendent vertices. Then for \(p=1\), \[\begin{aligned} \sigma(G)\geq 4, \end{aligned}\] where equality holds if and only if \(G\in B_{n}\), \(n\geq 6, 4\leq s\leq n-2\); and for \(p\geq 2\), \[\begin{aligned} \sigma(G)\geq 2p, \end{aligned}\] where equality holds if and only if \(G\in {\mathbb{G}}_{n,n+1,p}\) with \(n\geq 3p+2\).
Corollary 3.7. Let \(G\in {MG}_{n,m,p}\) \((m\geq n+2)\), that is \(G\) is an \(n\)-vertex chemical \((\!m\!-\!n\!+\!1\!)\)-cyclic graph with \(p\) pendent vertices. Then for \(p\geq1\), \[\begin{aligned} \sigma(G)\geq 2p, \end{aligned}\] where equality occurs only if \(G\in {\mathbb{G}}_{n,m,p}\) with \(3n\geq 2m+3p\).
Sun is supported by the Natural Science Foundation of Shanxi Province of China (2023030). Mei is supported by the Shanxi Scholarship Council of China (2022-149).
The authors declare no conflict of interest regarding the publication of this paper.