江玲瑤,湯自凱

(湖南師范大學(xué) 數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院,湖南 長(zhǎng)沙,410081)

給定分支點(diǎn)數(shù)目樹(shù)的離心率總和

江玲瑤,湯自凱

(湖南師范大學(xué) 數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院,湖南 長(zhǎng)沙,410081)

設(shè)G=(V,E)是簡(jiǎn)單連通圖,簡(jiǎn)單連通圖G的離心率總和定義為圖G中所有頂點(diǎn)的離心率總和。若樹(shù)T中某個(gè)頂點(diǎn)的度大于等于 3,則稱(chēng)這個(gè)點(diǎn)為T(mén)的分支點(diǎn)?？坍?huà)了給定分支點(diǎn)數(shù)為r頂點(diǎn)數(shù)為n的樹(shù)的離心率總和的上界和下界。

離心率總和;分支點(diǎn);樹(shù);極值圖

ζ指數(shù)是用來(lái)描述分子結(jié)構(gòu)特征的最經(jīng)典的拓?fù)渲笖?shù)之一,它在物理化學(xué)建模[1?5]和生物研究[6?8]中都有很多應(yīng)用。Dankelmann等[9]介紹了一個(gè)基于距離的拓?fù)渲笖?shù),這個(gè)指數(shù)被稱(chēng)為離心率的總和,它的定義是

若樹(shù)T中某個(gè)頂點(diǎn)的度大于等于3,則稱(chēng)這個(gè)點(diǎn)為T(mén)的分支點(diǎn)。當(dāng)樹(shù)至少有一個(gè)分支點(diǎn)和至多有r≤n/2? 1個(gè)分支點(diǎn)時(shí),樹(shù)的特征是不一樣的。林洪[10]研究了分支點(diǎn)數(shù)目對(duì) Wiener指數(shù)的影響,刻畫(huà)了n個(gè)頂點(diǎn)r個(gè)分支點(diǎn)樹(shù)的Wiener指數(shù)的上界和下界。因此，本文將刻畫(huà)分支點(diǎn)數(shù)目是怎樣影響離心率總和及n個(gè)頂點(diǎn)r個(gè)分支點(diǎn)樹(shù)的離心率總和的上界和下界。

1 術(shù)語(yǔ)和符號(hào)說(shuō)明

設(shè)G=(V,E)是簡(jiǎn)單連通圖,V(G)和E(G)分別為圖G的頂點(diǎn)集與邊集,記為圖G的階或記為n,為圖G的邊數(shù)或記為(或d(v))為頂點(diǎn)v在圖中G的度,對(duì)于u,v∈V(G),在G中頂點(diǎn)u,v之間的最短路的長(zhǎng)度稱(chēng)為這兩個(gè)點(diǎn)的距離d(u,v),點(diǎn)v到其他頂點(diǎn)最大的距離為v的離心率ε(v)。若一個(gè)點(diǎn)的度為1,則稱(chēng)這個(gè)點(diǎn)為懸掛點(diǎn),如果點(diǎn)v0為懸掛點(diǎn),則路為G中一條懸掛路,其中內(nèi)部頂點(diǎn)的度為2,vk的度至少為3。設(shè)Sn,Pn為n個(gè)頂點(diǎn)的星圖和路。對(duì)于其他的專(zhuān)業(yè)術(shù)語(yǔ)和符號(hào)均參考文獻(xiàn)[11]。

2 主要結(jié)論

引理1 設(shè)u為圖G0(至少有2個(gè)頂點(diǎn))中的1個(gè)頂點(diǎn)。對(duì)整數(shù)a≥1,將Sa+1的中心和u連接得到G1。將u連接a+1個(gè)懸掛點(diǎn)得到G2,則

圖1 引理1的圖

引理 2 設(shè)w為非平凡連通圖G的一頂點(diǎn),對(duì)于非負(fù)整數(shù)p和q。設(shè)為由G中頂點(diǎn)w連接長(zhǎng)度為p和q的懸掛路和如果則

由引理1和引理2易得如下結(jié)論。

圖2 引理2的圖

定理1 在n個(gè)頂點(diǎn)的樹(shù)中,Sn的離心率總和最小,nP的離心率總和最大。接下來(lái),給出給定分支點(diǎn)數(shù)目的n個(gè)頂點(diǎn)樹(shù)的離心率總和的上界和下界。

設(shè)ΒΤn,r為n個(gè)頂點(diǎn)r個(gè)分支點(diǎn)的樹(shù)的集合。F(n,r)和B(n,r)如圖3所示。顯然,

圖3F(n,r)和B(n,r)

圖4 定理2證明(2)的圖

[1]Arezoomand M,Taeri B.Applications of generalized hierarchical product of graphs in computing the Szeged index of chemical graphs [J].MATCH Commun Math Comput Chem,2010,64:591?602.

[2]De N.Augmented eccentric connectivity index of some thorn graphs [J].Int J Appl Math Res,2012,1(4):671?680.

[3]Eliasi M,Taeri B.Four new sums of graphs and their Wiener indices [J].Discret Appl Math,2009,157:794?803.

[4]Eskender B,Vumar E.Eccentric connectivity index and eccentric distance sum of some graph operations [J].Trans Comb,2013,2(1):103?111.

[5]Fathalikhani K,Faramarzi H,Youse-Azari H.Total eccentricity of some graph oper-ations [J].Electron Notes Discret Math,2014,45:125?131.

[6]Gutman I.Distance in thorny graph [J].Publ Inst Math,1998,63:31?36.

[7]Metsidik M,Zhang W,Duan F.Hyper and reverse Wiener indices of F-sums of graphs [J].Discret Appl Math,2010,158:1 433?1 440.

[8]Tang Y,Zhou B.On average eccentricity.MATCH Commun [J].Math Comput Chem,2012,67:405?423.

[9]Dankelmann P,Goddard W,Swart C S.The average eccentricity of a graph and its Subgraphs [J].Util Math,2004,65:41?51.

[10]Lin H.On the Wiener index of trees with given number of branching vertices [J].MATCH Commun Math Comput Chem,2014,72(1):301?310.

[11]Bondy J A,Murty U S R.Graph theory with applications [M].London:Macmillan,1976.

(責(zé)任編校:劉曉霞)

On the total eccentricity of trees with given number of branching vertices

Jiang Lingyao,Tang Zikai
(College of Mathematics and Computer Science,Hunan Normal University,Changsha 410081,China)

LetG=(V,E)be a simple connected graph,the total eccentricity of a simple and connected graphGis defined as the sum of eccentricities of all vertices inG.Avertex of a treeTwith 3 or greater is called a branching vertex ofT.That the upper bound and the lower bound of the total eccentricity of an n-vertex tree with r branching vertices are determined.

the total eccentricity;the branching vertex;tree;extremal graph

O 157.5

A

1672-6146(2017)02-0005-04

湯自凱,zikaitang@163.com。

2016?11?10

項(xiàng)目資助:湖南師范大學(xué)優(yōu)秀青年項(xiàng)目(ET13101)。

10.3969/j.issn.1672-6146.2017.02.002