In this note, we first show that the general Zagreb index can be obtained from the \(M-\)polynomial of a graph by giving a suitable operator. Next, we obtain \(M-\)polynomial of some cactus chains. Furthermore, we derive some degree based topological indices of cactus chains from their \(M-\)polynomial.
The concept of degree is analogous to the concept of valence in organic chemistry with a limitation that degree of any vertex in any chemical graph is at most 4. This gives graph theory a broad way to chemistry. It is always interesting to find some properties of graphs or molecular graphs which are invariant. Topological indices and polynomials are foremost among them. Over the last decade there are numerous research papers devoted to topological indices and polynomials. Several topological indices have been defined in the literature. For various topological indices one can refer to [1, 2, 3, 4, 5, 6, 7,8].
Let \(G=(V,E)\) be a simple, undirected graph. Let \(V(G)\) be the vertex set and \(E(G)\) be the edge set of the graph \(G\), respectively. The degree \(d_G(v)\) of a vertex \(v\in V(G)\) is the number of edges incident to it in \(G\). Let \(\{v_1,v_2,…,v_n\}\) be the vertices of \(G\) and let \(d_i=d_G(v_i)\). A graph \(G\) is said to be \(r-\) regular if degree of each vertex in \(G\) is \(r\). A graph is called cycle if it is \(2-\) regular. A cactus graph is a connected graph in which any two simple cycles have at most one vertex in common. Every cycle of cactus graph is chordless and every block of a cactus graph is either an edge or a cycle. If all blocks of a cactus graph are triangular then it is called triangular cacti. If all the triangles of a triangular cactus graph has at most two cut-vertices and each cut-vertex is shared by exactly two triangles then we say that triangular cactus graph is a chain triangular cactus. In chain triangular cactus if we replace triangles by cycles of length 4 then we obtain cacti whose every block is \(C_{4}\), such cacti are called square cacti. For ortho-chain square cactus the cut vertices are adjacent and a para-chain square cactus their cut vertices are not adjacent. Recent study on some cactus chain can be found in [9, 10, 11] and references cited therein. For undefined graph theoretic terminology used in this paper can be found in [12].
The general form of degree-based topological index of a graph is given by $$TI(G)=\sum_{e=uv\in G}f(d_G(u),d_G(v))$$ where \(f=f(x,y)\) is a function appropriately chosen for the computation. Table 1 gives the standard topological indices defined by \(f(x,y)\).
The \(M-polynomial\) [13] was introduced in 2015 by Deutch and Klav\(\check{\text{z}}\)ar and is found useful in determining many degree-based topological indices (listed in Table 1).Definition 1.[13] Let \(G\) be a graph. Then \(M-polynomial\) of \(G\) is defined as $$M(G;x,y)=\sum _{i\le j}m_{ij}(G)x^iy^j,$$ where \(m_{ij}, i, j\ge1\), is the number of edges \(uv\) of \(G\) such that \(\{d_G(u), d_G(v)\}=\{i,j\}\) [14].
Recently, the study of \(M-polynomial\) are reported in [15, 16, 17, 18, 19]. The Table 1 was given by Deutch and Klav\(\check{\text{z}}\)ar to derive degree based topological indices from the \(M-\) polynomial.| Notation | Topological Index | \(f(x,y)\) | Derivation from \(M(G;x,y)\) |
|---|---|---|---|
| \(M_1(G)\) | First Zagreb | \(x+y\) | \((D_x+D_y)(M(G;x,y)) |_{x=y=1}\) |
| \(M_2(G)\) | Second Zagreb | \(xy\) | \((D_xD_y)(M(G;x,y)) |_{x=y=1}\) |
| \(^{m}M_2(G)\) | Second modified Zagreb | \(\frac{1}{xy}\) | \((S_xS_y)(M(G;x,y)) |_{x=y=1}\) |
| \(S_{D}(G)\) | Symmetric division index | \(\frac{x^2+y^2}{xy}\) | \((D_xS_y+D_yS_x)(M(G;x,y)) |_{x=y=1}\) |
| \(H(G)\) | Harmonic | \(\frac{2}{x+y}\) | \(2S_xJ(M(G;x,y)) |_{x=1}\) |
| \(I_{n}(G)\) | Inverse sum index | \(\frac{xy}{x+y}\) | \(S_xJD_xD_y(M(G;x,y)) |_{x=1}\) |
| \(R_{\alpha}(G)\) | General Randi\'{c} index | \((xy)^\alpha\) | \(D_xD_y(M(G;x,y)) |_{x=y=1}\) |
| Notation | Topological Index | \(f(x,y)\) | Derivation from \(M(G;x,y)\) |
|---|---|---|---|
| \(\chi_{\alpha}(G)\) | General sum connectivity [7] | \((x+y)^\alpha\) | \(D^{\alpha}_x(J(M(G;x,y))) |_{x=1}\) |
| \(M^{\alpha}_1(G)\) | First general Zagreb [21] | \(x^{\alpha-1}+y^{\alpha-1}\) | \((D^{\alpha-1}_x+D^{\alpha-1}_y)(M(G;x,y)) |_{x=y=1}\) |
| Notation | Topological Index | \(f(x,y)\) | Derivation from \(M(G;x,y)\) |
|---|---|---|---|
| \(M_{(a,b)}(G)\) | General Zagreb index [22] | \(x^{a}y^{b}+x^{b}y^{a}\) | \((D^{a}_xD^{b}_y+D^{b}_xD^{a}_y)(M(G;x,y)) |_{x=y=1}\) |
In this section, we obtain \(M-\) polynomials of two general cactus chains namely para cacti chain and ortho-cacti chain of cycles. We first compute \(M-\) polynomial of para cacti chain of cycles denoted by \(C^{n}_{m}\) where \(m\) is the length of each cycle and \(n\) is the length of the chain. Every block in \(C^{n}_{m}\) is a cycle \(C_{m}\).
The following theorem gives the \(M-\) polynomial of \(C^{n}_{m}.\)Theorem 2. Let \(C^{n}_{m}\) be para cacti chain of cycles for \(m\ge 3, n\ge 2.\) Then \begin{eqnarray*} M(C^{n}_{m};x,y)&=&(mn-4n+4)x^2y^2+4(n-1)x^2y^4. \end{eqnarray*}
Proof. The para cacti chain of cycles \(C^{n}_{m}\) has \(mn-n+1\) vertices and \(mn\) edges. The edge set of \(C^{n}_{m}\) can be partitioned as, \begin{eqnarray*} |E_{\{2,2\}}|&=&|\{uv\in E(C^{n}_{m}): d_{C^{n}_{m}}(u)=2 \;\; and \;\; d_{C^{n}_{m}}(v)=2\}|=(mn-4n+4).\\ |E_{\{2,4\}}|&=&|\{uv\in E(C^{n}_{m}): d_{C^{n}_{m}}(u)=2 \;\; and \;\; d_{C^{n}_{m}}(v)=4\}|=4(n-1). \end{eqnarray*} Thus, by using definition of \(M-polynomial\) we have, $$ M(C^{n}_{m};x,y)=(mn-4n+4)x^2y^2+4(n-1)x^2y^4. $$
Corollary 3. Let \(C^{n}_{m}\) be para cacti chain of cycles for \(m\ge 3, n\ge 2.\) Then $$M_{a,b}(C^{n}_{m})=2(mn-4n+4)2^{a+b}+4(n-1)2^{a+b}(2^{a}+2^{b}).$$
Proof. To derive general Zagreb index from \(M-\)polynomial we use the operator given in Table 3. Now, \begin{eqnarray*} M_{a,b}(C^{n}_{m})&=&(D^{a}_xD^{b}_y+D^{b}_xD^{a}_y)(M(C^{n}_{m};x,y)) |_{x=y=1}\\ &=& (D^{a}_xD^{b}_y+D^{b}_xD^{a}_y)((mn-4n+4)x^2y^2+4(n-1)x^2y^4)|_{x=y=1}\\ &=& (D^{a}_xD^{b}_y)((mn-4n+4)x^2y^2+4(n-1)x^2y^4)\\&&+(D^{b}_xD^{a}_y)((mn-4n+4)x^2y^2+4(n-1)x^2y^4)|_{x=y=1}\\ &=&2(mn-4n+4)2^{a+b}+4(n-1)2^{a+b}(2^{a}+2^{b}). \end{eqnarray*}
The expression obtained above, i.e., $$M_{a,b}(C^{n}_{m})=2(mn-4n+4)2^{a+b}+4(n-1)2^{a+b}(2^{a}+2^{b})$$ is same expression obtained in [9], Theorem 1. This shows that the \(M-\)polynomial has an extra advantage than the general Zagreb index as one can derive about 10 (listed in Tables 1, 2 and 3) degree-based topological indices from the \(M-\)polynomial including general Zagreb index so far. The following corollary gives the several topological indices of para cacti chain of cycles derived from \(M-\)polynomial.Corollary 4. Let \(C^{n}_{m}\) be para cacti chain of cycles for \(m\ge 3, n\ge 2.\) Then
Proof. Using the above Theorem 2 and column 4 of Table 1, we get the desired results.
Corollary 5. Let \(Q_{n}\) be para-chain square cactus graph for \( n\ge 2.\) Then \begin{eqnarray*} M(Q_{n};x,y)&=&4x^2y^2+4(n-1)x^2y^4. \end{eqnarray*}
Proof. Taking \(m=4\) in the Theorem 2, we get the desired result.
Corollary 6. Let \(Q_{n}\) be para-chain square cactus graph for \( n\ge 2.\) Then
Corollary 7. Let \(Q_{n}\) be para-chain square cactus graph for \( n\ge 2.\) Then \begin{eqnarray*} M(Q_{n};x,y)&=&(2n+4)x^2y^2+4(n-1)x^2y^4. \end{eqnarray*}
Proof. Taking \(m=6\) in the Theorem 2, we get the desired result.
Corollary 8. Let \(L_{n}\) be para-chain hexagonal cactus graph for \( n\ge 3.\) Then
Theorem 9. Let \(CO^{n}_{m}\) be ortho cacti chain of cycles for \(m\ge 3, n\ge 2.\) Then \begin{eqnarray*} M(CO^{n}_{m};x,y)&=&(mn-3n+2)x^2y^2+2nx^2y^4+(n-1)x^4y^4. \end{eqnarray*}
Proof. The \(CO^{n}_{m}\) be ortho-chain cacti of cycles has \(mn-n+1\) vertices and \(mn\) edges. The edge partition of \(CO^{n}_{m}\) is given by, \begin{eqnarray*} E_{\{2,2\}}&=&{\{uv\in E(CO^{n}_{m}): d_{CO^{n}_{m}}(u)=2 \;\; and \;\; d_{CO^{n}_{m}}(v)=2\}},\\ E_{\{2,4\}}&=&{\{uv\in E(CO^{n}_{m}): d_{CO^{n}_{m}}(u)=2 \;\; and \;\; d_{CO^{n}_{m}}(v)=4\}},\\ E_{\{4,4\}}&=&{\{uv\in E(CO^{n}_{m}): d_{CO^{n}_{m}}(u)=4 \;\; and \;\; d_{CO^{n}_{m}}(v)=4\}},\\ \text{Now,}\;\; |E_{\{2,2\}}|&=&mn-3m+2,\\ |E_{\{2,4\}}|&=&2n,\\ |E_{\{4,4\}}|&=&n-1. \end{eqnarray*} Thus, the \(M-polynomial\) of \(CO^{n}_{m}\) is $$ M(CO^{n}_{m};x,y)=(mn-3n+2)x^2y^2+2nx^2y^4+(n-1)x^4y^4.$$
Corollary 10. Let \(CO^{n}_{m}\) be ortho cacti chain of cycles for \(m\ge 3, n\ge 2.\) Then
Proof. Using the Theorem 9 and column 4 of Table 1, we get the desired results.
Now, we consider chain triangular cactus as shown in Figure 3, denoted by \(T_{n}\), where \(n\) is the length of the \(T_{n}\). \(T_{n}\) is special case of \(CO^{n}_{m}\) for \(m=3.\)
Corollary 11. Let \(T_{n}\) be the chain triangular cactus for \(n\ge 2\). Then \begin{eqnarray*} M(T_{n};x,y)&=&2x^2y^2+2nx^2y^4+(n-1)x^4y^4. \end{eqnarray*}
Proof. The proof follows by substituting \(m=3\) in Theorem 9.
Corollary 12. Let \(T_{n}\) be the chain triangular cactus for \(n\ge 2\). Then
Corollary 13. Let \(O_{n}\) be the ortho-chain square cactus for \(n\ge 2\). Then \begin{eqnarray*} M(O_{n};x,y)&=&(n+2)x^2y^2+2nx^2y^4+(n-1)x^4y^4. \end{eqnarray*}
Proof. The proof follows by substituting \(m=4\) in Theorem 9.
Corollary 14. Let \(O_{n}\) be the ortho-chain square cactus for \(n\ge 2\). Then
Theorem 15. Let \(Q(m,n)\) be ortho-chain for \(m, n\ge 2.\) Then \begin{eqnarray*} M(Q(m,n);x,y)&=&\frac{m(n-1)(n-2)}{2}x^{n-1}y^{n-1}+m(n-1)x^{n-1}y^{m+n-2}+ \frac{m(n-1)}{2}x^{m+n-2}y^{m+n-2}. \end{eqnarray*}
Proof. The edge partition of \(Q(m,n)\) is partitioned into the following subsets, \begin{eqnarray*} E_{1}&=&{\{uv\in E(Q(m,n)): d_{Q(m,n)}(u)=d_{Q(m,n)}(v)=(n-1)\}},\\ E_{2}&=&{\{uv\in E(Q(m,n)): d_{Q(m,n)}(u)=(n-1) \;\; and \;\; d_{Q(m,n)}(v)=(m+n-2)\}},\\ E_{3}&=&{\{uv\in E(Q(m,n)): d_{Q(m,n)}(u)=d_{Q(m,n)}(v)=(m+n-2)\}},\\ \text{Now,}\;\; |E_{1}|&=&\frac{m(n-1)(n-2)}{2},\\ |E_{2}|&=&m(n-1),\\ |E_{3}|&=&\frac{m(n-1)}{2}. \end{eqnarray*} Thus, the \(M-polynomial\) of \(Q(m,n)\) is $$M(Q(m,n);x,y)=\frac{m(n-1)(n-2)}{2}x^{n-1}y^{n-1}+m(n-1)x^{n-1}y^{m+n-2}+ \frac{m(n-1)}{2}x^{m+n-2}y^{m+n-2}.$$
In the para-cacti chain \(C^{n}_{m}\), if we join a new vertex and each cycle of length \(m \ge 3\), \((C_{m}+K_{1})\) then we call it as wheel chain, denoted by \(W^{n}_{m}.\) The number of vertices and edges of \(W^{n}_{m}\) are \(mn+1\) and \(2mn\), respectively. In the following theorem we calculate the \(M-\)polynomial of \(W^{n}_{m}.\)Theorem 16. Let \(W^{n}_{m}\) be wheel chain for \(m \ge 3, n\ge 2.\) Then \begin{eqnarray*} M(W^{n}_{m};x,y)&=&2(m(n-1)-3n+4)x^{3}y^{3}+4(n-1)x^{3}y^{6}+2(m-1)x^{3}y^{m}+2(n-1)x^{6}y^{m}. \end{eqnarray*}
Proof. The edge partition of \(W^{n}_{m}\) is partitioned into the following subsets, \begin{eqnarray*} E_{1}&=&{\{uv\in E(W^{n}_{m}): d_{W^{n}_{m}}(u)=d_{W^{n}_{m}}(v)=3\}},\\ E_{2}&=&{\{uv\in E(W^{n}_{m}): d_{W^{n}_{m}}(u)=3 \;\; and \;\; d_{W^{n}_{m}}(v)=6\}},\\ E_{3}&=&{\{uv\in E(W^{n}_{m}): d_{W^{n}_{m}}(u)=3 \;\; and \;\; d_{W^{n}_{m}}(v)=m\}},\\ E_{4}&=&{\{uv\in E(W^{n}_{m}): d_{W^{n}_{m}}(u)=6 \;\; and \;\; d_{W^{n}_{m}}(v)=m\}},\\ \text{Now,}\;\; |E_{1}|&=&mn-4n+4,\\ |E_{2}|&=&4(n-1),\\ |E_{3}|&=&mn-2n+2,\\ |E_{4}|&=&2(n-1). \end{eqnarray*} Thus, the \(M-polynomial\) of \(W^{n}_{m}\) is $$M(W^{n}_{m};x,y)=(mn-4n+4)x^{3}y^{3}+4(n-1)x^{3}y^{6}+(mn-2n+2)x^{3}y^{m}+2(n-1)x^{6}y^{m}.$$
Corollary 17. Let \(W^{n}_{4}\) be the wheel chain graph for \(n\ge 2\). Then \begin{eqnarray*} M(W^{n}_{4};x,y)&=&4x^{3}y^{3}+4(n-1)x^{3}y^{6}+2(n+1)x^{3}y^{4}+2(n-1)x^{6}y^{4}. \end{eqnarray*}
Using Theorem 16 and Tables 1, 2 and 3 one can easily obtain topological indices of wheel chain graph \(W^{n}_{4}\). Since it is a routine task, we omit the calculation here.