Second Zagreb indices of transformation graphs and total transformation graphs

1. Introduction

Let \(G = (V,E)\) be a graph. We denote the number of vertices of \(G\) by \(n\) and the number of edges by \(m\), i.e., \(|V(G)| = n\) and \(|E(G)| = m\). The degree of a vertex \(v\), denoted by \(d_G(v)\) is the number of edges incident to \(v\). For undefined terminologies, we refer the reader to [1]. A graph invariant is any function on a graph that does not depend on a labeling of its vertices and are called topological indices. Hundreds of different invariants have been employed to date (with unequal success) in QSAR/QSPR studies. Among them two are Zagreb indices. Due to their chemical relevance, they have been subject of numerous papers in literature [2, 3, 4, 5]. There two invariants are called the first Zagreb index and second Zagreb index [6, 7, 8, 9, 10, 11] and are defined as: $$ M_1(G) = \sum_{u \in V(G)} d_G(u)^2 \hspace{10mm} \mbox{and} \hspace{10mm} M_2(G) = \sum_{uv \in E(G)} d_G(u)\,d_G(v), $$ respectively. In fact, one can rewrite the first Zagreb index as: $$ M_1(G) = \sum_{uv \in E(G)} \big[ d_G(u) +d_G(v) \big] . $$ Noticing the contribution of nonadjacent vertex pairs when computing the weighted Winer polynomials of certain composite graphs, the authors in [6] defined the first Zagreb coindex and the second Zagreb coindex as: $$ \overline{M_1}(G) = \sum_{uv \notin E(G)} \big[ d_G(u) +d_G(v) \big] \hspace{10mm} \mbox{and} \hspace{10mm} \overline{M_2}(G) = \sum_{uv \notin E(G)} d_G(u)\,d_G(v), $$ respectively.

1.1. Transformation and total transformation graphs

Transformation graphs receives information from the original graph and converts source information into a new structure. If it is possible to figure out the given graph from the transformed graph in polynomial time, such operation may be used to survey miscellaneous structural properties of the original graph considering the transformation graphs. Therefore it fosters the research of transformation graphs and their structural properties [12].

Sampathkumar [13] introduced the concepts of semitotal-point graph and semitotal-line graph which are stated as follows:

Let \(G=(V,E)\) be a graph. The semitotal-line graph \(T_2(G)\) is a graph with \(V(T_2(G)) = V(G) \cup E(G)\) and any two vertices \(u,v \in T_2(G)\) are adjacent if and only if

1. \(u\) and \(v\) are adjacent edges in \(G\), and
2. one is a vertex of \(G\) and other is an edge of \(G\) incident with it.

Note that the definition of semitotal-line graph and middle graphs [14] are identical. These two concepts have been introduced in the same year.

The semitotal-point graph \(T_1(G)\) is a graph with \(V(T_1(G)) = V(G) \cup E(G)\) and any two vertices \(u,v \in T_1(G)\) are adjacent if and only if

1. \(u\) and \(v\) are adjacent vertices in \(G\) and
2. one is a vertex of \(G\) and other is an edge of \(G\) incident with it.

The total graph \(T(G)\) of a graph \(G\) is the graph whose vertex set is \(V(G)\cup E(G)\), and in which two vertices are adjacent if and only if they are adjacent or incident in \(G\) [15].

Let \(G=(V,E)\) be a graph and \(x,y,z\) be three variables taking values \(+\) or \(-\). The total transformation graph \(G^{xyz}\) is a graph having \(V(G) \cup E(G)\) as a vertex set, and for \(\alpha, \beta \in V(G) \cup E(G)\), \(\alpha\) and \(\beta\) are adjacent in \(G^{xyz}\) if and only if

1. \(\alpha, \beta \in V(G)\), \(\alpha\), \(\beta\) are adjacent in \(G\) if \(x = +\) and \(\alpha\) and \(\beta\) are not adjacent in \(G\) if \(x = -\).
2. \(\alpha, \beta \in E(G)\), \(\alpha\), \(\beta\) are adjacent in \(G\) if \(y = +\) and \(\alpha\) and \(\beta\) are not adjacent in \(G\) if \(y = -\).
3. \(\alpha \in V(G)\) and \(\beta \in E(G)\), \(\alpha\), \(\beta\) are incident in \(G\) if \(z = +\) and \(\alpha\) and \(\beta\) are not incident in \(G\) if \(z = -\).

Since there are eight distinct 3-permutations of \(\{+, -\}\), we obtain eight graphical transformations of \(G\). It is interesting to see that \(G^{+++}\) is exactly the total graph \(T(G)\) of \(G\) and \(G^{---}\) is the complement of \(T(G)\). Also for a given graph \(G\), \(G^{++-}\) and \(G^{--+}\), \(G^{+-+}\) and \(G^{-+-}\), \(G^{-++}\) and \(G^{+--}\) are the other three pairs of complementary graphs.

The basic properties of these total transformation can be seen in [12,16,17, 18].

In this paper, we obtained some new properties of Zagreb indices. We mainly give explicit formulae for the second Zagreb index of semitotal-point graph, semitotal-line graph and eight total transformation graphs.

2. Results

We begin with the following straightforward observations.

Observation 1. For a positive integer \(k\), we have \(\xi_{k}(G) = \sum_{v \in V(G)} (d_G(v))^{k}\). One can see that \(\xi_1(G)\) is just the number of edges in \(G\), and \(\xi_2(G)\) is the first Zagreb index \(M_1(G)\).

Observation 2. For any nonempty graph \(G\), we have $$ \sum_{uv \in E(G)} \big[d_G(u)^2 + d_G(v)^2 \big] = \sum_{w \in V(G)} d_G(w)^3 = \xi_3(G). $$

Theorem 1.[6] Let \(G\) be any nontrivial graph of order \(n\) and size \(m\). Then $$ \overline{M_2}(G) =2m^{2} - M_{2}(G) - \frac{1}{2}M_{1}(G) . $$

In the next theorem, the explicit formulas of first Zagreb index are given [19].

Theorem 2.[19] Let \(G\) be any nontrivial graph of order \(n\) and size \(m\). Then \begin{eqnarray*} M_1(T_1(G)) &=& M_1(G)+2M_2(G)+\xi_3(G) ,\\ M_1(T_2(G)) &=& 4(m + M_1(G)),\\ M_1(G^{+++}) &=& 4M_1(G)+ 2M_2(G) + \xi_3(G),\\ M_1(G^{---}) &=& (m+n)[(m+n)^2+6m -2n +1]+ 8m + 2(m+n-3)M_1(G)+ 2M_2(G) + \xi_3(G),\\ M_1(G^{++-}) &=& mn(m+n-8)+ 16m + 2(n-4)M_1(G) + 2M_2(G) + \xi_3(G), \\ M_1(G^{--+}) &=& n(n-1)^{2} +m(m+3)^{2}-2(m +3)M_1(G) + 2M_2(G) + \xi_3(G),\\ M_1(G^{+-+}) &=& m(m+3)^2 -2(m + 1)M_1(G) + 2M_2(G) + \xi_3(G). \end{eqnarray*} \begin{eqnarray*} M_1(G^{-+-}) &=& (m+n)[n(m+n) -2(n+4m)] + m[(n-4)^2+9]+ 2(n-2)M_1(G) + 2M_2(G) + \xi_3(G) ,\\ M_1(G^{-++}) &=& n(n-1)^2 + 2M_2(G) + \xi_3(G),\\ M_1(G^{+--}) &=& m[(nm +1) +(m+n)(m +n -2)]- 2(m+n-1)M_1(G) + 2M_2(G) + \xi_3(G). \end{eqnarray*}

In the following Lemma, the order and size of transformation graphs are given [19].

Lemma 1. [19] Let \(G\) be a nontrivial graph of order \(n\) and size \(m\). Then \begin{eqnarray*} |V(T_{1}(G))| &=& m+n , |E(T_1(G))| =m= \frac{1}{2}[2m + M_1(G)]. \\ |V(T_{2}(G))| &=& m+n , |E(T_2(G))| =3m.\\ |V(G^{+++})| &=& m +n, |E(G^{+++})| = m = \frac{1}{2}[4m + M_1(G)].\\ |V(G^{---})| &=& m +n, |E(G^{---})| = m =\frac{1}{2}[(m+n-1)(m+n)-4m- M_1(G)]. \\ |V(G^{++-})| &=& m +n, |E(G^{++-})| =m =\frac{1}{2}[2m(n-2)+ M_1(G)].\\ |V(G^{--+})| &=& m +n, |E(G^{--+})| =m =\frac{1}{2}[m(m+n) + n(n+1)- M_1(G)].\\ |V(G^{+-+})| &=& m +n, |E(G^{+-+})| =m =\frac{1}{2}[m(m+7) - M_1(G)].\\ |V(G^{-+-})| &=& m +n, |E(G^{-+-})| =m =\frac{1}{2}[n(m+n-1) + m(n-8) + M_1(G)].\\ |V(G^{-++})| &=& m +n, |E(G^{-++})| =m =\frac{1}{2}[n(n-1) + M_1(G)].\\ |V(G^{+--})| &=& m +n, |E(G^{+--})| =m =\frac{1}{2}[m(m +2n -1) - M_1(G)]. \end{eqnarray*}

In the next Lemma, the edge partition of transformation graphs in terms of \(E(G)\) and \(E(L(G))\) are given.

Lemma 2. Let \(G\) be a nontrivial graph of order \(n\) and size \(m\). Then

1. \(E(G^{+++}) = E(G) \cup E(L(G)) \cup 2E(G) ,\)
2. \(E(G^{---}) = E(\overline{G}) \cup E(\overline{L(G)}) \cup (n-2) \cdot E(G),\)
3. \(E(G^{++-}) = E(G) \cup E(L(G)) \cup (n-2) \cdot E(G) ,\)
4. \(E(G^{--+}) = E(\overline{G}) \cup E(\overline{L(G)}) \cup 2E(G) ,\)
5. \(E(G^{+-+}) = E(G)\cup E(\overline{L(G)}) \cup 2E(G) ,\)
6. \(E(G^{-+-}) = E(\overline{G}) \cup E(L(G)) \cup (n-2) \cdot E(G) ,\)
7. \(E(G^{-++}) = E(\overline{G}) \cup E(L(G)) \cup 2E(G) ,\)
8. \(E(G^{+--}) = E(G) \cup E(\overline{L(G)}) \cup (n-2) \cdot E(G) .\)

Theorem 3. Let \(G\) be a nontrivial graph of order \(n\) and size \(m\). Then \(M_2(T_1(G)) = 4 (4m + M_{1}(G))\).

Proof. Note that for \(u \in V(T_1(G)) \cap V(G) \), \(d_{_{T_1(G)}}(u) =2d_G(u)\) and for \(u \in V(T_1(G) \cap E(G)\), \(d_{_{T_1(G)}}(u) =2\). Therefore by Lemma 2, \begin{eqnarray*} M_2(T_1(G)) &=& \sum_{u \in V(T_1(G))} (2d(u))^2 + 2\sum_{u \in V(T_1(G)) \cap V(G)} 4d(u) = 4 (4m + M_{1}(G)). \end{eqnarray*} as desired.

Theorem 4. Let \(G\) be a nontrivial graph of order \(n\) and size \(m\). Then \(M_2(T_2(G)) = 2M_{1}(G) +4M_{2}(G) + \xi_{3}(G).\)

Proof. Suppose \(e =uv\) is a vertex in \(T_2(G)\). It can be easily seen that \(d_{T_2(G)}(e) = d_G(u) + d_G(v)\) and if \(u \in V(T_2(G)) \cap V(G)\), then \(d_{T_2(G)}(u) =d_G(u)\). Therefore by Lemma 2, \begin{eqnarray*} M_2(T_2(G)) &=& \sum_{_{u \in V(T_2(G)) \cap V(G)}} (d(u) + d(v))^2 + 2d(u)\sum_{_{u \in V(T_2(G) \cap E(G))}} (d(u) + d(v))= 2M_{1}(G) +4M_{2}(G) + \xi_{3}(G) . \end{eqnarray*} This completes the proof.

Theorem 5. Let \(G\) be a nontrivial graph of order \(n\) and size \(m\). Then \( M_2(G^{+++}) = 8M_1(G)+ 6M_2(G) + \xi_3(G) . \)

Proof. Note that \(E(G^{+++}) = E(G) \cup E(L(G) \cup 2E(G)\) and for \(u \in V(G^{+++}) \cap V(G)\), \(d_{G^{+++}}(u) = 2d_G(u)\) and for \(u \in V(G^{+++}) \cap E(G)\), \(d_{G^{+++}}(u) = d_G(u)+d_G(v)\). Therefore by Lemma 2, \begin{eqnarray*} M_2(G^{+++}) &=& \sum \limits_{u \in V(G^{+++}) \cap V(G)} 2d(u))^2 + \sum\limits_{u \in E(G^{+++}) \cap V(G)} (d(u)+d(v))^2 + 4d(u)\sum \limits_{u, v \in E(G) } (d(u)+d(v)) \\ &=& 4M_{1}(G) + 2M_{2}(G) + \xi_{3}(G) +4M_{1}(G) + 4M_{2}(G) \\ &=& 8M_1(G)+ 6M_2(G) + \xi_3(G). \end{eqnarray*} as asserted.

Theorem 6. Let \(G\) be a nontrivial graph of order \(n\) and size \(m\). Then \( M_2(G^{---}) = mn(m +n)^{2} -2m(m+n)(3n+4) +m(n +16)- 3(m+n-1)M_{1}(G)+ 2(n-1)M_{2}(G) +\xi_{3}(G). \)

Proof. Note that \(E(G^{---}) = E(\overline{G}) \cup E(\overline{L(G)}) \cup (n-2) \cdot E(G)\), and for \(u \in V(G^{---}) \cap V(G)\), \(d_{G^{---}}(u) = m + n -1 - 2d_G(u)\) and for \(u \in V(G^{---}) \cap E(G)\), \(d_{G^{---}}(u) = m + n -1 - (d_G(u) +d_G(v))\). Therefore by Lemma 2, \begin{eqnarray*} M_2(G^{---}) &=& \sum_{u \in V(G^{---}) \cap V(G)} (m + n -(1 + 2d_G(u)))^2 + \sum_{u \in V(G^{---})\cap E(G)} (m + n -(1 + (d_G(u) +d_G(v))))^2 \\ &&+ (n-2)(m + n -(1 + 2d_G(u)))\sum_{u ,v \in E(G)} (m + n -(1 + (d_G(u) +d_G(v)))) \\ &=& \big[m(m+n)^{2} +2m(m+n) +17m + 4M_{1}(G) \big] + \big[m(m+n)^{2} +2m(m+n) + m \\&&-2(m +n -1) M_{1}(G) +2M_{2}(G) + \xi_{3}(G) \big]+ (n-2) \big[m(m+n)^{2} -6m(m+n) +5m \\&&- (m +n +3) M_{1}(G) +2M_{2}(G) \big]. \end{eqnarray*} This completes the proof.

In fully analogous manner we arrive also at:

Theorem 7. Let \(G\) be a nontrivial graph of order \(n\) and size \(m\). Then \begin{eqnarray*} M_2(G^{++-}) &=& m^{3} +m(n-4) \big[ n(m+1) -2(m+2) \big] + \big[n(m+2) -2(m+4) \big] M_{1}(G)+ 2M_{2}(G) + \xi_{3}(G), \\ M_2(G^{--+}) &=& m(m+3)^{2} +m(n-1)[2m+n+5] -2(m+n+2) M_{1}(G)+ 2M_{2}(G) + \xi_{3}, \\ M_2(G^{+-+}) &=& m(m+3)(m +11)-2(m +3)M_{1}(G)- 2M_2(G) + \xi_3(G), \\ M_2(G^{-+-}) &=& m\big[(m +n)^{2} + (n-4)^{2} \big] +m(n-2)(n-4)(n-4m) - 10m(m+n)\\&&+ 9m \big[ (n-2)^{2} +mn -11 \big] M_{1}(G) + \xi_{3}(G), \\ M_2(G^{-++}) &=& m(n-1)^2 + 2(n-1)M_{1}(G)+ 2M_2(G) + \xi_3(G), \end{eqnarray*} \begin{eqnarray*} M_2(G^{+--}) &=& m(m^{2}+1) + m(m+n)(m +n -2) +m^{2}(n-2)(m +n+1)- (n(m +2)-2)M_{1}(G) \\&&+2M_{2}(G) + \xi_{3}(G). \end{eqnarray*}

Applying Theorem 1, from the results of Theorems 3-7 and Lemma 1, we can deduce expressions for the second Zagreb coindex of the transformation graphs and total transformation graphs \(G^{xyz}\). These are collected in the following:

Corollary 8. Let \(G\) be a graph of order \(n\) and size \(m.\) Then \begin{eqnarray*} \overline{M_{2}}(T_{1}(G)) &=& 2m^{2} -16m +(M_{1}(G))^{2} +4 (m-1)M_{1}(G) - \frac{1}{2} \big[M_{1}(G) +2M_{2}(G) + \xi_{3}(G) \big], \\ \overline{M_{2}}(T_{2}(G)) &=& 18m^{2} -2m -4M_{1}(G) -4M_{2}(G) - \xi_{3}(G),\\ \overline{M_{2}}(G^{+++}) &=& \frac{1}{2} \big[4m^{2} +(M_{1}(G))^{2} +4(2m-1)M_{1}(G) -2M_{2}(G) - \xi_{3}(G) \big]- 8M_{1}(G) -6M_{2}(G) - \xi_{3}(G),\\ \overline{M_{2}}(G^{---}) &=& \frac{1}{2} \big[(m+n-1)(m+n) -(4m+M_{1}(G)) \big]^{2}- mn(m +n)^{2} + 2m(m+n)(3n+4) -m(n +16) \\ &&+ 3(m+n-1)M_{1}(G)- 2(n-1)M_{2}(G) -\xi_{3}(G) - \frac{1}{2} \big[(m+n)[(m+n)^2+6m -2n +1]\\&&77+ 8m + 2(m+n-3)M_1(G)+ 2M_2(G) + \xi_3(G) \big],\\ \overline{M_{2}}(G^{++-}) &=& \frac{1}{2} \big[(2m(n-2)) +M_{1}(G)^{2} -mn(m+n-8) -16m - 2(n-4)M_{1}(G) -2M_{2}(G) - \xi_{3}(G)\big] \\&&- \big[ m^{3} +m(n-4) \big[ n(m+1) -2(m+2) \big] + \big[n(m+2) -2(m+4) \big] M_{1}(G) + 2M_{2}(G) + \xi_{3} \big], \\ \overline{M_{2}}(G^{--+}) &=& \frac{1}{2} \bigg[(m(m+n) +n(n+1) -M_{1}(G))^{2} - \big[ n(n-1)^{2} +m(m+3)^{2}-2(m +3)M_1(G) + 2M_2(G) \\&&+ \xi_3(G) \big] \bigg] -\big[ m(m+3)^{2} +m(n-1)[2m+n+5] -2(m+n+2) M_{1}(G) + 2M_{2}(G) + \xi_{3}\big], \\ \overline{M_{2}}(G^{+-+}) &=& \frac{1}{2} \bigg[[m(m+7) - M_1(G)]^{2} - \big[ m(m+3)^2 -2(m + 1)M_1(G) + 2M_2(G) + \xi_3(G) \big] \bigg]\\ &&- \big[ m(m+3)(m +11)-2(m +3)M_{1}(G)- 2M_2(G) + \xi_3(G\big],\\ \overline{M_{2}}(G^{-+-}) &=& \frac{1}{2} \bigg[[n(m+n-1) + m(n-8) + M_1(G)]^{2} - \big[(m+n)[n(m+n) -2(n+4m)]\\ &&- m[(n-4)^2+9] + 2(n-2)M_1(G) + 2M_2(G) + \xi_3(G) \big] \bigg] - \bigg[m\big[(m +n)^{2} + (n-4)^{2} \big] \\ &&-m(n-2)(n-4)(n-4m) - 10m(m+n) + 9m \big[ (n-2)^{2} +mn -11 \big] M_{1}(G) + \xi_{3}(G) \bigg], \end{eqnarray*} \begin{eqnarray*} \overline{M_{2}}(G^{-++}) &=& \frac{1}{2} \bigg[[n(n-1) + M_1(G)]^{2} - \big[n(n-1)^2 + 2M_2(G) + \xi_3(G) \big] \bigg] - \bigg[m(n-1)^2 \\ &&+ 2(n-1)M_{1}(G)+ 2M_2(G) + \xi_3(G) \bigg],\\ \overline{M_{2}}(G^{+--}) &=& \frac{1}{2} \bigg[[m(m +2n -1) - M_1(G)]^{2} - \big[m[(nm +1) +(m+n)(m +n -2)] \\ &&- 2(m+n-1)M_1(G) + 2M_2(G) + \xi_3(G) \big] \bigg] -\bigg[m(m^{2}+1) + m(m+n)(m +n -2) \\ &&- m^{2}(n-2)(m +n+1) - (n(m +2)-2)M_{1}(G) +2M_{2}(G) + \xi_{3}(G). \bigg].\end{eqnarray*}

Proof. The proof follows from the Theorems 1 and 3-7.

Author Contributions

All authors contributed equally to the writing of this paper. All authors read and approved the final manuscript.

Conflicts of Interest:

The authors declare no conflict of interest.