On Augmented Zagreb Index of Molecular Graphs

DU Jian-wei (杜建伟) ，SHAO Yan-ling (邵燕灵)，SUN Xiao-ling (孙晓玲)

1 School of Science，North University of China，Taiyuan 030051，China

2 School of Information and Communication Engineering，North University of China，Taiyuan 030051，China

Introduction

Molecular descriptors have found wide applications in QSPR/QSAR studies.Among them，topological indices have a prominent place［1］.Topological indices are numbers associated with chemical structures derived from their hydrogen-depleted graphs as a tool for compact and effective description of structural formulas which are used to study and predict the structure-property correlations of organic compounds.

Let G =(V(G)，E(G))be a connected simple graph in which V(G)and E(G)are the vertex set and edge set of G，respectively.Let n= |V(G)| and m= |E(G)|.We use N(u)to denote the set of all neighbors of u∈V(G)in G，and d(u)= |N(u)| to denote the degree of u.A vertex u is called a pendent vertex if d(u)=1.A connected graph G is known as a molecular graph if its maximum degree is at most four.A connected graph G is called a tree if m = n -1.A hexagonal system is a finite connected plane graph with no cut vertex in which every interior region is surrounded by a regular hexagon of side length 1.Hexagonal systems are the natural graph representation of benzenoid hydrocarbons and have considerable importance in chemistry.A hexagonal system without internal vertex is called catacondensed hexagonal system［2-3］.

The augmented Zagreb index (AZI index for short)was firstly introduced by Furtula et al.in Ref.［4］，which is defined to be

It has been shown that this graph invariant is a valuable predictive index in the study of the heat of formation in octanes and heptanes［4］，whose prediction power is better than atombond connectivity index (please refer to Refs.［3，5-8］for its research background).In Ref.［4］，Furtula et al.obtained some tight upper and lower bounds for the AZI index of a chemical tree，and determined the trees of order n with minimal AZI index.Huang et al.［9］gave some attained upper and lower bounds on the AZI index and characterized the corresponding extremal graphs.Wang et al.［10］obtained some bounds on the AZI index of connected graphs by using different graph parameters， and characterized the corresponding graphs.Moreover，Ali et al.［11］proposed the tight upper bounds for AZI index of chemical bicyclic and unicyclic graphs and gave the Nordhaus-Gaddum-type result for AZI index.

In this paper，we first characterize the catacondensed hexagonal systems with extreme augmented Zagreb index in Section 1.In Section 2，the lower bound for augmented Zagreb index of molecular trees with fixed numbers of pendent vertices is presented，and the extremal trees are characterized.In Section 3，another proof of a known theorem in Ref.［10］on augmented Zagreb index is given.Our other notations are standard and taken mainly from Ref.［12］.

1 Extreme Augmented Zagreb Index of Catacondensed Hexagonal Systems

Throughout this section，the following notations and terminology will be used.Let Chbe the set of catacondensed hexagonal systems with h hexagons.For Ch∈Ch，a hexagon s of Chis called a kink of Chif s has exactly two consecutive vertices with degree 2 in Ch，and called a branched hexagon if s has three neighboring hexagons.For a hexagonal system Ch∈Ch，its dualist graph D(Ch)is the graph whose vertex set is the set of hexagons of Ch，and two vertices of which are adjacent if the corresponding hexagons have a common edge.Clearly the dualist graph of a catacondensed hexagonal system is a tree with the maximum degree at most 3.A kink (respectively branched hexagon) of Chcorresponds to a vertex of degree 2(respectively degree 3)in the dualist graph D(Ch)of Ch.Let p(Ch) (respectively q (Ch)) be the number of kinks(respectively branched hexagons)in Ch.

Theorem 1 Let Ch∈Ch，then

Proof We prove the result by induction on h.

If h=1，2，then p(C1)=q(C1)=0.It is easy to check that Eq.(2)holds for h=1，2.

If h = 3，then q (C3)= 0.Suppose p (C3)= 0(respectively p(C3)= 1)，thenso Eq.(2)holds for h=3.

Suppose that h≥4 and Eq.(2)holds for all Ch-1∈Ch-1，that is，Let Ch∈Ch，which is obtained by gluing a new hexagon shto some Ch-1.Without loss of generality，suppose the hexagon shis adjacent to some hexagon skin Ch-1.Now in Chthere exist the following three cases.

Case 1.skis a branched hexagon of Ch.Then p(Ch)= p(Ch-1)- 1 and q(Ch)= q(Ch-1)+1.By the induction hypothesis and direct computation，it can be shown that

Case 2.skis a kink of Ch.Then p(Ch)=p(Ch-1)+1 and q(Ch)= q(Ch-1).By the induction hypothesis and direct computation，it can be shown that

Case 3.Otherwise，p(Ch)= p(Ch-1)and q(Ch)=q(Ch-1).By the induction hypothesis and direct computation，it can be shown that

Therefore，Theorem 1 holds.

The linear hexagonal chain Lhwith h hexagons is the catacondensed hexagonal systems without kink and branched hexagon.Let Dhbe the set of the catacondensed hexagonal systems with h hexagons for which the dualist graph of any hexagonal systems Ch∈Dhhas at most one vertex of degree 2，and the vertex of degree 2 corresponds to a kink of Ch.It is easy to see that any hexagonal system in Dhhas exactlybranched hexagons.

Theorem 2 Let Ch∈Ch，Then AZI(Lh)≤AZI(Ch)≤AZI(Dh)，where Lhis the linear hexagonal chain with h hexagons and Dh∈Dh.

Proof Since 0 =p(Lh)≤p(Ch)，0 =q(Lh)≤q(Ch)，and AZI(Ch)is monotonously increasing in p(Ch)or q(Ch)in Eq.(2)，then AZI(Lh)≤AZI(Ch).

For any Dh∈Dh，if h is even (respectively odd)，thenFrom Eq.(2)，we have

Since a branched hexagon (respectively kink)of Chcorresponds to a vertex of degree 3 (respectively degree 2)in the dualist graph D(Ch)of Chand note that a vertex of degree 2 in D(Ch)not necessarily corresponding to a kink of Ch，2p(Ch)+3q(Ch)+ (h - p(Ch)- q(Ch))≤2(h -1)，so p(Ch)+ 2q(Ch)≤h -2.It follows thatFrom Eq.(2)，we have

Therefore，Theorem 2 holds.

2 Lower Bound for Augmented Zagreb Index of Molecular Trees with Fixed Numbers of Pendent Vertices

For a molecular tree T with n vertices，denoted by ni，the number of vertices in T with degree i for i=1，2，3，4，and xijthe number of edges of T connecting vertices of degree i and j are denoted，where 1≤i≤j≤4 and n≥3.Then

From Eq.(1)，we have

Let T be a molecular tree of order n with n1pendent vertices.If n1=2，3，4，we can easily check that the minimum AZI index is equal to 8n -8，8n -and 8n -for n≥n1+2，respectively.Next，we consider the case of n1≥5.

Let ETn，n1be the set of molecular trees which satisfies x14=The structures of trees in ETn，n1are complicated (see Ref.［8］).

Theorem 3 Let T be a molecular tree with n vertices，and n1(n1≥5)pendent vertices.Then

with equality if and only if T ∈ETn，n1.

Proof Since T is a molecular tree，Eq.(3)holds.Use the abbreviations as follows

It follows that

This implies that

Thus，

Substituting them back into Eq.(4)，one can get

Note that AZI(T)has positive coefficients for x12，x13，x33，x34，and x44.Thus

with equality if and only if the parameters x12，x13，x33，x34and x44are all equal to zero，or equivalently，x14= n1，x22= n -i.e.，T ∈ETn，n1.

3 A New Proof of a Theorem in Ref.［10］

In this section，by using the convexity of function f(x)=x3，we give a new proof of a known Theorem in Ref.［10］on augmented Zagreb index.Sometimes，this method(using the convexity of function f(x)= x3)can be used to obtain some lower bounds on augmented Zagreb index and it is easier than using graph parameters.

Lemma 1［9］Let f(x，y)=t hen

2)f(2，y)=2 for y≥2.

3)If x≥3 is fixed，then f(x，y)is increasing for y≥2.

Let Φ1be the class of connected graphs whose pendent vertices are adjacent to the maximum degree vertices and all other edges have at least one end-vertex of degree 2.Let Φ2be the class of connected graphs whose vertices are of degree at least two and all the edges have at least one end-vertex of degree 2.Theorem 4［10］Let G be a connected graph of order n≥3 with m edges，p pendent vertices，maximum degree Δ，and minimum non-pendent vertex degree δ1.Then

with equality if and only if G is isomorphic to a regular graph or G is isomorphic to a (1，Δ)-biregular graph or G∈Φ1or G∈Φ2.

Now，we give another proof of theTheorem 4 (the Theorem 2.8 in Ref.［10］).

Proof From Eq.(1)，we have

Since f(x)=x3is a strictly convex function for x ＞0，then

and

Thus，by above inequalities and Lemma 1，we get

and

Combining formulas(6)-(8)，the result of formula(5)is obtained.

Now suppose that equality holds in formula (5).Then all inequalities in the above argument must be equalities.Fromin formula (7)，we get d(v)= Δ for uv ∈E(G)，d(u)= 1.Now consider the following two cases.

Case1.δ1= 2.From formula (8)，we get d(u)= 2，d(v)≥2 for uv∈E(G)，d(u)，d(v)≠1.

If p ＞0，then G∈Φ1.If p =0，then G∈Φ2.

Case2.δ1＞2.From formula (8)，we get d(u)=d(v)=δ1，for uv∈E(G)，d(u)，d(v)≠1.

If p ＞0，since G is connected，then Δ =δ1，that is，G is isomorphic to a (1，Δ)-biregular graph.If p =0，then G is isomorphic to a regular graph.

Conversely，it is easy to see that the equality holds in formula(5)for regular graph or (1，Δ)-biregular graph or Φ1or Φ2.

Hence the Theorem 4 holds.

4 Conclusions

So far，in the field of chemical graph theory，there have been only a few research results about the augmented Zagreb index since its formula is more complicated than most of topological indices.In this paper，we obtained the formula which can be used to compute the augmented Zagreb index of catacondensed hexagonal systems with p kinks and q branched hexagons，and characterized Lhhaving minimal augmented Zagreb index and Dhhaving maximal augmented Zagreb index.We also present the lower bound for augmented Zagreb index of molecular trees with fixed numbers of pendent vertices and characterized the extremal trees.Then by using the convexity of function f(x)=x3，we give a new proof of a known Theorem in Ref.［10］on augmented Zagreb index.Sometimes，this method(using the convexity of function f(x)= x3)can be used to obtain some lower bounds on augmented Zagreb index and it is easier than using graph parameters.

［1］Todeschini R，Consonni V.Handbook of Molecular Descriptors［M］.Weinheim:Wiley-VCH，2000.

［2］Deogun J S，Guo X F，Wei W D，et al.Catacondensed Hexagonal Systems with Smaller Numbers of Kekulé Structures［J］.Journal of Molecular Structure，2003，639(1/2/3):101-108.

［3］Chen J S，Guo X F.Extreme Atom-bond Connectivity Index of Graphs［J］.Match Communications in Mathematical and in Computer Chemistry，2011，658:713-722.

［4］Furtula B，Graovac A，Vukicˇevic＇ D.Augmented Zagreb Index［J］.Journal of Mathematical Chemistry，2010，48(2):370-380.

［5］Hosseini S A，Ahmadi M B，Gutman I.Kragujevac Trees with Minimal Atom-bond Connectivity Index ［J ］.Match Communications in Mathematical and in Computer Chemistry，2014，71:5-20.

［6］Lin W，Gao T，Chen Q，Lin X.On the Minimal ABC Index of Connected Graphs with Given Degree Sequence［J］.Match Communications in Mathematical and in Computer Chemistry，2013，69:571-578.

［7］Dimitrov D.Efficient Computation of Trees with Minimal Atombond Connectivity Index ［J］.Applied Mathematics and Computation，2013，224:663-670.

［8］Xing R D，Zhou B，Du Z B.Further Results on Atom-Bond Connectivity Index of Trees［J］.Discrete Applied Mathematics，2010，158(14):1536-1545.

［9］Huang Y F，Liu B L，Gan L.Augmented Zagreb Index of Connected Graphs［J］.Match Communications in Mathematical and in Computer Chemistry，2012，67:483-494.

［10］Wang D，Huang Y F，Liu B L.Bounds on Augmented Zagreb Index［J］.Match Communications in Mathematical and in Computer Chemistry，2012，68:209-216.

［11］Ali A，Raza Z，Bhatti A A.On the Augmented Zagreb Index［J］.arXiv:1402.3078v1［math.CO］，2014.

［12］Bondy J A，Murty U S R.Graph Theory with Applications［M］.New York:Elsvier，1976.