Reformulated Zagreb Indices of Some Derived Graphs

Abstract

A topological index is a numeric quantity that is closely related to the chemical constitution to establish the correlation of its chemical structure with chemical reactivity or physical properties. Miličević reformulated the original Zagreb indices in 2004, replacing vertex degrees by edge degrees. In this paper, we established the expressions for the reformulated Zagreb indices of some derived graphs such as a complement, line graph, subdivision graph, edge-semitotal graph, vertex-semitotal graph, total graph, and paraline graph of a graph.

1. Introduction

In the fields of mathematical chemistry and chemical graph theory, a topological index is a numerical parameter that is measured based on the molecular graph of a chemical constitution. Topological indices are extensively used in the study of quantitative structure-activity relationships (QSARs) to establish the correlation between different properties of molecules and/or the biological activity with their structure. Topological indices have also been applied in spectral graph theory to measure the resilience and robustness of complex networks [1].

Suppose that $\Omega$ denotes the set of all graphs. Then, a function $T:\Omega \to {\mathbb{R}}^{+}$ is called a topological index if for any pair of isomorphic graphs G and H, we have $T\left(G\right)=T\left(H\right)$. There are many topological indices that are useful in chemistry, biochemistry, and nanotechnology.

Throughout this paper, we are concerned only with the simple and connected graphs. Let $G=(V,E)$ be such a graph. We use the notations $V=V\left(G\right)$ and $E=E\left(G\right)$ for the vertex set and edge set of G, respectively. We use the notation $d_G\left(i\right)$ for the degree of a vertex i in G. The hand shaking lemma says that the sum of the degrees of all the vertices is equal to double the number of edges. Mathematically,

$\begin{array}{c}\hfill \sum _{i\in V\left(G\right)}{d}_G\left(i\right)=2\left|E\left(G\right)\right|\end{array}$

For basic definitions and notations, see the book [2].

The first and second Zagreb indices are defined as:

$\begin{array}{ccc}\hfill M_1& =& M_1\left(G\right)=\sum _{i\in V\left(G\right)}{d}_G{\left(i\right)}^2\hfill \\ \hfill M_2& =& M_2\left(G\right)=\sum _{ij\in E\left(G\right)}{d}_G\left(i\right)d_G\left(j\right).\hfill \end{array}$

Another expression for the first Zagreb index is:

$\begin{array}{c}\hfill M_1=M_1\left(G\right)=\sum _{ij\in E\left(G\right)}[d_G\left(i\right)+d_G\left(j\right)].\end{array}$

These two Zagreb indices defined by Gutman and Trinajstic in 1972 [3] are among the oldest topological indices, having many applications in mathematical chemistry. Zagreb indices are known to be very useful in quantitative structure-property relationships (QSPR) and QSAR [4,5,6]. In [7] and [8], the authors have derived the expressions for Zagreb indices of some derived graphs.

Zagreb indices were reformulated by Miličević [9] as:

$\begin{array}{ccc}\hfill E{M}_1& =& E{M}_1\left(G\right)=\sum _{e\in E\left(G\right)}{d}_G{\left(e\right)}^2,\hfill \\ \hfill E{M}_2& =& E{M}_2\left(G\right)=\sum _{e\sim f\in E\left(G\right)}{d}_G\left(e\right)d_G\left(f\right),\hfill \end{array}$

where $d_G\left(e\right)$ denotes the degree of an edge $e=ij$ in G and defined as the total number of edges incident with e. Mathematically, $d_G\left(e\right)=d_G\left(i\right)+d_G\left(j\right)-2$. Here, $e\sim f$ indicates that the edges e and f are incident. Another expression for the first reformulated Zagreb index is:

$\begin{array}{c}\hfill E{M}_1=E{M}_1\left(G\right)=\sum _{e\sim f\in E\left(G\right)}[d_G\left(e\right)+d_G\left(f\right)].\end{array}$

The first reformulated Zagreb index is closely related to Laplacian eigenvalues [10]. Much interest has been shown by researches and scientists in the reformulated Zagreb indices [11,12,13,14,15].

Another vertex-degree-based topological index was found to be useful in the earliest work on Zagreb indices [3,16], but later was totally ignored. Quite recently, some interest has been shown in it [17,18]. It is called the forgotten index or simply the F-index and is defined as:

$\begin{array}{ccc}\hfill F=F\left(G\right)& =& \sum _{i\in V\left(G\right)}{d}_G{\left(i\right)}^3\hfill \\ & =& \sum _{ij\in E\left(G\right)}[d_G{\left(i\right)}^2+d_G{\left(j\right)}^2].\hfill \end{array}$

In general, for any real number “$\alpha$”, the generalized version of first Zagreb index is defined as:

$\begin{array}{ccc}\hfill {}^{\alpha }{M}_1={}^{\alpha }{M}_1\left(G\right)& =& \sum _{i\in V\left(G\right)}{d}_G{\left(i\right)}^{\alpha }\hfill \\ & =& \sum _{ij\in E\left(G\right)}[d_G{\left(i\right)}^{\alpha -1}+d_G{\left(j\right)}^{\alpha -1}].\hfill \end{array}$

Clearly, the first Zagreb index and F-index are special cases of ${}^{\alpha }{M}_1$ for $\alpha =2$ and $\alpha =3$, respectively.

Bearing in mind the reformulation of Zagreb indices, here we reformulate the F-index as:

$\begin{array}{ccc}\hfill EF=EF\left(G\right)& =& \sum _{e\in E\left(G\right)}{d}_G{\left(e\right)}^3\hfill \\ & =& \sum _{e\sim f\in E\left(G\right)}[d_G{\left(e\right)}^2+d_G{\left(f\right)}^2].\hfill \end{array}$

We prefer to call it the reformulated forgotten index or simply the reformulated F-index.

Some Derived Graphs

Let, as before, G be a simple and connected graph with vertex set $V\left(G\right)$ and edge set $E\left(G\right)$. Let $\left|V\right(G\left)\right|=n$ and $\left|E\right(G\left)\right|=m$. Now, we consider the following graphs derived from G:

• Complement: The complement $\overline{G}$ of G is the graph with the same set of vertices as G, but there is an edge between two vertices of $\overline{G}$ if and only if there is no edge between these vertices in G. Clearly, $\left|V\right(\overline{G}\left)\right|=n$ and $\overline{m}=\left|E\left(\overline{G}\right)\right|=\frac{n(n-1)}{2}-m$.

• Line graph: The line graph $L=L\left(G\right)$ of G is the graph in which the vertex set is the edge set of G, and there is an edge between two vertices of L if and only if their corresponding edges are incident in G. Thus, $\left|V\right(L\left)\right|=m$, and by hand shaking lemma,

  $\begin{array}{ccc}\hfill \left|E\right(L\left)\right|& =& \frac{1}{2}\sum _{i\in V\left(L\right)}{d}_L\left(i\right)=\frac{1}{2}\sum _{e\in E\left(G\right)}{d}_G\left(e\right)\hfill \\ & =& \frac{1}{2}\sum _{ij\in E\left(G\right)}[d_G\left(i\right)+d_G\left(j\right)-2]\hfill \\ & =& \frac{1}{2}(M_1-2m)=\frac{M_1}{2}-m.\hfill \end{array}$

• Subdivision graph: A subdivision graph of a graph G can be constructed by inserting a vertex on each edge of G, which will change that edge into a path of length two. This graph is denoted as $S=S\left(G\right)$.

  So, $\left|V\right(S\left)\right|=\left|V\right(G\left)\right|+\left|E\right(G\left)\right|=n+m$ and $\left|E\right(S\left)\right|=2\left|E\right(G\left)\right|=2m$.

• Vertex-semitotal graph: A vertex-semitotal graph $T_1=T_1\left(G\right)$ is constructed from G by inserting a new vertex on each edge of G and then by joining every newly-inserted vertex to the end vertices of the corresponding edge. Thus, $|V\left(T_1\right)|=|V\left(G\right)|+|E\left(G\right)|=n+m$ and $|E\left(T_1\right)|=|E\left(S\right)|+|E\left(G\right)|=2m+m=3m$.

• Edge-semitotal graph: An edge-semitotal graph $T_2=T_2\left(G\right)$ is made by putting a new vertex in each edge of G and then joining with edges those new vertices whose corresponding edges are incident in G. Thus, $|V\left(T_2\right)|=|V\left(G\right)|+|E\left(G\right)|=n+m$ and $|E\left(T_2\right)|=|E\left(S\right)|+|E\left(L\right)|=2m+\frac{M_1}{2}-m=m+\frac{M_1}{2}$.

• Total graph: The total graph $T=T\left(G\right)$ is the union of the vertex-semitotal graph and the edge-semitotal graph. Thus, $\left|V\right(T\left)\right|=\left|V\right(G\left)\right|+\left|E\right(G\left)\right|=n+m$ and $\left|E\left(T\right)\right|=\left|E\left(G\right)\right|+\left|E\left(S\right)\right|+\left|E\left(L\right)\right|=m+2m+\frac{M_1}{2}-m=2m+\frac{M_1}{2}$.

• Paraline graph: The paraline graph $PL=PL\left(G\right)$ is the line graph of the subdivision graph denoted by $PL=PL\left(G\right)=L\left(S\right(G\left)\right)$. Furthermore, $\left|V\right(PL\left)\right|=\left|E\right(S\left)\right|=2m$ and:

  $\begin{array}{c}\hfill \left|E\left(PL\right)\right|=\frac{M_1\left(S\right)}{2}-2m.\end{array}$

In [7], one can easily see that $M_1\left(S\right)=M_1+4m$. Thus:

$\begin{array}{c}\hfill \left|E\left(PL\right)\right|=\frac{M_1+4m}{2}-2m=\frac{M_1}{2}.\end{array}$

In Figure 1, self-explanatory examples of these derived graphs are given for a particular graph. In every derived graph of G (except the paraline graph $PL\left(G\right)$), the vertices corresponding to the vertices of G are denoted by circles and the vertices corresponding to the edges of G are denoted by squares.

The following are some known results on Zagreb indices.

Lemma 1.

[7] If $\overline{G}$ is the complement of G, then:

$\begin{array}{c}\hfill M_1\left(\overline{G}\right)=M_1+n{(n-1)}^2-4m(n-1).\end{array}$

Lemma 2.

[7] If $\overline{G}$ is the complement of G, then:

$\begin{array}{c}\hfill M_2\left(\overline{G}\right)=\frac{2n-3}{2}{M}_1-M_2+\frac{1}{2}n{(n-1)}^3-3m{(n-1)}^2+2m^2.\end{array}$

Lemma 3.

[17] If $\overline{G}$ is the complement of G, then:

$\begin{array}{c}\hfill F\left(\overline{G}\right)=3(n-1)M_1-F+n{(n-1)}^3-6m{(n-1)}^2.\end{array}$

Lemma 4.

[15] The reformulated first Zagreb index can be written in terms of the Zagreb indices and F-index as:

$\begin{array}{c}\hfill E{M}_1=F-4M_1+2M_2+4m.\end{array}$

2. Reformulated First Zagreb Index of Some Derived Graphs

In [7] and [8], the authors derived the expressions for Zagreb indices and coindices of those derived graphs, which have been discussed above. In [19], the authors derived the expressions for multiplicative Zagreb indices and coindices of some derived graphs. In this section, we present the expressions for the reformulated first Zagreb index of these derived graphs.

Theorem 1.

If $\overline{G}$ is the complement of G, then:

$\begin{array}{ccc}\hfill E{M}_1\left(\overline{G}\right)& =& 5(n-2)M_1-2M_2-F+2n(n-1){(n-2)}^2\hfill \\ & & -4m(n-2)(3n-4)+4m^2.\hfill \end{array}$

Proof. 

By the definition of the first reformulated Zagreb index,

$\begin{array}{ccc}\hfill E{M}_1\left(\overline{G}\right)& =& \sum _{e\in E\left(\overline{G}\right)}{d}_{\overline{G}}{\left(e\right)}^2\hfill \\ & =& \sum _{ij\in E\left(\overline{G}\right)}{[d_{\overline{G}}\left(i\right)+d_{\overline{G}}\left(j\right)-2]}^2\hfill \\ & =& \sum _{ij\in E\left(\overline{G}\right)}[d_{\overline{G}}{\left(i\right)}^2+d_{\overline{G}}{\left(j\right)}^2]+4\sum _{ij\in E\left(\overline{G}\right)}1+2\sum _{ij\in E\left(\overline{G}\right)}{d}_{\overline{G}}\left(i\right)d_{\overline{G}}\left(j\right)\hfill \\ & & -4\sum _{ij\in E\left(\overline{G}\right)}[d_{\overline{G}}\left(i\right)+d_{\overline{G}}\left(j\right)]\hfill \\ & =& F\left(\overline{G}\right)+4\left|E\left(\overline{G}\right)\right|+2M_2\left(\overline{G}\right)-4M_1\left(\overline{G}\right)\hfill \end{array}$

Using Lemma 1, Lemma 2, and Lemma 3 for fourth, third, and first term, respectively, we have:

$\begin{array}{ccc}\hfill E{M}_1\left(\overline{G}\right)& =& 3(n-1)M_1-F+n{(n-1)}^3-6m{(n-1)}^2+2n(n-1)-4m\hfill \\ & & +(2n-3)M_1-2M_2+n{(n-1)}^3-6m{(n-1)}^2+4m^2\hfill \\ & & -4M_1-4n{(n-1)}^2+16m(n-1)\hfill \\ & =& 5(n-2)M_1-2M_2-F+2n{(n-1)}^3-4n{(n-1)}^2+2n(n-1)\hfill \\ & & -12m{(n-1)}^2-4m+16m(n-1)+4m^2\hfill \\ & =& 5(n-2)M_1-2M_2-F+2n(n-1){(n-2)}^2-4m(n-2)(3n-4)+4m^2.\hfill \end{array}$

 □

Theorem 2.

If $L=L\left(G\right)$ is the line graph of G, then:

$\begin{array}{c}\hfill E{M}_1\left(L\right)=EF+2E{M}_2-4F+18M_1-8M_2-20m.\end{array}$

Proof. 

By the definition of the reformulated first Zagreb index,

$\begin{array}{ccc}\hfill E{M}_1\left(L\right)& =& \sum _{e\in E\left(L\right)}{d}_L{\left(e\right)}^2\hfill \\ & =& \sum _{ij\in E\left(L\right)}{[d_L\left(i\right)+d_L\left(j\right)-2]}^2\hfill \\ & =& \sum _{ij\in E\left(L\right)}[d_L{\left(i\right)}^2+d_L{\left(j\right)}^2]+4\sum _{ij\in E\left(L\right)}1+2\sum _{ij\in E\left(L\right)}{d}_L\left(i\right)d_L\left(j\right)\hfill \\ & & -4\sum _{ij\in E\left(L\right)}[d_L\left(i\right)+d_L\left(j\right)]\hfill \\ & =& F\left(L\right)+4\left|E\left(L\right)\right|+2M_2\left(L\right)-4M_1\left(L\right).\hfill \end{array}$

Now, by the definition of the line graph, it is clear that:

$\begin{array}{c}\hfill F\left(L\right)=EF,M_1\left(L\right)=E{M}_1,M_2\left(L\right)=E{M}_2.\end{array}$

Thus:

$\begin{array}{c}\hfill E{M}_1\left(L\right)=EF+4(\frac{M_1}{2}-m)+2E{M}_2-4E{M}_1.\end{array}$

Using Lemma 4 for term $E{M}_1$,

$\begin{array}{c}\hfill E{M}_1\left(L\right)=EF+2E{M}_2-4F+18M_1-8M_2-20m.\end{array}$

 □

Now, for subdivision graph S, vertex-semitotal graph $T_1$, edge-semitotal graph $T_2$, and total graph T, we can see that there are two types of vertices in these graphs: first, the vertices corresponding to the vertices of G and, second, the vertices corresponding to the edges of G. We call them $\alpha$-vertices and $\beta$-vertices, respectively. Depending on the nature of end vertices, we can divide the edges of these graphs into three types:

• $\alpha \alpha$-edge: an edge between two $\alpha$-vertices.

• $\beta \beta$-edge: an edge between two $\beta$-vertices.

• $\alpha \beta$-edge: an edge between a $\alpha$-vertex and a $\beta$-vertex.

The above idea is very similar to the idea used in [20].

Theorem 3.

If $S=S\left(G\right)$ is a subdivision graph of G, then:

$\begin{array}{c}\hfill E{M}_1\left(S\right)=F.\end{array}$

Proof. 

We can see that for any $\alpha$-vertex $i_{\alpha }$ of S:

$\begin{array}{c}\hfill d_S\left(i_{\alpha }\right)=d_G\left(i_{\alpha }\right)\end{array}$

and for any $\beta$-vertex $j_{\beta }$ of S:

$\begin{array}{c}\hfill d_S\left(j_{\beta }\right)=2.\end{array}$

Furthermore, all the edges of S are $\alpha \beta$-edges. Thus:

$\begin{array}{ccc}\hfill E{M}_1\left(S\right)& =& \sum _{e_{\alpha \beta }\in E\left(S\right)}{d}_S{\left(e_{\alpha \beta }\right)}^2\hfill \\ & =& \sum _{i_{\alpha }{j}_{\beta }\in E\left(S\right)}{[d_S\left(i_{\alpha }\right)+d_S\left(j_{\beta }\right)-2]}^2.\hfill \end{array}$

In fact, every $\alpha$-vertex $i_{\alpha }$ of S is connected with $d_G\left(i_{\alpha }\right)$$\beta$-vertices, each of degree two. Hence:

$\begin{array}{c}\hfill E{M}_1\left(S\right)=\sum _{i_{\alpha }\in V\left(G\right)}{d}_G\left(i_{\alpha }\right){[d_G\left(i_{\alpha }\right)+2-2]}^2=F.\end{array}$

 □

Theorem 4.

If $T_1=T_1\left(G\right)$ is a vertex-semitotal graph of G, then:

$\begin{array}{c}\hfill E{M}_1\left(T_1\right)=8(F-M_1+M_2)+4m.\end{array}$

Proof. 

First note that for any $\alpha$-vertex $i_{\alpha }$ of $T_1$:

$\begin{array}{c}\hfill d_{T_1}\left(i_{\alpha }\right)=2d_G\left(i_{\alpha }\right)\end{array}$

and for any $\beta$-vertex $j_{\beta }$ of $T_1$:

$\begin{array}{c}\hfill d_{T_1}\left(j_{\beta }\right)=2.\end{array}$

Furthermore, any edge of $T_1$ is either an $\alpha \alpha$-edge or an $\alpha \beta$-edge. Thus:

$\begin{array}{ccc}\hfill E{M}_1\left(T_1\right)& =& \sum _{e\in E\left(T_1\right)}{d}_{T_1}{\left(e\right)}^2\hfill \\ & =& \sum _{e_{\alpha \alpha }\in E\left(T_1\right)}{d}_{T_1}{\left(e_{\alpha \alpha }\right)}^2+\sum _{e_{\alpha \beta }\in E\left(T_1\right)}{d}_{T_1}{\left(e_{\alpha \beta }\right)}^2\hfill \\ & =& \sum _{i_{\alpha }{j}_{\alpha }\in E\left(T_1\right)}{[d_{T_1}\left(i_{\alpha }\right)+d_{T_1}\left(j_{\alpha }\right)-2]}^2+\sum _{i_{\alpha }{j}_{\beta }\in E\left(T_1\right)}{[d_{T_1}\left(i_{\alpha }\right)+d_{T_1}\left(j_{\beta }\right)-2]}^2.\hfill \end{array}$

For $\alpha \beta$-edges in the second term, it is clear that every $\alpha$-vertex $i_{\alpha }$ of $T_1$ is connected with $d_G\left(i_{\alpha }\right)$$\beta$-vertices, each of degree two. Therefore, corresponding to every vertex $i_{\alpha }$ in G, there are $d_G\left(i_{\alpha }\right)$ edges in $T_1$ each of (edge) degree $[2d_G\left(i_{\alpha }\right)+2-2]$. Thus:

$\begin{array}{ccc}\hfill E{M}_1\left(T_1\right)& =& \sum _{i_{\alpha }{j}_{\alpha }\in E\left(G\right)}{[2d_G\left(i_{\alpha }\right)+2d_G\left(j_{\alpha }\right)-2]}^2+\sum _{i_{\alpha }\in V\left(G\right)}{d}_G\left(i_{\alpha }\right){[2d_G\left(i_{\alpha }\right)+2-2]}^2\hfill \\ & =& 4\sum _{i_{\alpha }{j}_{\alpha }\in E\left(G\right)}[d_G{\left(i_{\alpha }\right)}^2+d_G{\left(j_{\alpha }\right)}^2]+4\sum _{i_{\alpha }{j}_{\alpha }\in E\left(G\right)}1+8\sum _{i_{\alpha }{j}_{\alpha }\in E\left(G\right)}{d}_G\left(i_{\alpha }\right)d_G\left(j_{\alpha }\right)\hfill \\ & & -8\sum _{i_{\alpha }{j}_{\alpha }\in E\left(G\right)}[d_G\left(i_{\alpha }\right)+d_G\left(j_{\alpha }\right)]+4\sum _{i_{\alpha }\in V\left(G\right)}{d}_G{\left(i_{\alpha }\right)}^3\hfill \\ & =& 8(F-M_1+M_2)+4m.\hfill \end{array}$

 □

Theorem 5.

If $T_2=T_2\left(G\right)$ is an edge-semitotal graph of G, then:

$\begin{array}{c}\hfill E{M}_1\left(T_2\right)=EF+2E{M}_2+9F-26M_1+16M_2+20m.\end{array}$

Proof. 

First note that for any $\alpha$-vertex $i_{\alpha }$ of $T_2$:

$\begin{array}{c}\hfill d_{T_2}\left(i_{\alpha }\right)=d_G\left(i_{\alpha }\right)\end{array}$

and for any $\beta$-vertex $j_{\beta }$ of $T_2$

$\begin{array}{c}\hfill d_{T_2}\left(j_{\beta }\right)=d_L\left(j_{\beta }\right)+2.\end{array}$

Any edge in $T_2$ is either an $\alpha \beta$-edge or a $\beta \beta$-edge. In fact,

• Corresponding to every edge $i_{\alpha }{j}_{\alpha }$ in G, there are two $\alpha \beta$-edges $i_{\alpha }{x}_{\beta }$ and $x_{\beta }{j}_{\alpha }$ in $T_2$ such that:

  $\begin{array}{ccc}\hfill d_{T_2}\left(i_{\alpha }\right)& =& d_G\left(i_{\alpha }\right)\hfill \\ \hfill d_{T_2}\left(j_{\alpha }\right)& =& d_G\left(j_{\alpha }\right)\hfill \end{array}$

  and:

  $\begin{array}{ccc}\hfill d_{T_2}\left(x_{\beta }\right)& =& d_L\left(x_{\beta }\right)+2=d_G\left(i_{\alpha }\right)+d_G\left(j_{\alpha }\right)-2+2\hfill \\ & =& d_G\left(i_{\alpha }\right)+d_G\left(j_{\alpha }\right).\hfill \end{array}$

• $\beta \beta$-edges are the edges corresponding to the edges of $L\left(G\right)$.

Thus:

$\begin{array}{ccc}\hfill E{M}_1\left(T_2\right)& =& \sum _{e\in E\left(T_2\right)}{d}_{T_2}{\left(e\right)}^2\hfill \\ & =& \sum _{e_{\alpha \beta }\in E\left(T_2\right)}{d}_{T_2}{\left(e_{\alpha \beta }\right)}^2+\sum _{e_{\beta \beta }\in E\left(T_2\right)}{d}_{T_2}{\left(e_{\beta \beta }\right)}^2\hfill \\ & =& \sum _{i_{\alpha }{j}_{\alpha }\in E\left(G\right)}[{(d_{T_2}\left(i_{\alpha }\right)+d_{T_2}\left(x_{\beta }\right)-2)}^2+{(d_{T_2}\left(x_{\beta }\right)+d_{T_2}\left(j_{\alpha }\right)-2)}^2]\hfill \\ & & +\sum _{i_{\beta }{j}_{\beta }\in E\left(L\right)}{(d_{T_2}\left(i_{\beta }\right)+d_{T_2}\left(j_{\beta }\right)-2)}^2\hfill \\ & =& \sum _{i_{\alpha }{j}_{\alpha }\in E\left(G\right)}[{(2d_G\left(i_{\alpha }\right)+d_G\left(j_{\alpha }\right)-2)}^2+{(d_G\left(i_{\alpha }\right)+2d_G\left(j_{\alpha }\right)-2)}^2]\hfill \\ & & +\sum _{i_{\beta }{j}_{\beta }\in E\left(L\right)}{(d_L\left(i_{\beta }\right)+d_L\left(j_{\beta }\right)+2)}^2\hfill \\ & =& 5F+8m+8M_2-12M_1+F\left(L\right)+4\left|E\left(L\right)\right|+2M_2\left(L\right)+4M_1\left(L\right).\hfill \end{array}$

Now, by the definition of the line graph, it is clear that:

$\begin{array}{c}\hfill F\left(L\right)=EF,M_1\left(L\right)=E{M}_1,M_2\left(L\right)=E{M}_2.\end{array}$

Thus:

$\begin{array}{c}\hfill E{M}_1\left(T_2\right)=5F+8m+8M_2-12M_1+EF+4(\frac{M_1}{2}-m)+2E{M}_2+4E{M}_1.\end{array}$

Using Lemma 4,

$\begin{array}{c}\hfill E{M}_1\left(T_2\right)=EF+2E{M}_2+9F-26M_1+16M_2+20m.\end{array}$

 □

Theorem 6.

If $T=T\left(G\right)$ is the total graph of G, then:

$\begin{array}{c}\hfill E{M}_1\left(T\right)=EF+2E{M}_2+18F-38M_1+28M_2+24m.\end{array}$

Proof. 

First note that for any $\alpha$-vertex $i_{\alpha }$ of T:

$\begin{array}{c}\hfill d_T\left(i_{\alpha }\right)=2d_G\left(i_{\alpha }\right)\end{array}$

and for any $\beta$-vertex $j_{\beta }$ of T:

$\begin{array}{c}\hfill d_T\left(j_{\beta }\right)=d_L\left(j_{\beta }\right)+2.\end{array}$

T has all three types of edges. In fact,

• Corresponding to every edge $i_{\alpha }{j}_{\alpha }$ in G, there is one $\alpha \alpha$-edge, which is $i_{\alpha }{j}_{\alpha }$, and two $\alpha \beta$-edges, which are $i_{\alpha }{x}_{\beta }$ and $x_{\beta }{j}_{\alpha }$ in T such that:

  $\begin{array}{ccc}\hfill d_T\left(i_{\alpha }\right)& =& 2d_G\left(i_{\alpha }\right)\hfill \\ \hfill d_T\left(j_{\alpha }\right)& =& 2d_G\left(j_{\alpha }\right)\hfill \end{array}$

  and:

  $\begin{array}{ccc}\hfill d_T\left(x_{\beta }\right)& =& d_L\left(x_{\beta }\right)+2=d_G\left(i_{\alpha }\right)+d_G\left(j_{\alpha }\right)-2+2\hfill \\ & =& d_G\left(i_{\alpha }\right)+d_G\left(j_{\alpha }\right).\hfill \end{array}$

• $\beta \beta$-edges are the edges corresponding to the edges of $L\left(G\right)$.

Thus:

$\begin{array}{ccc}\hfill E{M}_1\left(T\right)& =& \sum _{e\in E\left(T\right)}{d}_T{\left(e\right)}^2\hfill \\ & =& \sum _{e_{\alpha \alpha }\in E\left(T\right)}{d}_T{\left(e_{\alpha \alpha }\right)}^2+\sum _{e_{\beta \beta }\in E\left(T\right)}{d}_T{\left(e_{\beta \beta }\right)}^2+\sum _{e_{\alpha \beta }\in E\left(T\right)}{d}_T{\left(e_{\alpha \beta }\right)}^2\hfill \\ & =& \sum _{i_{\alpha }{j}_{\alpha }\in E\left(G\right)}{(d_T\left(i_{\alpha }\right)+d_T\left(j_{\alpha }\right)-2)}^2+\sum _{i_{\beta }{j}_{\beta }\in E\left(L\right)}{(d_T\left(i_{\beta }\right)+d_T\left(j_{\beta }\right)-2)}^2\hfill \\ & & +\sum _{i_{\alpha }{j}_{\alpha }\in E\left(G\right)}[{(d_T\left(i_{\alpha }\right)+d_T\left(x_{\beta }\right)-2)}^2+{(d_T\left(x_{\beta }\right)+d_T\left(j_{\alpha }\right)-2)}^2]\hfill \\ & =& 4\sum _{i_{\alpha }{j}_{\alpha }\in E\left(G\right)}{(d_G\left(i_{\alpha }\right)+d_G\left(j_{\alpha }\right)-1)}^2+\sum _{i_{\beta }{j}_{\beta }\in E\left(L\right)}{(d_L\left(i_{\beta }\right)+d_L\left(j_{\beta }\right)+2)}^2\hfill \\ & & +\sum _{i_{\alpha }{j}_{\alpha }\in E\left(G\right)}[{(3d_G\left(i_{\alpha }\right)+d_G\left(j_{\alpha }\right)-2)}^2+{(d_G\left(i_{\alpha }\right)+3d_G\left(j_{\alpha }\right)-2)}^2]\hfill \\ & =& 14F-24M_1+20M_2+12m+F\left(L\right)+4\left|E\left(L\right)\right|+2M_2\left(L\right)+4M_1\left(L\right).\hfill \end{array}$

Now, using the facts:

$\begin{array}{c}\hfill F\left(L\right)=EF,M_1\left(L\right)=E{M}_1,M_2\left(L\right)=E{M}_2,\end{array}$

and then using Lemma 4, we get:

$\begin{array}{c}\hfill E{M}_1\left(T\right)=EF+2E{M}_2+18F-38M_1+28M_2+24m.\end{array}$

 □

Theorem 7.

If $PL=PL\left(G\right)$ is a paraline graph of G, then:

$\begin{array}{c}\hfill E{M}_1\left(PL\right)=2{(}^4{M}_1+M_1+M_2)-5F.\end{array}$

Proof. 

It can be noted that for any vertex $i\in V\left(G\right)$, there are $d_G\left(i\right)$ vertices in $PL\left(G\right)$ having the same degree as i such that all these $d_G\left(i\right)$ vertices are connected with each other. In fact, $PL\left(G\right)$ can be obtained from G by replacing every vertex i by $K_{d_G\left(i\right)}$. Now, the edges of $PL\left(G\right)$ can be divided into two categories:

• The edges in $K_{d_G\left(i\right)}$, where $i\in V\left(G\right)$.

• Edges corresponding to edges of G. It can be seen that corresponding to every edge in G, there is an edge in $PL\left(G\right)$ of the same degree.

Thus:

$\begin{array}{ccc}\hfill E{M}_1\left(PL\right)& =& \sum _{e\in E\left(PL\right)}{d}_{PL}{\left(e\right)}^2\hfill \\ & =& \sum _{e\in E\left(K_{d_G\left(i\right)}\right),i\in V\left(G\right)}{d}_{PL}{\left(e\right)}^2+\sum _{e\in E\left(G\right)}{d}_G{\left(e\right)}^2.\hfill \end{array}$

Now, in each $K_{d_G\left(i\right)}$, there are $\frac{d_G\left(i\right)(d_G\left(i\right)-1)}{2}$ edges, each of degree $d_G\left(i\right)+d_G\left(i\right)-2=2d_G\left(i\right)-2$. Thus:

$\begin{array}{ccc}\hfill E{M}_1\left(PL\right)& =& \sum _{i\in V\left(G\right)}\frac{d_G\left(i\right)(d_G\left(i\right)-1)}{2}{(2d_G\left(i\right)-2)}^2+E{M}_1.\hfill \end{array}$

Solving the first term and using Lemma 4 in the second term, we get:

$\begin{array}{ccc}\hfill E{M}_1\left(PL\right)& =& 2{(}^4{M}_1-3F+3M_1-2m)+F-4M_1+2M_2+4m\hfill \\ & =& 2{(}^4{M}_1+M_1+M_2)-5F.\hfill \end{array}$

 □

3. Reformulated Second Zagreb Index of Some Derived Graphs

In this section, we derive the expressions for the reformulated second Zagreb index of some derived graphs.

Theorem 8.

If $S=S\left(G\right)$ is a subdivision graph of G, then:

$\begin{array}{c}\hfill E{M}_2\left(S\right)=\frac{1}{2}{(}^4{M}_1-F)+M_2.\end{array}$

Proof. 

We can divide the pairs of incident edges of $S=S\left(G\right)$ into two categories:

• For any vertex $i\in V\left(G\right)$, there are $d_G\left(i\right)$ edges, each of degree $d_G\left(i\right)$ in S, and all these edges are incident at i. Therefore, for any vertex $i\in V\left(G\right)$, the total number of pairs of incident edges lying in this category is $\frac{d_G\left(i\right)(d_G\left(i\right)-1)}{2}$.

• Corresponding to every pair of adjacent vertices i and j in G, there is a pair of incident edges of degrees $d_G\left(i\right)$ and $d_G\left(j\right)$ in S.

Thus:

$\begin{array}{ccc}\hfill E{M}_2\left(S\right)& =& \sum _{e\sim f\in E\left(S\right)}{d}_S\left(e\right)d_S\left(f\right)\hfill \\ & =& \sum _{i\in V\left(G\right)}\frac{d_G\left(i\right)(d_G\left(i\right)-1)}{2}{d}_G\left(i\right)d_G\left(i\right)+\sum _{ij\in E\left(G\right)}{d}_G\left(i\right)d_G\left(j\right)\hfill \\ & =& \frac{1}{2}{(}^4{M}_1-F)+M_2.\hfill \end{array}$

 □

Before going to the next theorem, we prove another lemma here.

Lemma 5.

For a graph G, the following equality holds.

$\begin{array}{c}\hfill \sum _{ij\in E\left(G\right)}{d}_G\left(i\right)d_G\left(j\right)[d_G\left(i\right)+d_G\left(j\right)]=\frac{1}{3}(EF-{}^4{M}_1+8m)+2F+4(M_2-M_1).\end{array}$

Proof. 

$\begin{array}{ccc}\hfill \sum _{ij\in E\left(G\right)}{d}_G\left(i\right)d_G\left(j\right)[d_G\left(i\right)+d_G\left(j\right)]& =& \frac{1}{3}\sum _{ij\in E\left(G\right)}{[d_G\left(i\right)+d_G\left(j\right)]}^3-\frac{1}{3}\sum _{ij\in E\left(G\right)}[d_G{\left(i\right)}^3+d_G{\left(j\right)}^3]\hfill \\ & =& \frac{1}{3}\sum _{e\in E\left(G\right)}{[d_G\left(e\right)+2]}^3-\frac{1}{3}{}^4{M}_1\hfill \\ & =& \frac{1}{3}EF+2E{M}_1+4\sum _{e\in E\left(G\right)}{d}_G\left(e\right)+\frac{8}{3}m-\frac{1}{3}{}^4{M}_1.\hfill \end{array}$

Using Lemma 4 and the relation:

$\begin{array}{ccc}\hfill \sum _{e\in E\left(G\right)}{d}_G\left(e\right)& =& \sum _{i\in V\left(L\right)}{d}_L\left(i\right)=2\left|E\left(L\right)\right|=M_1-2m,\hfill \end{array}$

we have:

$\begin{array}{ccc}\hfill \sum _{ij\in E\left(G\right)}{d}_G\left(i\right)d_G\left(j\right)[d_G\left(i\right)+d_G\left(j\right)]& =& \frac{1}{3}EF+2F-8M_1+4M_2+8m+4M_1-8m+\frac{8}{3}m-\frac{1}{3}{}^4{M}_1\hfill \\ & =& \frac{1}{3}(EF-{}^4{M}_1+8m)+2F+4(M_2-M_1).\hfill \end{array}$

 □

Theorem 9.

If $T_1=T_1\left(G\right)$ is vertex-semitotal graph of G, then:

$\begin{array}{c}\hfill E{M}_2\left(T_1\right)=\frac{1}{3}(14{(}^4{M}_1)+4EF+68m)+4E{M}_2+6F-30M_1+28M_2.\end{array}$

Proof. 

By definition

$\begin{array}{c}\hfill E{M}_2\left(T_1\right)=\sum _{e\sim f\in E\left(T_1\right)}{d}_{T_1}\left(e\right)d_{T_1}\left(f\right)\end{array}$

We can divide the pairs of incident edges $(e,f)$ of $T_1=T_1\left(G\right)$ into three cases:

Case 1: When $e,f\in E\left(S\right)$. Just like Theorem 8, we have two further categories:

• For any vertex $i\in V\left(G\right)$, there are $d_G\left(i\right)$ edges, each of degree $2d_G\left(i\right)$ in S, and all these edges are incident at i. Therefore, for any vertex $i\in V\left(G\right)$, the total number of pairs of incident edges lying in this category is $\frac{d_G\left(i\right)(d_G\left(i\right)-1)}{2}$.

• Corresponding to every pair of adjacent vertices i and j in G, there is a pair of incident edges of degrees $2d_G\left(i\right)$ and $2d_G\left(j\right)$ in S.

Case 2: When $e,f\in E\left(G\right)$. For any pair of incident edges e and f in G, e and f are also incident in $T_1$. Furthermore, for any edge $e=ij$ in G,

$\begin{array}{c}\hfill d_{T_1}\left(e\right)=d_{T_1}\left(i\right)+d_{T_1}\left(j\right)-2=2d_G\left(i\right)+2d_G\left(j\right)-2=2(d_G\left(e\right)+1).\end{array}$

Case 3: When $e\in E\left(G\right),f\in E\left(S\right)$. Every edge $ij$ of G has degree $2d_G\left(i\right)+2d_G\left(j\right)-2$ in T. This edge is incident with $d_G\left(i\right)$ edges, each of degree $2d_G\left(i\right)$ at i, and $d_G\left(j\right)$ edges, each of degree $2d_G\left(j\right)$ at j.

Thus:

$\begin{array}{ccc}\hfill E{M}_2\left(T_1\right)& =& \sum _{e\sim f\in E\left(S\right)}{d}_{T_1}\left(e\right)d_{T_1}\left(f\right)+\sum _{e\sim f\in E\left(G\right)}{d}_{T_1}\left(e\right)d_{T_1}\left(f\right)+\sum _{e\sim f,e\in E\left(G\right),f\in E\left(S\right)}{d}_{T_1}\left(e\right)d_{T_1}\left(f\right)\hfill \\ & =& \sum _{i\in V\left(G\right)}\frac{d_G\left(i\right)(d_G\left(i\right)-1)}{2}2d_G\left(i\right)2d_G\left(i\right)+\sum _{ij\in E\left(G\right)}2d_G\left(i\right)2d_G\left(j\right)\hfill \\ & & +\sum _{e\sim f\in E\left(G\right)}2(d_G\left(e\right)+1)2(d_G\left(f\right)+1)\hfill \\ & & +\sum _{ij\in E\left(G\right)}[d_G\left(i\right)(2d_G\left(i\right)+2d_G\left(j\right)-2)2d_G\left(i\right)+d_G\left(j\right)(2d_G\left(i\right)+2d_G\left(j\right)-2)2d_G\left(j\right)]\hfill \\ & =& 2\sum _{i\in V\left(G\right)}{d}_G{\left(i\right)}^4-2\sum _{i\in V\left(G\right)}{d}_G{\left(i\right)}^3+4M_2+4\sum _{e\sim f\in E\left(G\right)}{d}_G\left(e\right)d_G\left(f\right)\hfill \\ & & +4\sum _{e\sim f\in E\left(G\right)}[d_G\left(e\right)+d_G\left(f\right)]+4\sum _{e\sim f\in E\left(G\right)}1+4\sum _{ij\in E\left(G\right)}[d_G{\left(i\right)}^3+d_G{\left(j\right)}^3]\hfill \\ & & -4\sum _{ij\in E\left(G\right)}[d_G{\left(i\right)}^2+d_G{\left(j\right)}^2]+4\sum _{ij\in E\left(G\right)}{d}_G\left(i\right)d_G\left(j\right)[d_G\left(i\right)+d_G\left(j\right)].\hfill \end{array}$

Using Lemma 5 and the fact:

$\begin{array}{c}\hfill \sum _{e\sim f\in E\left(G\right)}1=\sum _{ij\in E\left(L\right)}1=\left|E\left(L\right)\right|=\frac{M_1}{2}-m\end{array}$

we have:

$\begin{array}{ccc}\hfill E{M}_2\left(T_1\right)& =& 2{(}^4{M}_1)-2F+4M_2+4E{M}_2+4E{M}_1+2M_1-4m\hfill \\ & & +4{(}^4{M}_1)-4F+\frac{4}{3}EF-\frac{4}{3}{(}^4{M}_1)+\frac{32}{3}m+8F+16M_2-16M_1.\hfill \end{array}$

Now, using Lemma 4 and simplifying the above expression, we get:

$\begin{array}{c}\hfill E{M}_2\left(T_1\right)=\frac{1}{3}(14{(}^4{M}_1)+4EF+68m)+4E{M}_2+6F-30M_1+28M_2.\end{array}$

 □

Proposition 1.

Let $K_n$ be the complete graph on n vertices, then the total number of pairs of incident edges in $K_n$ is $\frac{n(n-1)(n-2)}{2}$.

Proof. 

The total number of pairs of incident edges in $K_n$:

$\begin{array}{cc}=& \sum _{e\sim f\in E\left(K_n\right)}1=\sum _{ij\in E\left(L\left(K_n\right)\right)}1=E\left(L\left(K_n\right)\right)=\frac{M_1\left(K_n\right)}{2}-\left|E\left(K_n\right)\right|\hfill \\ =& \frac{n{(n-1)}^2}{2}-\frac{n(n-1)}{2}=\frac{n(n-1)(n-2)}{2}.\hfill \end{array}$

 □

Theorem 10.

If $PL=PL\left(G\right)$ is a paraline graph of G, then:

$\begin{array}{c}\hfill E{M}_2\left(PL\right)=2{(}^5{M}_1)+\frac{1}{3}(2EF-26{(}^4{M}_1)+16m)+14F-10M_1.\end{array}$

Proof. 

As we explained in Theorem 7, $PL\left(G\right)$ can be obtained from G by replacing every vertex i by $K_{d_G\left(i\right)}$. Therefore, we can divide the pairs of incident edges of $PL=PL\left(G\right)$ into two cases:

Case 1: For any vertex $i\in V\left(G\right)$, there are $\frac{d_G\left(i\right)(d_G\left(i\right)-1)}{2}$ edges each of degree $(2d_G\left(i\right)-2)$ in the corresponding $K_{d_G\left(i\right)}$ of $PL$, and all these edges are incident with each other. By Proposition 1, for any vertex $i\in V\left(G\right)$, the total number of pairs of incident edges in $K_{d_G\left(i\right)}$ is:

$\begin{array}{c}\hfill =\frac{d_G\left(i\right)(d_G\left(i\right)-1)(d_G\left(i\right)-2)}{2}.\end{array}$

Case 2: Corresponding to every edge $ij$ in G, there is an edge in $PL\left(G\right)$ of the same degree that is incident with $(d_G\left(i\right)-1)$ edges, each of degree $(2d_G\left(i\right)-2)$ at i, and $(d_G\left(j\right)-1)$ edges, each of degree $(2d_G\left(j\right)-2)$ at j.

Thus:

$\begin{array}{ccc}\hfill E{M}_2\left(PL\right)& =& \sum _{e\sim f\in E\left(PL\right)}{d}_{PL}\left(e\right)d_{PL}\left(f\right)\hfill \\ & =& \sum _{e\sim f\in E\left(K_{d_G\left(i\right)}\right),i\in V\left(G\right)}{d}_{PL}\left(e\right)d_{PL}\left(f\right)\hfill \\ & & +\sum _{e=ij\in E\left(G\right)}[(d_G\left(i\right)-1)d_G\left(e\right)(2d_G\left(i\right)-2)+(d_G\left(j\right)-1)d_G\left(e\right)(2d_G\left(j\right)-2)]\hfill \\ & =& \sum _{i\in V\left(G\right)}\left[\frac{d_G\left(i\right)(d_G\left(i\right)-1)(d_G\left(i\right)-2)}{2}\right](2d_G\left(i\right)-2)(2d_G\left(i\right)-2)\hfill \\ & & +2\sum _{ij\in E\left(G\right)}(d_G\left(i\right)+d_G\left(j\right)-2)[{(d_G\left(i\right)-1)}^2+{(d_G\left(j\right)-1)}^2]\hfill \\ & =& 2\sum _{i\in V\left(G\right)}{d}_G\left(i\right){(d_G\left(i\right)-1)}^3(d_G\left(i\right)-2)\hfill \\ & & +2\sum _{ij\in E\left(G\right)}[(d_G{\left(i\right)}^3+d_G{\left(j\right)}^3)-4(d_G{\left(i\right)}^2+d_G{\left(j\right)}^2)+6(d_G\left(i\right)+d_G\left(j\right))\hfill \\ & & -4d_G\left(i\right)d_G\left(j\right)+d_G\left(i\right)d_G\left(j\right)[d_G\left(i\right)+d_G\left(j\right)]-4].\hfill \end{array}$

Now, using Lemma 5:

$\begin{array}{ccc}\hfill E{M}_2\left(PL\right)& =& 2{(}^5{M}_1)-10{(}^4{M}_1)+18F-14M_1+8m+2{(}^4{M}_1)-8F+12M_1-8M_2\hfill \\ & & +\frac{2}{3}EF-\frac{2}{3}{(}^4{M}_1)+\frac{16}{3}m+4F+8M_2-8M_1-8m\hfill \\ & =& 2{(}^5{M}_1)+\frac{1}{3}(2EF-26{(}^4{M}_1)+16m)+14F-10M_1.\hfill \end{array}$

 □

4. Conclusions

In this note, we obtained some relations for degrees between a derived graph and its parent graph. Using these relations, the expressions for reformulated Zagreb indices of some derived graphs have been found in terms of some topological indices of the parent graph. Finding expressions of derived graphs like these is an open problem for many other topological indices.

Author Contributions

All the authors contributed equally to preparing this article.

Funding

This work is partially supported by the China Postdoctoral Science Foundation under grant No. 2017M621579 and the Postdoctoral Science Foundation of Jiangsu Province under grant No. 1701081B. Project of Anhui Jianzhu University under Grant no. 2016QD116 and 2017dc03. Anhui Province Key Laboratory of Intelligent Building and Building Energy Saving.

Acknowledgments

The authors are grateful to the referees for the useful comments that improved the first version of this article.

Conflicts of Interest

The authors declare no conflict of interest.

Figure

Figure 1. Different graphs derived from G.