# Note on the Reformulated Zagreb Indices of Two Classes of Graphs

Authors: Tongkun Qu; Mengya He; Shengjin Ji; Xia Li
Journal: Journal of Chemistry
 (2020)

---

## Abstract

The reformulated Zagreb indices of a graph are obtained from the original Zagreb indices by replacing vertex degrees with edge degrees, where the degree of an edge is taken as the sum of degrees of its two end vertices minus 2. In this paper, we obtain two upper bounds of the first reformulated Zagreb index among all graphs withp pendant vertices and all graphs having key vertices for which they will become trees after deleting their one key vertex. Moreover, the corresponding extremal graphs which attained these bounds are characterized.


---

## Body

## 1. Introduction

Some constants are used to characterize some properties of the graph of a molecule, which are usually called topological indices. One of the most famous topological indices is the Randić index (Randić connectivity index), proposed by Randic [1] in 1975 (for details, see [2, 3]). Soon later, a lot of mathematicians focused on the structure and application of Randić connectivity index. In 1977, Kier and Kall [4] extended the concept of molecular connectivity index and defined the zeroth-order general Randić index. Note that the first Zagreb index is the zeroth-order general Randić index for α=2. For more results of the zeroth-order general Randić index and first Zagreb index, we refer to [5, 6, 7]. In addition, Zagreb indices have been explored as molecular descriptors in QSPR and QSAR (see [8, 9, 10, 11, 12, 13, 14, 15, 16, 17–20]). For a graph G, the first Zagreb index M1 and the second Zagreb index M2 [21] are defined as(1)M1=M1G=∑v∈VGdv2,M2=M2G=∑uv∈Edudv.For an edgee=uv, the edge degree of e is referred as the sum of degrees of its two end vertices minus 2 and is denoted by de=du+dv−2. e∼f indicates the edges e and f are adjacent.For a givenG, let LG be its line graph. Observe that two edges are adjacent in G if and only if the corresponding two vertices are adjacent in LG. The edge version of the Zagreb indices [22], motivated by the above property, was proposed by Miličeviv́ et al. in 2004 through the edge degree instead of vertex degree, that is,(2)EM1G=∑e∈Ede2,EM2G=∑e∼fde⋅df.The reformulated Zagreb indices, particularly its bounds, have attracted recently the attention of many mathematicians (see, [12, 22–30]).In order to describe this more clearly in the sequel, we now introduce some notations. LetGnp be the set of connected graphs with p≥2 pendant vertices. Evidently, if G∈Gnp, then there will be a connected subgraph H0 with order n−p for which G can be reconstructed by linking p vertices to some vertices H0. For convenience, we call H1 as the core of G. Since H0 is connected, it has two extremal cases, i.e., H0≅Kn−p and H0≅Tn−p. Let An∈Gnp be the graph with core Kn−p, and let all pendants of An have a common neighbor in Kn−p. Let Bn be the set of all graphs for which each of its element will be changed to a tree by deleting some of its vertex. That is to say, if G belongs to Bn, then there is a vertex v0∈VG such that G−v0 is isomorphic to a tree. We call the vertex v0 as the key of G. Note that, for a given graph, its key may not be unique, e.g., G is a cycle, and every vertex is a key of G. Let Bn be the graph with two vertices having degree n−1 and other vertices owning degree 2. Obviously, Bn∈Bn and the two vertices possessing degree n−1 are keys.In this paper, we determined the two upper bounds of reformulated Zagreb indices of two kinds of graphs and characterized completely extremal graphs.


## 2. Main Results

In the section, we will research the maximal properties regarding the reformulated Zagreb index onGnp and Bn, respectively. Meanwhile, the graphs attaining the bounds are obtained.Based on the definition ofEM1, the following result holds obviously.Proposition 1.
LetG be a connected graph.(i)
Ife∈EG, then EM1G>EM1G−e(ii)
Ife∉EG, then EM1G<EM1G+eLemma 1.
G and G′ denote the two graphs as shown in Figure 1, and G′ is regarded as the graph from G by shifting all pendants of vs to vt. If dGvt≥dGvs and dGvs≥n−p, then EM1G′>EM1G.Figure 1
G and G′ used in Lemma 1.
(a)
(b)Proof.
Let G andG′ be the two graphs as shown in Figure 1, and vs and vt be two vertices owning ℓ pendants and k pendants, respectively. The common neighbors of vs and vt are labeled as u1,u2,…,un−p−2, and these n−p vertices induce a complete subgraph Kn−p of G. We write r=n−p−2 for short. Obviously, dGvt=k+r+1, dGvs=ℓ+r+1, dG′vt=k+ℓ+r+1, and dG′vs=r+1. In order to show EM1G′>EM1G, we can confirm that EM1G′−EM1G>0. In fact, we arrive at(3)EM1G′−EM1G=∑i=1rdG′vt+dG′ui−22+∑i=1rdG′vs+dG′ui−22+∑i=1k+ℓdG′vt−12+dG′vt+dG′vs−22−∑i=1rdGvt+dGui−22−∑i=1rdGvs+dGui−22−∑i=1kdGvt−12−∑i=1ℓdGvs−12−dGvt+dGvs−22=r2r2+rk+ℓ+2r2+k+ℓk+ℓ+r2−rℓ+2r2+rk+2r2+kk+r2+ℓℓ+r2>2rkℓ>0.
The proof hence is complete.Theorem 1.
IfG∈Gnp, then EM1G≤n−p−122n−2p−42+n−p−12n−p−42+pn−22. Furthermore, the above equality is attained only if G≅An.Proof.
LetG be a graph with n vertices and p pendants and having the maximum with respect to EM1. Let H0 denote the core of G. Clearly, H0 is connected. In fact, H0≅Kn−p. On the contrary, suppose that H0 is not a complete subgraph of G. That is to say, there are some nonadjacent vertex pairs in H0. After connecting these pairs of H0, we obtain a new graph G1. Evidently, G1∈Gnp. From Proposition 1, EM1G1>EM1G, which is contradicted with the maximum of G.
We now show that all pendants of G are adjacent to the same vertex inH0. If not, assume that there are two vertices vs,vt∈VH0 possessing pendants. In other words, dvs,dvt≥n−p. We obtain a new graph G′∈Gnp by removing all pendants of vs and joining them to vt. Then, by Lemma 1, EM1G′>EM1G. Hence, all pendants in G own a common neighbor. In other words, G≅An. In addition, by calculation,(4)EM1An=n−p−122n−2p−42+n−p−12n−p−42+pn−22.
Therefore, we complete the proof.Lemma 2.
LetG be a graph with key v0, and let T=G−v0 be a tree having an edge e=vsvt with dTvt≥dTvs≥2. If G′ is obtained by deleting the ℓ branches of vs and adding them to vt, then EM1G′>EM1G.Proof.
LetG and G′ are two graphs with n vertices as shown in Figure 2. Suppose that dTvt≥dTvs≥2. It is clear that dTvs=ℓ+1, dTvt=k+1, dT′vt=dTvt+ℓ, and dT′vs=1. We now consider the difference EM1G′−EM1G and deduce that(5)EM1G′−EM1G=∑i=1kdG′vt+dG′wi−22+∑i=1ℓdG′vt+dG′ui−22+dG′vt+dG′vs−22+dG′v0+dG′vs−22+dG′vt+dG′v0−22−dGvt+dGv0−22−dGvt+dGvs−22−dGv0+dGvs−22−∑i=1kdGvt+dGwi−22−∑i=1ℓdGvs+dGui−22>n−12+k+ℓ+n−12−n−1+ℓ2−k+n−12=2kℓ>0.
Therefore, the result holds.Figure 2
G and G′ used in Lemma 2.
(a)
(b)Theorem 2.
LetG∈Bn. Then, EM1G≤2n3−4n2−10n+12 with equality if and only if G≅Bn.Proof.
LetG be a graph in Bn. Hence, there is a vertex v0∈VG such that T=G−v0 is a tree with n−1 vertices. Assume that G is the maximal graph with respect to EM1. We firstly claim that dGv0=n−1. Otherwise, if G−v0 is a tree for v0∈VG, we have dGv0<n−1. Let the new graph G1 is obtained from G by connecting v0 to all of its nonadjacent vertices in G. Hence, by Proposition 1, EM1G1>EM1G, which is contradicted with the choice of G.
We next claim that the treeT is isomorphic to a star with n−1 vertices. If not, we find an edge e=vsvt in ET such that dTvt,dTvs≥2. Suppose now that dTvt≥dTvs. From Lemma 2, we will obtain a new graph G2∈Bn and EM1G2 is more than EM1G, a contradiction. Based on the above discussion, we deduce that G≅Bn. Furthermore, by direct calculation, EM1Bn=2n3−4n2−10n+12.
Consequently, the proof is complete.



---

*Source: 4860327-2020-02-10.xml*