# Extremum Modified First Zagreb Connection Index ofn-Vertex Trees with Fixed Number of Pendent Vertices

Authors: Sadia Noureen; Akhlaq Ahmad Bhatti; Akbar Ali
Journal: Discrete Dynamics in Nature and Society
 (2020)

---

## Abstract

The modified first Zagreb connection indexZC1∗ is a graph invariant that appeared about fifty years ago within a study of molecular modeling, and after a long time, it has been revisited in two papers ((Ali and Trinajstić, 2018) and (Naji et al., 2017)) independently. For a graph G, this graph invariant is defined as ZC1∗G=∑v∈VGdvτv, where dv is the degree of the vertex v and τv is the connection number of v (that is, the number of vertices having distance 2 from v). In this paper, the graphs with maximum/minimum ZC1∗ value are characterized from the class of all n-vertex trees with fixed number of pendent vertices (that are the vertices of degree 1).


---

## Body

## 1. Introduction

Throughout this paper, we consider only simple and connected graphs. The vertex set and edge set of a graphG are denoted by VG and EG, respectively. The degree of a vertex v∈VG is the number of edges incident to v and is denoted by dvG or simply by dv if the graph under consideration is clear.LetΩ be the collection of all graphs. A mapping f:Ω⟶ℝ is called a graph invariant or a topological index, if for every graph H isomorphic to G, it holds that fG=fH, where ℝ is the set of all real numbers. In chemical graph theory, there are many topological indices having different applications in isomer discrimination, QSAR/QSPR investigation, pharmaceutical drug design, etc. There are various topological indices that are extensively studied by a number of researchers. The first Zagreb index M1 and the second Zagreb index M2 are among these much studied topological indices. These Zagreb indices for a graph G are defined as(1)M1G=∑v∈VGdv2,M2G=∑uv∈EGdudv.To the best of our knowledge, the first Zagreb index firstly appeared in a formula derived in [1] and the second Zagreb index was firstly introduced in [2]. These two Zagreb indices have several chemical applications, for example, see the recent papers [3, 4]. Detail about the mathematical properties of the indices M1 and M2 can be found in the recent survey papers [5–8], recent papers [9–22], and related references listed therein.The following topological indexZC1∗ is known as the modified first Zagreb connection index [23]:(2)ZC1∗G=∑v∈VGdvτv,where τv is the connection number of the vertex v (that is, the number of vertices having distance 2 from v, see [24]). Actually, this index initially appeared within a certain formula, derived by Gutman and Trinajstić [1]. The index ZC1∗ was referred as the third leap Zagreb index in [25]. After the publications of the papers [23, 25], the modified first Zagreb connection index has attracted a considerable attention from researchers, for example, see [25–39].The main idea of the present paper comes from [40]. In the present paper, the sharp lower and upper bounds on the modified first Zagreb connection index of trees in terms of order and number of pendent vertices are derived and the corresponding extremal trees are characterized.


## 2. Some Definitions and Notations

Fors≥1, let P=v0v1,…,vs be a path in a graph G with dv1=⋯=dvs−1=2 unless s=1. If dv0=1 and dvs≥3, then P is called a pendent path of G and s is called the length of this pendent path. If dv0,dvs≥3, then P is called an internal path of G. A tree containing exactly one vertex of degree greater than 2 is called a starlike tree. K1,n1p1,p2,…,pn1 is used to denote the starlike tree of order n which is obtained by attaching paths of lengths p1,p2,…,pn1 to the pendent vertices of the star K1,n1 where n=n1+1+∑i=1n1pi and pi≥0 for all 1≤i≤n1.P
T
n
,
n
1 is used to denote the set of all trees of order n≥5 and with n1 pendent vertices. Since the path graph is the only member of PTn,2 and the star graph is the unique element of PTn,n−1, we assume 3≤n1≤n−2 in the remaining part of the paper. For any T∈PTn,n1, we assume V1T:=v:v is a pendent vertex of T, V2T:=∪v∈V1TNv, and V3T:=VT\V1T∪V2T. Taking Sn1n:=K1,n10,0,…,n−n1−1 and Kn1n:=K1,n10,0,…,0,1,1,…,1︸n−n1−1, we assume that Tn1n:=K1,n1p1,p2,…,pn1:pi≥1,1≤i≤n1. Then, Kn1n⊆PTn,n1, Sn1n⊆PTn,n1, and Tn1n⊆PTn,n1 (see Figure 1).Figure 1
The elements of the classPTn,n1. (a) T∈Sn1n. (b) T∈Kn1n. (c) T∈Tn1n.
(a)
(b)
(c)LetTn1∗:=T∈PT2n1−2,n1:T has n1−2 vertices of degree 3, where n1≥4, further E∗T:=uv∈ET:du=dv=3. Let Tn,n1∗ be a set of trees of order n obtained from T∈Tn1∗ by replacing each edge of E∗T by a path with length at least 2.


## 3. On the Minimum Modified First Zagreb Connection Index of Trees with Fixed Number of Pendent Vertices

Lemma 1.
(see [41]). Let T∈PTn,n1 and v∈VT, then(i)
dv≤n1,(ii)
dv=n1>2 which implies that T is a starlike tree.Lemma 2.
LetT∈PTn,n1 and P=v0v1,…,vs be considered as a suspended path of T such that v0∈V1T and dvs=t≥3. Considering Nvs∩V1T=q and Nvs\V1T∪vs−1=x1,x2,…,xt−q for s=1 and Nvs\V1T∪vs−1=x1,x2,…,xt−q−1 for s≥2 and let dxi=di≥2 for 1≤i≤t−q, then(a)
Ifs≥2, then (i) ∑i=1t−q−1di≤n1+t−2q−2 and (ii) q≥max0,2t−n.(b)
Ifs=1, then (i) ∑i=1t−qdi≤n1+t−2q and (ii) ≥max1,2t−n+1.Proof.
(a)
See [41].(b)
(i) AsT\v0,v1 contains t−q subtrees Tx1,Tx2,…,Txt−q containing x1,x2,…,xt−q, respectively, where each Txi has at least di−1 pendent vertices of T. Therefore, ∑i=1t−qdi−1≤n1−q or ∑i=1t−qdi−1≤n1+t−2q.(ii)
Since forn≥2t the result is obvious, so let n<2t, and we observe that ∑i=1t−q−1di≤n−t+1 and also ∑i=1t−q−1di≥t−q as di≥2.
Hence,t−q≤n−t−1 or q≥2t−n+1.Lemma 3.
IfT∈PTn,n1 is a tree such that ZC1∗T is as small as possible, then T contains at most one pendent path of length greater than 1.Proof.
We contrarily assume thatP=v0v1,…,vs and P′=v0′v1′,…,vl′l,s≥2 are two pendent paths of T such that v0,v0′∈V1T and dvs,dvl′≥3. If T′=T−vs−1vs−2+vs−2v0′, then T′∈PTn,n1 and we have(3)ZC1∗T′−ZC1∗T=dvs−1−3dvs−2+4−1=22−dvs<0,which is a contradiction to the choice of T.
Let us denoteTn1=T:T∈PTn,n1 and Tis a generalized star.Lemma 4.
For any treeT∈Tn1,(4)ZC1∗T≥4n+n12−3n1−8.
Equality in the above expression holds if and only ifT≅Sn1n.Proof.
LetT′∈Tn1 be the tree with minimal ZC1∗ among all the members of Tn1. Since T′≅K1,n1, therefore it contains at least one pendent path of length greater than 1. By using Lemma 4, we conclude that T′ contains exactly one pendent path of length greater than 1. Therefore, T′≅Sn1n. Since T′ is a starlike tree, and for any T∈Tn1,(5)ZC1∗T≥ZC1∗T′=4n+n12−3n1−8,and equality in the above expression holds if and only ifT≅Sn1n.Lemma 5.
IfT∈PTn,n1\Tn1 is a tree such that ZC1∗T is as small as possible, then T does not contain a pendent path of length greater than 1.Proof.
We contrarily assume thatP=v0v1,…,vss≥2 be a pendent path of T such that v0∈V1T and dvs=q≥3. As T∈PTn,n1\Tn1, so there must be a vertex v∈VT\vs, with v∈VT\vs. Also, there must be a path between v and vs. Let u be a vertex in this path, adjacent to vs, and also, let du=t≥2. If T′=T−vsu,v0v1+v0vs,v1u, then T′∈PTn,n1\Tn1 and we have(6)ZC1∗T′−ZC1∗T=3t−4+q−2tq+t+q=2q−21−t<0,which is a contradiction to the minimality of T.Theorem 1.
IfT∈PTn,n1 for 3≤n1≤n−2, then(7)ZC1∗T≥4n−8,ifn1=3,andn≥5,(8)ZC1∗T≥4n+4n1−22,if4≤n1≤n−2.In the above inequality (7), equality holds if and only if T≅S3n. In (8), equality holds if and only if n≥3n1−5 and T∈Tn,n1∗.Proof.
Let we denoteϕn,n1=4n+4n1−22. If we take T∈Tn1, then by Lemma 4, ZC1∗T≥4n+n12−3n1−8 and the equality holds if and only if T≅S3n. So, the above theorem holds. Now, we assume that T∈PTn,n1\Tn1 and 4≤n1≤n−2. We observe that if T∈Tn,n1∗, then n≥3n1−5 and equality in equation (8) can be obtained by a simple elementary calculation. Now, by applying induction on n1, we show that if T∈PTn,n1\Tn1, then (8) holds and the equality in (8) holds only if T∈Tn,n1∗. Let us choose T such that ZC1∗T is as small as possible.
Ifn1=4, then by Lemma 5 T∈T4∗ when n=6, or T∈Tn,4∗ if n≥7. Hence, ZC1∗T=20>ϕn,n1ifn=6 and ZC1∗T=4n−6=ϕn,n1ifn≥7. Therefore, equality in (8) holds for n1=4 only if n≥7 and T∈Tn,4∗. We assume that n1≥5 and the result is true for all smaller values of n1.
Letu∈V2T and denote the degree of vertex u by t. Considering v1,v2,…,vq and vq+1,vq+2,…,vt as the pendent and nonpendent neighbors of u, respectively, then t−q≥1 (because T≇K1,n−1). Lemma 5 ensures that HTML translation failed, and we consider the following cases:Case I:t≥4.LetT′=T−v1. So, T′∈PTn−1,n1−1 and we have(9)ZC1∗T=ZC1∗T′+2q−2+2∑i=q+1tdvi≥ϕn−1,n1−1+2q−1+22t−q=ϕn,n1+2t+2t−q−10≥ϕn,n1.Case II:t=3.Ifq=1, then we take Nu\v1=x1,x2 and let dxi=di for i=1,2.IfT′=T−v1, then T′∈PTn−1,n1−1 and(10)ZC1∗T=ZC1∗T′+2d1+2d2≥ϕn−1,n1−1+8=ϕn,n1,and equality holds only ifd1=d2=2 and ZC1∗T′=ϕn−1,n1−1. Further, by induction hypothesis, T′∈Tn−1,n1−1∗. As d1=d2=2, so there must be an internal path of length at least 4, connecting x1 and x2 in T′ and VT′≥3n1−1−3. Hence, n=VT′+1≥3n1−5 and T belongs to Tn,n1∗. If we take q=2, then Nu\v1,v2=x1 and let dx1=d1. Assuming that P:u0=uu1=x1u2,…,ul be an internal path of T with du=3 and dul=s≥3, having l≥1, we consider the following cases:Subcase I. If l=1,we considerT′=T−v1,v2, then T′∈PTn−2,n1−1 and(11)ZC1∗T=ZC1∗T′+2+4d1≥ϕn−2,n1−1+2+4d1=ϕn,n1+4d1−10>ϕn,n1.(12)ZC1∗T=ZC1∗T′+2s+4l+2≥ϕn−l−1,n1−1+2s+4l+2=ϕn,n1+2s−6≥ϕn,n1.
Subcase II. If l≥2,
we can obtain a treeT′=T−v1,v2,u0,…,ul−2 such as T′∈PTn−l−1,n1−1 and
To get equality, all the relations considered above should be reduced to equalities. So, we getZC1∗T=ϕn−l−1,n1−1, s=3, and l≥2.
Further, by induction hypothesis,T′∈Tn−l−1,n1−1∗ and VT′≥3n1−1−3−l. Therefore, n=VT′+l+1≥3n1−5 and T∈Tn,n1∗ which completes the proof.


## 4. On the Maximum Modified First Zagreb Connection Index of Trees with Fixed Number of Pendent Vertices

Lemma 6.
LetT∈PTn,n1 be a tree that maximizes ZC1∗, then(a)
Forn≥2n1+1, T contains at least one pendent path of length greater than 1,(b)
Forn≤2n1, T contains at least one pendent path of length 1.Proof.
(a)
Letn≥2n1+1, and we assume that every pendent path of T has length at most 1, so we have du≥3 for all u∈V2T. Now, we show that dw≥3 for all w∈V3T. Otherwise, there would be a path P=w0w1w2,…,wqwq+1, such that for some l, 1<l<q, wl∈V3T, and dwl=2, where w0,wq+1∈V1T. Let dwi=di, 0≤i≤q+1. Then, d1,dq≥3 and di≥2 for 2≤i≤q−1.IfT′=T−wl−1wl,wlwl+1,w0w1+wl−1wl+1,w0wl,w1wl, then T′∈PTn,n1 and we have(13)ZC1∗T′−ZC1∗T=1+3d1−2+2dl−1dl+1−dl−1−dl+1−2d1+1+d1−4dl−1+2+dl−1−4dl+1+2+dl+1=2d1−4+2dl−1−2dl+1−2>0,which is a contradiction to the choice ofT. Hence, we have the result that dv≥3 for all v∈VTV1T. Therefore, 2n−1=∑v∈VT≥n1+3n−n1 which gives n≤2n1−2, a contradiction.(b)
Now forn≤2n1, if we assume that each pendent vertex of T is adjacent to a vertex of degree 2, then V2T=n1. Since T≇K1,n−1, we therefore have VT\V1T∪V2T≥1. Hence, n=V1T+V2T+VT\V1T∪V2T≥2n1+1, a contradiction.Theorem 2.
LetT be a tree such that T∈PTn,n1, and if 3≤n1≤n−2, then(14)ZC1∗T≤4n+3n12−9n1−4,ifn≥2n1+1,(15)ZC1∗T≤n12n−n1−3,ifn≤2n1.Equalities in (14) and (15) hold if and only if T∈Tn1n and T≅Kn1n, respectively.Proof.
We observe that ifT∈Tn1n and T≅Kn1n, then, respectively, equalities (14) and (15) hold by using simple elementary calculation.Let us denoteφ1n,n1:=4n+3n12−9n1−4 and φ2n,n1:=n12n−n1−3. Now, by applying induction on n1, we show that if T∈Tn,n1 for n1≥3, then (14) and (15) hold and the equalities in (14) and (15) hold only if T∈Tn1n and T≅Kn1n, respectively. Let n1=3, then T is a starlike tree and n≥5. It can be easily verified that T5,3=T1 and T6,3=T2,T3 (see Figure 2).Note thatZC1∗T1=12=φ25,3, ZC1∗T2=16<φ26,3, ZC1∗T3=18=φ26,3, and T1≅K35, T3≅K36. Therefore, Theorem 2 holds for n=5,6, so we assume that n≥7 or n≥2n1+1, and we find the following results:(16)ZC1∗T=4n−4=φ1n,3,if T∈T3n,4n−8<φ1n,3,if T≅S3n,4n−6<φ1n,3,if T∈Tn,3\T3n∪S3n.So, now we have to considern1≥4, as the results hold for the smaller values of n1. Let T∈Tn,n1 if T≅Sn1n, then ZC1∗T=4n+n12−3n1−8. Therefore, ZC1∗T=φ1n,n1−2n1−1n1−2<φ1n,n1 and(17)ZC1∗T=φ2n,n1−2n1−2n−n1−2≤φ2n,n1.We observe that equality in (17) holds if n=n1+2. Also, if n=n1+2, then Sn1n≅Kn1n. Now, we consider the case that T≇Sn1n and T≇Kn1n for 4≤n1≤n−3.LetP:v0v1,…,vs be a pendent path of T such that v0∈V1T and dvs=t≥3. Considering Nvs∩V1T=q and Nvs\V1T∪vs−1=x1,x2,…,xt−q−1. Then, q≥0, t−q≥2SinceT≇Kn1n and dxi=di≥2. Now, we consider the following two cases:Case I.n≥2n1+1.Here, we chooseT such that ZC1∗T is as large as possible. Therefore, by Lemma 6, T contains at least one pendent path (say) P of length greater than 1. Let us consider T′=T−v0,v1,…,vs−1, so T′∈PTn−s,n1−1. Now, for n−s≥2n1−1+1, Lemma 2 implies that ∑i=1t−q−1di≤n1+t−2q−2 and(18)ZC1∗T=ZC1∗T′+1+4s−2+3t−2+q−t−q−1+2∑i=1t−q−1di≤φ1n−s,n1−1+1+4s−2+3t−2+q−t−q−1+2n1+t−2q−2=φ1n,n1−4n1+4t−2q≤φ1n,n1,where the equality holds if all the inequalities mentioned in the above argument turn into equalities. Thus, we haveZC1∗T′=φ1n−s,n1−1,ifq=0andn1=t.By the induction hypothesis,T′∈Tn1−1n−s. Here, T′ contains a unique vertex of degree greater than 2, and hence T∈Tn1n.Now ifn−s≤2n1−1, then(19)ZC1∗T=ZC1∗T′+1+4s−2+3t−2+q−t−q−1+2∑i=1t−q−1diφ2n−s,n1−1+1+4s−2+3t−2+q−t−q−1+2n1+t−2q−2φ1n,n1+2n1−6n−s−4n12+10n1−6+4t−2qφ1n,n1+2n1−12n1−6−4n12+10n1−6+4t−2qφ1n,n1−4n1+4t−2n1−6−2q<φ1n,n1.Case II:n≤2n1By using Lemma2, we may choose P with s=1. Let T′=T−v0, then T′∈PTn−1,n1−1. So.(20)ZC1∗T=ZC1∗T′+2q−2+2∑i=1t−qdi≤ZC1∗T′+2n1+2t−2q−2.Now ifn=2n1, then n−1=2n1−1 and we get(21)ZC1∗T≤φ12n1−1,n1−1+2n1+2t−2q−2=φ22n1,n1−2n1+2t−2q+2≤φ22n1,n1,where the equality holds only ifZC1∗T′=φ12n1−1,n1−1, q=1, and n1=t. As T′≅Kn1−12n1−1 and Kn1−12n1−1 contain a unique vertex with degree greater than 2, so we have T≅Kn12n1.If we haven<2n1, then(22)ZC1∗T≤φ2n−1,n1−1+2n1+2t−2q−2=φ2n,n1−2n+2n1+2t−2q+2≤φ2n,n1.The above inequality follows from Lemma2. Equality ZC1∗T=φ2n,n1 shows that all the above relations are also equalities. Particularly ZC1∗T′=φ2n−1,n1−1. Therefore, by induction hypothesis, T′≅Kn1−1n−1. We observe that Kn1−1n−1 contains a unique vertex of degree greater than 2 and dvs≥3, hence T≅Kn1n. By this result the proof of Theorem 2 is complete.Figure 2
The trees (a) T1, (b)T2, and (c) T3.
(a)
(b)
(c)



---

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