# The Third Leap Zagreb Index for Trees

Authors: Jia-Ming Zhu; Nasrin Dehgardi; Xiaoxin Li
Journal: Journal of Chemistry
 (2019)

---

## Abstract

The third leap Zagreb index is the sum of the products of vertex degrees and second degrees. In this paper, a lower bound on the third leap Zagreb index is established, and the extremal trees achieving this bound are characterized.


---

## Body

## 1. Introduction

In this paper, we consider simple and connected graphs. LetG be such a graph with vertex set V=VG and edge set E=EG. The order V of G is denoted by n=nG and the size E of G is denoted by m=mG. The degree of a vertex v in G is the number of edges incident to v and is denoted by dv/G. The minimum and maximum degrees of a graph G are denoted by δ=δG and Δ=ΔG, respectively.Thedistance dGu,v between any two vertices u and v of a graph G is equal to the length of a shortest path connecting them. For a vertex v∈VG and a positive integer k, the open k-neighborhood of v in the graph G, denoted by Nkv/G, is defined as Nkv/G=u∈VG:du,v=k. The k-distance degree of a vertex v in G, denoted by dkv/G, is the number of k-neighbors of the vertex v in G, i.e., dkv/G=Nkv/G. Evidently, d1v/G=dv/G for every v∈VG.Aleaf of a tree T is a vertex of degree one. A stem is a vertex adjacent to a leaf, and a strong stem is a stem adjacent to at least two leaves. An end stem is a stem whose all neighbors with exception at most one are leaves. Denote by ℓv the number of leaves that are adjacent to the vertex v. A rooted tree is a directed tree having a distinguished vertex ω, called the root. For a vertex v in a rooted tree T, let Cv denote the set of children of v and Dv denote the set of descendants of v, whereas the depth of v, depthv, is the largest distance from v to a vertex in Dv.The Zagreb indices are the oldest vertex-degree-based graph invariants. They were introduced in the 1970s [1, 2]. Details of their mathematical theory and chemical applications can be found in the surveys [3–12].For a graphG, the first and second Zagreb indices are defined as(1)M1=M1G=∑v∈VGdvG2,M2=M2G=∑uv∈EGduGdvG.Note that M1G=∑uv∈EGdu/G+dv/G.In recent years, some novel variants of Zagreb indices have been put forward, such as Zagreb coindices [13, 14], reformulated Zagreb indices [15, 16, 17], Zagreb hyper indices [18, 19], multiplicative Zagreb indices [20], general Zagreb indices [21], multiplicative sum Zagreb indices [22, 23], multiplicative Zagreb coindices [24], etc.Naji et al. [25] extended the concept of the Zagreb index to the second vertex degrees, conceiving the so-called leap Zagreb indices. For a graph G, the first, second, and third leap Zagreb indices are defined as follows:(2)LM1=LM1G=∑v∈VGd2vG2,LM2=LM2G=∑uv∈EGd2uGd2vG,LM3=LM3G=∑v∈VGdvGd2vG.In [25], the basic properties of these invariants were established, including bounds in terms of Zagreb indices, order, and the size of the underlying graph. In this paper, we establish a lower bound on the third leap Zagreb index and characterize the extremal trees achieving this bound.


## 2. A Lower Bound on the Third Leap Zagreb Index of Trees

In this section, we present a sharp lower bound for the third leap Zagreb index of trees in terms of their order and maximum degree and characterize all extremal trees.Throughout this section,T denotes a rooted tree with root ω, where ω is a vertex of maximum degree and Nω=w1,w2,…,wΔ.We start with some lemmas.Lemma 1.
LetT be a tree of order n with 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 maximum degree Δ such that LM3T′<LM3T.Proof.
Letu≠ω be a stem of T with du=α≥3 and let NTu=v,x1,x2,…,xα−1, where v is the parent of u. Assume dv=β. We consider the following cases.Case 1. All neighbors ofu except v are leaves.Subcase 1.v is adjacent to a leaf z, and the variable v is preceded by a variable.LetT′ be the tree obtained from T−x1 by attaching the path zx1. Clearly, T′ is a tree of order n with ΔT=ΔT′ and du/T=du/T′+1, dz/T=dz/T′−1, d2u/T=d2u/T′, d2v/T=d2v/T′, d2x1/T=d2x1/T′+α−2=α−1, and d2xi/T=d2xi/T′+1=α−1 for 2≤i≤α−1. By definitions, we have(3)LM3T′−LM3T=∑v∈VT′dvT′d2vT′−∑v∈VTdvTd2vT=∑i=2α−1dxiT′d2xiT′+duT′d2uT′+dzT′d2zT′+dx1T′d2x1T′−∑i=2α−1dxiTd2xiT−duTd2uT−dzTd2zT−dx1Td2x1T=α−2α−2+α−1β−1+2β−1+1−α−2α−1−αβ−1−β−1−α−1=−2α+4<0.Subcase 2.v has no new leaf neighbor.LetT′=T−xiu1≤i≤α−2∪xixi+11≤i≤α−2. Then,(4)LM3T′−LM3T=∑v∈VT′dvT′d2vT′−∑v∈VTdvTd2vT=∑i=2α−1dxiT′d2xiT′+duT′d2uT′+dvT′d2vT′−∑i=2α−1dxiTd2xiT−duTd2uT−dvTd2vT=βk+1+2β+4α−2+2+1−βα+k−1−αβ−1−α−12=−α2+7α−αβ−6.Ifα≥4, then LM3T′−LM3T≤−α2+7α−4β−6≤α2+7α−14<0.Ifα=3 and β≥3, then LM3T′−LM3T=−3β+6<0.Ifα=3 and β=2, then LM3T′−LM3T=2k+1+6−2k+2−7=−3<0.Case 2.u is adjacent to a leaf x1, and uy1y2,…,yℓ is a path in T for ℓ≥2.Ifv is a stem, then the result is immediate as in Case 1. So assume that v is not a stem. Let T′ be the tree obtained from T−x1 by attaching the path yℓx1. Then, d2v/T=d2v/T′+1=k+α−1, d2u/T=d2u/T′, d2x1/T=d2x1/T′+α−2, d2yℓ−1/T=d2yℓ−1/T′−1, and d2xi/T=d2xi/T′+1, for 2≤i≤α−1. Let d2u/T=s. Then,(5)LM3T′−LM3T=∑v∈VT′dvT′d2vT′−∑v∈VTdvTd2vT=βk+α−2+α−1+2α−1+4ℓ−3+4+2+1−βk+α−1−αs−2α−α−1−4ℓ−3−2−1=−α−β−s+3<0.Case 3.u is not a stem, and ux1x2,…,xℓ and uy1y2,…,yt ℓ,t≥2 are two paths in T.Clearlyd2u/T=β+α−2, d2v/T=k+α−1, and d2z/T=du−1=α−1 for z∈Nu−v. Let T′ be the tree obtained from T−x1 by attaching the path ytx1. Then, d2v/T′=k+α−2, d2u/T′=β+α−3, and d2z/T′=α−2 for z∈Nu−x1,y1,v. Also, we have d2xi/T=d2xi/T′ for 2≤i≤ℓ, d2yt/T=d2yt−1/T=1, d2x1/T=d2yt/T′=d2yt−1/T′=2, d2yj/T=d2yj/T′ for 2≤j≤t−2, d2x1/T=d2y1/T=α−1, and d2y1/T′=α−2. Now, we consider the following subcases.Subcase 1.ℓ,t≥3.(6)LM3T′−LM3T=∑v∈VT′dvT′d2vT′−∑v∈VTdvTd2vT=βα+k−2+α−1s−1+2α−1+4ℓ+t−3+2+1−βα+k−1−αs−2α−4ℓ+t−4−4−2=−β−3α−s<0.Subcase 2.ℓ=2,t≥3.(7)LM3T′−LM3T=∑v∈VT′dvT′d2vT′−∑v∈VTdvTd2vT=βα+k−2+α−1s−1+2α−1+4t−1+3−βα+k−1−αs−2α−1−2α−4t−2−2−2=−β−3α−s+2<0.Subcase 3.ℓ=t=2.(8)LM3T′−LM3T=∑v∈VT′dvT′d2vT′−∑v∈VTdvTd2vT=βα+k−2+α−1s−1+2α−1+7−βα+k−1−αs−4α−1−2=−β−3α−s+8<0.
Aspider is a tree with at most one vertex of degree greater than 2, called the center of the spider. If there is no vertex of degree greater than two, then any vertex can be the considered as the center. A leg of the spider is a path from the center to a vertex of degree one. Thus, a star with k edges is a spider with k legs, each of length 1, and the path is a spider with 1 or 2 legs.
By Lemma1, among all trees of order n with maximum degree Δ, the spiders have the minimum third leap Zagreb index. In what follows, we determine the spiders having minimum third leap Zagreb index. If Δ=2, then T≅Pn. Therefore, let Δ≥3.Lemma 2.
LetT be a spider of order n with p≥3 legs. If T has at least two legs of length at least 2, then there is a spider T′ of order n with p legs such that LM3T′<LM3T.Proof.
Letω be the center of T and let ωx1x2,…,xℓ, ωy1y2,…,yt be two legs of length at least two in T. Let T′ be the tree obtained from T−x1x2 by attaching the path ytx2, and let d2ω/T=k. We consider the following cases.Case 1.ℓ=t=2.(9)LM3T′−LM3T=∑v∈VT′dvT′d2vT′−∑v∈VTdvTd2vT=Δk−1+Δ−1+2Δ+3−Δk−4Δ−1−2=−2Δ+4<0.Case 2.ℓ=2,t≥3.(10)LM3T′−LM3T=∑v∈VT′dvT′d2vT′−∑v∈VTdvTd2vT=Δk−1+Δ−1+2Δ+4+3−Δk−2Δ−1−2Δ−3=−2Δ+5<0.Case 3.ℓ,t≥3.(11)LM3T′−LM3T=∑v∈VT′dvT′d2vT′−∑v∈VTdvTd2vT=Δk−1+2Δ+Δ−1+4t+ℓ−4+3−Δk−2Δ−2Δ−4t+ℓ−6−4−2=−2Δ+4<0.
Now, we are ready to state our main result.Theorem 3.
For any treeT of order n≥5 with maximum degree Δ,(12)LM3T≥Δ2−4Δ+4n−9,ifΔ<n−2,Δ2+Δ,ifΔ=n−2,Δ−12,ifΔ=n−1,with equality if and only if T is a spider with at most one leg of length at least two.Proof.
LetT1 be a tree of order n≥2 with maximum degree Δ such that(13)LM3T1=minLM3TTis a tree of ordernwith maximum degreeΔ.
Letv be a vertex with maximum degree Δ. Root T1 at v. 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 LM3T1=n−12. Now, let T1 have only one leg of length at least two. Then, LM3T1=Δ2+Δ when Δ=n−2, and LM3T1=Δ2−4Δ+4n−9 when Δ<n−2. This completes the proof.


## 3. Conclusion

We continue the study of the third leap Zagreb index and establish the lower bound on the third leap Zagreb index of trees in terms of their order and maximum degree. Also, we characterize the extremal trees achieving this bound. We conclude this paper with two open problems.Problem 1.
Present sharp lower bounds for the first and second leap Zagreb indices of trees in terms of their order and maximum degree.Problem 2.
Present sharp upper bounds for the leap Zagreb indices of trees in terms of their order and maximum degree.



---

*Source: 9296401-2019-12-24.xml*