Trees with Given Diameter Minimizing the Augmented Zagreb Index and Maximizing the ABC Index

HUANG YU-FEI

(Department of Mathematics Teaching,Guangzhou Civil Aviation College,Guangzhou,510403)

Trees with Given Diameter Minimizing the Augmented Zagreb Index and Maximizing the ABC Index

HUANG YU-FEI

(Department of Mathematics Teaching,Guangzhou Civil Aviation College,Guangzhou,510403)

Communicated by Du Xian-kun

Let G be a simple connected graph with vertex set V(G)and edge set E(G).The augmented Zagreb index of a graph G is defned as

and the atom-bond connectivity index(ABC index for short)of a graph G is defned as

where duand dvdenote the degree of vertices u and v in G,respectively.In this paper, trees with given diameter minimizing the augmented Zagreb index and maximizing the ABC index are determined,respectively.

tree,augmented Zagreb index,ABC index,diameter

1 Introduction

Let G be a simple connected graph with vertex set V(G)and edge set E(G).Let Nudenote the set of all neighbors of a vertex u∈V(G),and du=|Nu|denote the degree of u in G. A connected graph G is called a tree if|E(G)|=|V(G)|−1.The length of a shortest path connecting the vertices u and v in G is called the distance between u and v,and denoted by d(u,v).The diameter d of G is the maximum distance d(u,v)over all pairs of vertices u and v in G.

Molecular descriptors have found wide applications in QSPR/QSAR studies(see[1]). Among them,topological indices have a prominent place.Augmented Zagreb index,which was introduced by Furtula et al.[2],is a valuable predictive index in the study of the heat of formation in octanes and heptanes.Another topological index,Atom-bond connectivity index(for short,ABC index),proposed by Estrada et al.[3],displays an excellent correlation with the heat of formation of alkanes(see[3])and strain energy of cycloalkanes(see[4]).

The augmented Zagreb index of a graph G is defned as:

and the ABC index of a graph G is defned as:

Some interesting problems such as mathematical-chemical properties,bounds and extremal graphs on the augmented Zagreb index and the ABC index for various classes of connected graphs have been investigated in[2],[5]and[6]–[10],respectively.Besides,in the literature, there are many papers concerning the problems related to the diameter(see,e.g.,[11]–[13]).In this paper,trees with given diameter minimizing the augmented Zagreb index and maximizing the ABC index are determined,respectively.

2 Trees with Given Diameter Minimizing the Augmented Zagreb Index

2.1 The Augmented Zagreb Index of a Tree with Diameter 3

Lemma 2.1Let

Then g(x)is decreasing for x≥2,and k(x),m(x)are both increasing for x≥2.

Proof.By directly computing,we have

for x≥2.The proof is fnished.

Lemma 2.2Let n≥5 and

Now we consider the following two cases.

In this time,we have

Hence

and

where the functions g(x)and k(x)are defned in Lemma 2.1.Since n−p≥p≥2,by Lemma 2.1,we have

Now we just need to show that J′(p)≥8.By directly computing,we have

Note that

Then from the fact that

we obtain

where the function m(x)is defned in Lemma 2.1.By Lemma 2.1,we get

Combining this with inequality(2.1),namely,J(p)is increasing for p.It implies that J(p+1)−J(p)is decreasing for p.Therefore,

If n is even,then n≥6 and

If n is odd,then n≥5 and

Then by Lemma 2.2,we obtain the desired results.

2.2 Trees with Diameter 4≤d≤n−1 Minimizing the Augmented Zagreb Index

Lemma 2.3[5](1)Z1jis decreasing for j≥2;

(2)Z2j=8 for j≥1;

(3)If i≥3 is fxed,then Zijis increasing for j≥1.

Fig.2.1 T∼=T1

Fig.2.2 T2

Fig.2.3 T3

Fig.2.4 Td−2

Lemma 2.4AZI(Ti)≤AZI(Ti−1)with equality if and only if Vi+1=Ø,where i= 2,3,···,d−2 and 4≤d≤n−1.

Proof.Clearly,AZI(Ti)=AZI(Ti−1)if Vi+1=Ø.It sufce to show that AZI(Ti)＜AZI(Ti−1)if Vi+1/=Ø.

Case 1. i=2.

Notice that|E(T[V3∪{v3}])|=|V3|.By Lemma 2.3,for any uv∈E(T[V3∪{v3}])(since du+dv＞2,without loss of generality,assume that dv＞1),we obtain

Since V3/=Ø,one has dv3＞2.It follows from dv2,dv4≥2 and Lemma 2.3 that

Therefore,bearing in mind that V3/=Ø,

Case 2. 3≤i≤d−2.

Clearly,

For any uv∈E(T[Vi+1∪{vi+1}])(since du+dv＞2,without loss of generality,suppose dv＞1),by Lemma 2.3,we have

Besides,since dvi+1≥2 and dvi+2≥2,by Lemma 2.3,one has

Then

and the last inequality holds since Vi+1/=Ø.

Theorem 2.2Let T∈,where 4≤d≤n−1.Then

with equality if and only if TTd−2.Actually,

Since for x≥2,

the function t(x)is convex increasing for x≥2.

It leads to

3 Trees with Given Diameter Maximizing the ABC Index

In this section,we continue to use the marks in Section 2.

It is known from Section 2 that

By simply computing,we have

where xijdenotes the number of edges in G connecting vertices of degrees i and j,and∆denotes the maximum degree of G.

Lemma 3.2[8],[9](1)A1jis increasing for j≥1;

(3)If i≥3 is fxed,then Aijis decreasing for j≥1.

Lemma 3.3ABC(Ti)≥ABC(Ti−1)with equality if and only if Vi+1=Ø,where i= 2,3,···,d−2 and 4≤d≤n−2.

Proof.It is obvious that ABC(Ti)=ABC(Ti−1)if Vi+1=Ø.We need to show that ABC(Ti)＞ABC(Ti−1)if Vi+1/=Ø.

Case 1. i=2.

Clearly,

By Lemma 3.2,for any uv∈E(T[V3∪{v3}])(since du+dv＞2,without loss of generality, assume that dv＞1),we have

Since V3/=Ø,we know dv3＞2,and combining this with dv2,dv4≥2 and Lemma 3.2,we get

Consequently,

and the last inequality holds since V3/=Ø.

Case 2. 3≤i≤d−2.

It can be seen that

For any uv∈E(T[Vi+1∪{vi+1}])(since du+dv＞2,without loss of generality,suppose dv＞1),it follows from Lemma 3.2 that

Moreover,since dvi+1≥2 and dvi+2≥2,by Lemma 3.2 we have

Then bearing in mind that Vi+1/=Ø,we have

This completes the proof of Lemma 3.3.

have

[1]Todeschini R,Consonni V.Handbook of Molecular Descriptors.Weinheim:Wiley-VCH,2000.

[2]Furtula B,Graovac A,Vuki˘cevi´c D.Augmented Zagreb index.J.Math.Chem.,2010,48: 370–380.

[3]Estrada E,Torres L,Rodr´ıguez L,Gutman I.An atom-bond connectivity index:Modelling the enthalpy of formation of alkanes.Indian J.Chem.,1998,37A:849–855.

[4]Estrada E.Atom-bond connectivity and the energetic of branched alkanes.Chem.Phys.Lett., 2008,463:422–425.

[5]Huang Y F,Liu B L,Gan L.Augmented Zagreb index of connected graphs.MATCH Commun. Math.Comput.Chem.,2012,67(2):483–494.

[6]Das K C.Atom-bond connectivity index of graphs.Discrete Appl.Math.,2010,158:1181–1188.

[7]Furtula B,Graovac A,Vuki˘cevi´c D.Atom-bond connectivity index of trees.Discrete Appl. Math.,2009,157:2828–2835.

[8]Gan L,Hou H Q,Liu B L.Some results on atom-bond connectivity index of graphs.MATCH Commun.Math.Comput.Chem.,2011,66:669–680.

[9]Xing R D,Zhou B,Du Z B.Further results on atom-bond connectivity index of trees.Discrete Appl.Math.,2010,158:1536–1545.

[10]Zhou B,Xing R D.On atom-bond connectivity index.Z.Naturforsch,2011,66a:61–66.

[11]Li S,Zhang M.Sharp upper bounds for Zagreb indices of bipartite graphs with a given diameter.Appl.Math.Lett.,2011,24:131–137.

[12]Pan X,Liu H,Liu M H.Sharp bounds on the zeroth-order general Randi´c index of unicyclic graphs with given diameter.Appl.Math.Lett.,2011,24:687–691.

[13]Yang Y,Lu L.The Randi´c index and the diameter of graphs.Discrete Math.,2011,311: 1333–1343.

A

1674-5647(2017)01-0008-11

10.13447/j.1674-5647.2017.01.02

Received date:Feb.3,2015.

Foundation item:The NSF(11501139)of China.

E-mail address:fayger@qq.com(Huang Y F).

2010 MR subject classifcation:05C35,05C50