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

劉中柱

（惠州學(xué)院 數(shù)學(xué)與大數(shù)據(jù)學(xué)院,廣東 惠州 516007）

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

劉中柱

（惠州學(xué)院 數(shù)學(xué)與大數(shù)據(jù)學(xué)院,廣東 惠州 516007）

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

Zagreb指數(shù)；簡單圖；直徑

1 基本知識介紹

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

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

Zagreb指數(shù)是由Gutman和Trinajsti?[1]提出的經(jīng)典圖論拓?fù)渲笖?shù)，在分子設(shè)計、分子復(fù)雜性、能量等方面得到廣泛應(yīng)用，它反映了分子骨架的分支數(shù).Zagreb拓?fù)渲笖?shù)的數(shù)學(xué)性質(zhì)在文獻(xiàn)[2-3]中有相關(guān)研究.有關(guān)Zagreb指數(shù)的進展及更多的研究背景可參考文獻(xiàn)[4-9]。鄧漢元[10]給出了樹、單圈圖與雙圈圖的Zagreb指數(shù)的結(jié)果；李樹超[11]給出了給定直徑的二部圖的第2類Zagreb指數(shù)的界并刻畫了極圖；最近關(guān)于Zagreb指數(shù)的結(jié)果參考文獻(xiàn)[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,它是頂點數(shù)為n、直徑長為3的圖.令P=v0v1…vd是長為d的路，在頂點vi,vi+1,vi+2與Kn-d-1中所有的頂點連邊得到一系列圖，記為圖類Gn,d,其中1≤i≤d-3.

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

2 主要結(jié)論

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

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

根據(jù)文獻(xiàn)[17]，可以得到定理1.

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

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

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

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

當(dāng)d≥3時，2≤x0+xd≤n-d-1;

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

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

參考文獻(xiàn):

[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

（責(zé)任編輯:陳 靜）

2016-12-19

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

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