# Lower Bounds on the Entire Zagreb Indices of Trees

Authors: Liang Luo; Nasrin Dehgardi; Asfand Fahad
Journal: Discrete Dynamics in Nature and Society
 (2020)

---

## Abstract

For a (molecular) graphG, the first and the second entire Zagreb indices are defined by the formulas M1εG=∑x∈VG∪EGdx2 and M2εG=∑xiseitheradjacentorincidenttoydxdy in which dx represents the degree of a vertex or an edge x. In the current manuscript, we establish some lower bounds on the first and the second entire Zagreb indices and determine the extremal trees which achieve these bounds.


---

## Body

## 1. Introduction

In the modern era, certain graph invariants present significant applications not only in mathematics but also in other branches of science such as characterization of a molecular structure in computational chemistry and determination of the energies ofπ-electrons in the chemical physics. These invariants may associate a numeric number, a polynomial, a matrix, a sequence of numbers, or a drawing to a graph (or an equivalent object such as a molecular structure). Such values are either identical or possess similar trends for isomorphic graphs. One such revolutionary example of these invariants is a topological index (TI) of the graphs (or equivalent objects), which is sensitive to symmetry, size, bonding pattern, and the shape in a graph. Consequently, the study of the TIs contributes greatly to the quantitative characterizations of the objects (which are equivalent to graphs) in several branches of science. Therefore, the evaluation and the analysis of TIs of graphs are modern trends of research having significant importance in many branches of science, for example, in nanotechnology and theoretical chemistry. A prediction on bioactivity of molecular structures (chemical compounds) in QSAR/QSPR studies can be made on the basis of these graph invariants. Thus, the analysis of the lower/upper bounds of these invariants may possess a significant impact in mathematics and in the prediction of bioactivity. For a comprehensive literature review, the readers are referred to [1–4].Throughout this manuscript, we use the standard notations from the field of graph theory. We consider the simple and connected graphG, and denote a vertex set by V=VG, edge set by E=EG, the cardinality of V by n=nG, and the cardinality of E by m=mG. Furthermore, we denote the degree of a vertex v by dGv=dv (degree of an edge e by dGe=de), minimum and maximum degrees by δ=δG and Δ=ΔG, respectively, and the open neighborhood of v in G by Nv/G. Lastly, ℓv denotes the number of leaves adjacent to the vertex v, Dv denotes the set of descendants of v, and depthv is the largest distance from v to a vertex in Dv. For the notions and notations not given here, we refer the readers [5].For a simple and connected graphG, the first and the second Zagreb indices are defined in terms of the degrees of the vertices by the formulas M1G=∑v∈VGdv2 and M2G=∑uv∈VGdudv, see [6, 7]. The Zagreb indices are among the oldest TIs and have been studied extensively. The development of the study of these indices along with their applications can be seen in the surveys [8–11].In a recent study related to these TIs, several variants of these TIs have been introduced and their properties and applications have been analysed. For example, Zagreb coindices [12], graph operations [13], reformulated Zagreb indices [14, 15], Zagreb hyperindex of graph operations, Zagreb hyperindex and its coindices [16, 17], multiplicative Zagreb indices [18, 19], general Zagreb index [20], multiplicative sum Zagreb index [21, 22], multiplicative Zagreb coindices [23], general first Zagreb index [24], and the First Zagreb index [25]. In [26], an upper bound on the first Zagreb index and coindex in trees was established. In [24], the general first Zagreb index has been expressed in terms of a star sequence. Behtoei [27] studied bounds and relations of the general first Zagreb index and modified the results proved in [24]. For further aspects of the topological descriptors and their applications see [25, 28, 29].Recently, Alwardi et al. [30] extended the concept of Zagreb indices to the vertex and edge degrees, conceiving the so-called entire Zagreb indices. For a simple and connected graph G, the formulas M1εG=∑x∈VG∪EGdx2 and M2εG=∑xiseitheradjacent orincident toydxdydefine the first and the second entire Zagreb indices. Moreover, the basic properties including bounds in terms of Zagreb indices, order, and the size of the underlying graph G were established. In [31], the relationship between the entire Zagreb indices and reformulated Zagreb indices has been developed. Along with this, several inequalities related to these indices involving different graphs have been proved. In this manuscript, we intend to establish some lower bounds on the first and the second entire Zagreb indices and determine those external trees which achieve these bounds. The following theorem providing the exact values of the first and the second entire Zagreb indices for the path Pn (with n≥3) will be useful to determine the lower bounds for trees.Theorem 1 (see [30]).
For any pathPn with n≥3, M1εPn=8n−2 and M2εPn=11 when n=3 and M2εPn=28n−19 when n≥4.Before proceeding further, we include a remark which will be helpful to establish a lower bound for any graphG by using a lower bound for a tree.Remark 1.
LetG be a graph. Then, for every edge e∉EG,(a)
M1εG+e>M1εG.(b)
M2εG+e>M2εG.


## 2. Main Results

Throughout this section,T denotes a rooted tree with root ω, where ω is a vertex of a maximum degree and Nω=w1,w2,…,wΔ. Firstly, for a tree with some useful conditions, we prove existence of another tree of the same order and the same maximum degree which provide lower bounds on the first and second entire Zagreb indices (Figures 1–3).Figure 1
Case1.Figure 2
Case2.Figure 3
Case3.Lemma 1.
LetT be a tree of order n with a maximum degree Δ. If T has a vertex u of degree at least three in maximum distance from ω, then there is a tree T of order n with a maximum degree Δ such that M1εT′<M1εT and M2εT′<M2εT.Proof.
Letu≠ω be an end-stem of T with du=α≥3 and let NTu=x1,x2,…,xα−1,xα=v, where v is the parent of u. We consider the following cases.Case 1.
All neighbors ofu except v are leaves.
LetT′ be the tree obtained from T−x1 by attaching the path x1x2. Then, we have(1)M1εT−M1εT′=∑x∈VT∪ETdx2−∑x∈VT′∪ET′dx2=∑i=1α−1dTuxi2+dTx22+dTu2+dTuv2−∑i=3α−1dTuxi−12−dTu−12−dTuv−12−dT′x22−dT′x1x22−dT′ux22=∑i=3α−1dTuxi2−dTuxi−12+α2−4+dTuv2−dTuv−12+>α2−4≥0,(2)M2εT−M2εT′=∑xiseither adjacent or incident toydTxdTy−∑xiseither adjacent or incident toydT′xdT′y=∑i=1αdTxidTu+dTxidTuxi+dTudTuxi+∑1≤ij≤αdTuxidTuxj+∑w∈NTvdTuvdTvw−∑i=3αdTxidTu−1+dTxidTuxi−1+dTu−1dTuxi−1+∑3≤i<j≤αdTuxi−1dTuxj−1+∑w∈NTvdTuv−1dTvw−∑3≤i≤αdTx2u+1dTxiu−1−dT′x1dT′x2−dT′x1dT′x1x2−dT′x2dT′x1x2−dT′x1x2dTux2+1−dT′x2dTux2+1−dTu−1dTux2+1−dT′x2dTu−1≥2α+α−1+αα−1+α−12α−2+α−3+2α−1dTuv−α−1α−2α−3−α−1−2α−1−α−1dTuv−1−αα−1−2α−1−5>α3−2α2−3>0.Case 2.
Whenu is adjacent to a leaf x1, uy1y2…yl is a path in T for l≥2 and x2=y1.
LetT′ be the tree obtained from T−x1 by attaching the path ylx1. Then,(3)M1εT−M1εT′=∑x∈VT∪ETdx2−∑x∈VT′∪ET′dx2=∑i=2αdTuxi2+dTu2+dTux12+dTyl2+dTylyl−12−∑i=2αdTuxi−12−dTu−12−dTyl+12−dT′x1yl2−dTylyl−1+12>α−12+α2+2−9−α−12=α2−7>0,(4)M2εT−M2εT′=∑xiseither adjacent or incident toydTxdTy−∑xiseither adjacent or incident toydT′xdT′y=∑i=1αdTxidTu+dTxidTuxi+dTudTuxi+∑1≤i<j≤αdTuxidTuxj+∑w∈NTvdTuvdTvw+dTyldTyl−1+dTyldTylyl−1+dTyl−1dTylyl−1+dTyl−1yl−2dTylyl−1−∑i=2αdTxidTu−1+dTxidTuxi−1+dTu−1dTuxi−1−∑2≤i<j≤αdTuxi−1dTuxj−1−∑w∈NTvdTuv−1dTvw−dT′x1dT′yl−dT′x1dT′x1yl−dT′yl−1yl−2dT′ylyl−1−dT′2yldT′2yl−1dT′yldT′x1yl−dT′x1yldT′ylyl−1−dT′yldT′ylyl−1−dT′yl−1dT′ylyl−1≥α3−2α2+5α−17−dTyl−1yl−2>0.Case 3.
Whenu is not a stem, uz1z2,…,zt, and uy1y2,…,yl, l,t≥2 are two paths in T such that x1=z1 and x2=y1.
LetT′ be the tree obtained from T−z1 by attaching the path ylz1. Therefore, we have(5)M1εT−M1εT′=∑x∈VT∪ETdx2−∑x∈VT′∪ET′dx2=∑i=2αdTuxi2+dTu2+dTux12+dTyl2+dTylyl−12−∑i=2αdTuxi−12−dTu−12−dTyl+12−dT′x1yl2−dTylyl−1+12>2α2+2−12−α−12=α2+2α−11>0,(6)M2εT−M2εT′=∑xiseither adjacent or incident toydTxdTy−∑xiseither adjacent or incident toydT′xdT′y=∑i=1αdTxidTu+dTxidTuxi+dTudTuxi+dTz1z2dTuz1+∑1≤i<j≤αdTuxidTuxj+∑w∈NTvdTuvdTvw+dTyldTyl−1+dTyldTylyl−1+dTyl−1dTylyl−1+dTyl−1yl−2dTylyl−1−∑i=2αdTxidTu−1+dTxidTuxi−1+dTu−1dTuxi−1∑2≤i<j≤αdTuxi−1dTuxj−1∑w∈NTvdTuv−1dTvw−dT′z1dT′yl−dT′z1dT′z1yl−dT′yl−1yl−2dT′ylyl−1−dT′z1yldT′z1z2−dT′yldT′z1yl−dT′z1yldT′ylyl−1−dT′yldT′ylyl−1−dT′yl−1dT′ylyl−1−dT′yldT′yl−1≥α3+5α−29−dTyl−1yl−2>0,which completes the proof.
Before proceeding further, we recall some useful definitions from the literature. A spider is a tree with at most one vertex of degree more than 2, which is called the center of a spider. In case, there is no such vertex, then any vertex may be the center. A path from the center to a vertex of degree 1 is called a leg of a spider. Thus, a star withk edges is a spider of k legs, each having length 1, and a path is a spider with 1 or 2 legs. By Lemma 1 we have that between all trees of order n with a maximum degree Δ, spiders have the minimum first and second entire Zagreb indices. Next, we determine the spiders having the minimum first and the second entire Zagreb indices. If Δ=2 then T=Pn. Now, we prove the following important lemma.Lemma 2.
LetT be a spider of order n with p≥3 legs. If T has two legs of length at least 2, then there is a spider T′ of order n with p legs such that M1εT′<M1εT and M2εT′<M2εT.Proof.
Letω be the center of T and let ωx1x2,…,xt and ωy1y2,…,yl,l,t≥2 be the two legs of length at least three in T. Let T′ be the tree obtained from T−x1x2 by attaching the path ylx2. Then,(7)M1εT−M1εT′=∑x∈VT∪ETdx2−∑x∈VT′∪ET′dx2≥dTx12+dTx1x22+dTx1w2+dTyl2+dTyl−1yl2−dT′x12−dT′x1w2−dT′yl2−dT′yl−1yl2−dT′x2yl2=2Δ−4>0.
Now, we show thatM2εT′<M2εT. Firstly, let l=t=2, then(8)M2εT−M2εT′=∑xiseither adjacent or incident toydTxdTy−∑xiseither adjacent or incident toydT′xdT′y≥dTx1dTx2+dTx2dTx1x2+dTx1dTx1x2+dTx1x2dTx1w+dTx1dTx1w+dTx1dTw+dTy1dTy1y2+dTy2dTy1y2+dTy1dTy2+dTx1wdTwy1+dTy1wdTy1y2+dTwdTx1w−dT′x1wdTy1w−dT′x1dTx1w−dT′x1dTw−dT′wdTx1w−dT′x2dT′x2y2−dT′x2dT′y2−dT′x2y2dT′y2−dT′y1dT′y2−dT′y1y2dT′x2y2−dT′y1dT′y1y2−dT′y1y2dT′y2−dT′y1y2dT′wy1=4Δ−8>0.
Ift=2 and l≥3, then(9)M2εT−M2εT′=∑xiseither adjacent or incident toydTxdTy−∑xiseither adjacent or incident toydT′xdT′y≥dTx1dTx2+dTx2dTx1x2+dTx1dTx1x2+dTx1x2dTx1w+dTx1dTx1w+dTx1dTw+dTyl−1dTyl−1yl+dTyldTyl−1yl+dTyl−1dTyl+dTylyl−1dTyl−1yl−2+dTx1wdTwy1+dTwdTx1w−dT′x1wdTy1w−dT′x1dTx1w−dT′x1dTx1w−dT′x1dTw−dT′wdTx1w−dT′x2dTx2yl−dT′x2dT′yl−dT′x2yldT′yl−dT′yl−1dT′yl−dT′yl−1yldT′x2yl−dT′yl−1dT′yl−1yl−dT′yl−1yldT′yl−dT′yl−1yldT′yl−1yl−2=5Δ−10>0.
Finally, letl,t≥3, then(10)M2εT−M2εT′=∑xiseither adjacent or incident toydTxdTy−∑xiseither adjacent or incident toydT′xdT′y≥dTx1dTx2+dTx2dTx1x2+dTx1dTx1x2+dTx1x2dTx1w+dTx1dTx1w+dTx1dTw+dTyl−1dTyl−1yl+dTyldTyl−1yl+dTyl−1dTyl+dTylyl−1dTyl−1yl−2+dTx1wdTwy1+dTwdTx1w−dT′x1wdTy1w−dT′x1dTx1w−dT′x1dTw−dT′wdTx1w−dT′x2dTx2yl−dT′x2dT′yl−dT′x2yldT′yl−dT′yl−1dT′yl−dT′yl−1yldT′x2yl−dT′yl−1dT′yl−1yl−dT′yl−1yldT′yl−dT′yl−1yldT′yl−1yl−2=6Δ−8>0,which completes the proof.
In the following theorems, we prove the lower bounds on the first and the second entire Zagreb indices in terms of the maximum degreeΔ.Theorem 2.
For any treeT of order n≥3 with a maximum degree Δ, we have(i)
M1εT≥Δ3−Δ2+8n−4Δ−12, whenever Δ<n−1.(ii)
M1εT≥n3−4n2+7n−4, for Δ=n−1.
Moreover, the equality corresponding to each case holds if and only ifT is a spider with at most one leg of length at least two.Proof.
LetT1 be a tree of order n≥3 with a maximum degree Δ such that M1εT1=minM2εTTisa tree of ordernwith maximum degreeΔ. Let v be a vertex with a maximum degree Δ and root T1 at v. If Δ=2, then T is a path of order n and the result follows by Theorem 1. Let Δ≥3. By the choice of T1, we deduce from Lemma 1 that T1 is a spider with center v. It follows from Lemma 2 and the choice of T1 that T1 has at most one leg of length at least two. First let all legs of T1 have length one. Then, T1 is a star of order n and M1εT1=n3−4n2+7n−4. Now, let T1 have only one leg of length at least two. Then, M2εT1=Δ3−Δ2+8n−4Δ−12, and this completes the proof.Theorem 3.
For any treeT of order n≥3 with a maximum degree Δ, we get(11)iM2εT≥Δ−121+2Δ+Δ−1Δ−22+2Δ2−11Δ+16n−29forΔ<n−2,iiM2εT≥n−322n+n−3n−42−3+n−3n−2+n−22+5n−5ifΔ=n−2,iiiM2εT≥n−12n−3+n−12n−2+n−1n−232forΔ=n−1.
Furthermore, the equality in each case holds if and only ifT is a spider with at most one leg of length at least two.Proof.
The proof is similar to the proof of Theorem2.
By Remark1, we obtain the following corollary.Corollary 1.
LetG be a graph of order n and maximum degree Δ. Then,(12)iM1εG≥Δ3−Δ2+8n−4Δ−12,wheneverΔ<n−1,(13)iiM1εG≥n3−4n2+7n−4,forΔ=n−1,(14)iiiM2εG≥Δ−121+2Δ+Δ−1Δ−22+2Δ2−11Δ+16n−29,wheneverΔ<n−2,(15)ivM2εG≥n−322n+n−3n−42−3+n−3n−2+n−22+5n−5,forΔ=n−2,(16)vM2εG≥n−12n−3+n−12n−2+n−1n−232,ifΔ=n−1.
The equality corresponding to each case holds if and only ifG is a spider with at most one leg of length at least two.



---

*Source: 8616725-2020-04-27.xml*