給定直徑圖的第1類Zagreb指數的上界及極圖

劉中柱

（惠州學院 數學與大數據學院,廣東 惠州 516007）

給定直徑圖的第1類Zagreb指數的上界及極圖

劉中柱

（惠州學院 數學與大數據學院,廣東 惠州 516007）

令圖G是具有n個頂點、直徑為d的簡單連通圖.本文根據Ore的方法，給出了G的第1類Zagreb指數的上界，并刻畫了極圖.

Zagreb指數；簡單圖；直徑

1 基本知識介紹

令G=(V,E)是簡單連通圖，其中V,E分別是G的點集與邊集，且 ||V=n, ||E=m.圖G第1類和第2類Zagreb指數分別定義為

其中d(v)表示頂點v的度.

Zagreb指數是由Gutman和Trinajsti?[1]提出的經典圖論拓撲指數，在分子設計、分子復雜性、能量等方面得到廣泛應用，它反映了分子骨架的分支數.Zagreb拓撲指數的數學性質在文獻[2-3]中有相關研究.有關Zagreb指數的進展及更多的研究背景可參考文獻[4-9]。鄧漢元[10]給出了樹、單圈圖與雙圈圖的Zagreb指數的結果；李樹超[11]給出了給定直徑的二部圖的第2類Zagreb指數的界并刻畫了極圖；最近關于Zagreb指數的結果參考文獻[12-16].

令G(n,d)為具有n個頂點，直徑為d≥2的簡單連通圖.d(u,v)表示頂點u和v間的距離，G[E]表示邊集E在原圖G中的邊生成子圖，NG(v)表示點v在圖G中的鄰接點集，表示點集V1與V2間的邊的集合，E(V1,V2)表示端點分別在點集V1和V2間的邊的集合.令Kn是n個頂點的完全圖，Kn-e是在Kn中刪去一邊得到的圖，聯(lián)接1條懸掛邊到Kn-1-e中度為n-2的點上，得到的圖記為Kn,3,它是頂點數為n、直徑長為3的圖.令P=v0v1…vd是長為d的路，在頂點vi,vi+1,vi+2與Kn-d-1中所有的頂點連邊得到一系列圖，記為圖類Gn,d,其中1≤i≤d-3.

本文根據Ore[17]的方法與技巧，得到G(n,d)中第1類Zagreb指數的上界，并刻畫了極圖.

2 主要結論

引理1 令a≥a0≥a1≥…≥ad為非負整數，且當且僅當a0=a1=a2=a,且ai=0,3≤i≤d時等號成立.

從而存在另一個d+1元非負整數集π′={ } a0,…,ak-2,ak-1+1,ak-1,0,…,0,使得 f(π′)>f(π),與假設矛盾等式成立時當且僅當a0=a1=a2=a,且ai=0,3≤i≤d.

根據文獻[17]，可以得到定理1.

定理1 令G∈G(n,d),其中n≥4,從而有

1)當d=2,M1(G)≤(n2-3)(n-2),當且僅當G=Kn-e時等號成立；

2)當d=3,M1(G)=n3-5n2+6n+2,當且僅當G=Kn,3時等號成立；

證 令G∈G(n,d).令P=v0v1…vd為圖G的直徑路，Z=V-V(P).

當d≥3時，2≤x0+xd≤n-d-1;

當d=2時，有M1≤(n2-3)(n-2),當且僅當G=Kn-e,x0=xd=n-3時等號成立；

當d=3時，有M1=n3-5n2+6n+2,當且僅當G=Kn,3,x0=n-4,xd=0或x0=0,xd=n-4時等號成立；

參考文獻:

[1] GUTMAN I,TRINAJSTIC N.Graph theory and molecular orbitals,Totalφ-electron energy of alternant hydrocarbons[J].Chem Phys Lett,1972(17):535-538.

[2] GUTMAN I,JAMIL M K,AKHTER N.Graphs with fixed number of pendent vertices and minimal first Zagreb index[J].Trans Comb,2015(4):43-48.

[3] GUTMAN I,RUSCIC B,Trinajstiic N,et al.Graph theory and molecular orbitals XII Acyclic polyenes[J].J Chem Phys,1975,62: 3 399-3 405.

[4]HANSEN P,VUK?CEVI?C D.Comparing Zagreb indices[J].Croat ChemActa,2007,80:165-168.

[5]VUK?CEVI?C D.Comparing variable Zagreb indices[J].MATCH Commun Math Comput Chem,2007,57:633-641.

[6] VUK?CEVI?C D,GRAOVAC A.Comparing ZagrebM1andM2indices for acyclic molecules[J].MATCH Commun Math Comput Chem,2007,57:587-590.

[7]ZHOU B.Zagreb indices[J].MATCH Commun Math Comput Chem,2004,52:113-118.

[8]ZHOU B,STEVANOVIC'D.Anote on Zagreb indices[J].MATCH Commun Math Comput Chem,2006,56:571-578.

[9] ZHOU B,TRINAJSTIC N.Some properties of the reformulated Zagreb index[J].J Math Chem,2010,48:714-719.

[10] DENG H.A unified approach to the extremal Zagreb indices for trees,unicyclic graphs and bicyclic graphs[J].MATCH Commun Math Comput Chem,2007,57:597-616.

[11] LI S,ZHANG M.Sharp upper bounds for Zagreb indices of bipartite graphs with a given diameter[J].Applied Math Lett,2011, 24:131-137.

[12] NIKOLI?C S,KOV?CEVI?C G,MILI?CEVI CA,et al.The Zagreb indices 30 years after[J].Croat ChemActa,2003,76:113-124.

[13] BIANCHI M,CORNARO A,PALACIOS J L,et al.New bounds of degree-based topological indices for some classes of c-cyclic graphs[J].DiscrAppl Math,2015,194:62-75.

[14] ANIN B B.On the extremal Zagreb indices of trees with given number of segments or given number of branching vertices[J]. MATCH Commun Math Comput Chem,2015,74:57-79.

[15] CHEN S,LIU S.Tricyclic graphs with minimum modified Schultz index and maximum Zagreb indices[J].Ars Comb,2015,122: 379-397.

[16] WANG J F,BELARDO F.A lower bound for the first Zagreb index and its application[J].MATCH Commun Math Comput Chem,2015,74:35-56.

[17] ORE O.Diameters in Graphs[J].Journal of Combinatorial Theory,1968(5):75-81.

The Upper Bound of the First Zagreb Index of Graphs with Given Diameter

LIU Zhongzhu

（Shool of Mathematics and Big Data Science,Huizhou University,Huizhou,Guangdong 516007,China）

LetGbe the graph withnvertices and diameterd.The idea of O.Orea(1986)is applied to investigate the upper bound of the first Zagreb index ofGand then characterize the extreme graph.

:Zagreb index；simple graph；diameter

O157.5

A

1009-8445（2017）02-0012-03

（責任編輯:陳 靜）

2016-12-19

惠州市科學技術創(chuàng)新基金資助項目(2014B020004027)；廣東省杰出青年教師基金資助項目(YQ2015155)；國家社會科學基金資助項目(15BTJ024）

劉中柱(1982-）,男,廣東河源人,惠州學院數學與大數據學院講師,博士.