趙紅錦，耿顯亞

(安徽理工大學(xué) 數(shù)學(xué)與大數(shù)據(jù)學(xué)院，安徽 淮南 231001)

固定直徑樹(shù)的距離平方和問(wèn)題

趙紅錦，耿顯亞*

(安徽理工大學(xué) 數(shù)學(xué)與大數(shù)據(jù)學(xué)院，安徽 淮南 231001)

定義圖G中所有點(diǎn)對(duì)間的距離的平方和為，其中dG(u,v)為圖G中任意頂點(diǎn)u,v之間的距離，LG(v)表示圖G中點(diǎn)v到其它點(diǎn)的距離的平方和。在所有直徑為d的n頂點(diǎn)樹(shù)中分別確定使S(G)最小和第二小的樹(shù)。

樹(shù)；懸掛點(diǎn)；直徑

1947年Harold Wiener引入了第一個(gè)化學(xué)指標(biāo)（現(xiàn)稱(chēng)為Wiener指標(biāo)）并發(fā)表了一系列的文章力證了有機(jī)化合物分子圖的Wiener指標(biāo)與分子化合物的一系列物理化學(xué)指標(biāo)間有著密切聯(lián)系。文中的圖均為樹(shù)圖，與樹(shù)的Wiener指標(biāo)相關(guān)文章見(jiàn)文獻(xiàn)[1-6]。近來(lái)許多學(xué)者將研究目標(biāo)放在尋找具有最小和第二小指標(biāo)值所對(duì)應(yīng)的圖上，并取得了一些成果見(jiàn)文獻(xiàn)[1,7,8]，且在Wiener指標(biāo)之后引入了一個(gè)新指標(biāo)S(G)，其定義如下：

令S=S(G)為圖G中所有點(diǎn)對(duì)間距離的平方和，表示為

其中dG(u,v)為圖G中任意頂點(diǎn)u,v之間的距離；LG(v)表示圖G中點(diǎn)v到其它所有點(diǎn)的距離的平方和。該量是由Mustapha Aouchich和Pierre Hansen在[9]中引入并在專(zhuān)論中得以廣泛研究。S(G)被用于距離譜半徑的研究，Zhou和Trinajsti?利用階數(shù)n證明了距離平方和S(G)的上界，見(jiàn)[10-12]；并在只使用S(G)的情況下確定了圖的距離譜半徑的下界。作為它的延續(xù)，該文中確定在集合Tn,d(3≤d≤n-3)中使S(G)最小所對(duì)應(yīng)的樹(shù)。

文中所有的圖都是簡(jiǎn)單且有限的。G=(VG,EG)表示頂點(diǎn)集為VG邊集為EG的圖。G-v,G-uv分別表示刪除圖G中點(diǎn)v以及點(diǎn)v所關(guān)聯(lián)的邊和刪除邊uv(uv∈EG)所得到的圖。類(lèi)似地，G+uv表示在圖G上添加邊uv(uv?EG)，其中u,v∈VG。圖G中與點(diǎn)v相鄰的所有頂點(diǎn)的個(gè)數(shù)稱(chēng)為頂點(diǎn)v的度，表示為d(v)。懸掛點(diǎn)是度為1的頂點(diǎn)。頂點(diǎn)u,v之間的距離d(u,v)為連接頂點(diǎn)u,v之間最短路的邊數(shù)。圖G中任意兩頂點(diǎn)之間距離的最大值為G的直徑，記為d。距離DG(v（)v∈V(G)）即為v到其它頂點(diǎn)的所有距離和，而LG(v)為v到其它頂點(diǎn)的所有距離的平方和。文中未定義的符號(hào)和術(shù)語(yǔ)參見(jiàn)[13]。

樹(shù)是連通的無(wú)圈圖，令T是直徑為d的n個(gè)頂點(diǎn)樹(shù)。如果d=n-1，那么T?Pn，即n頂點(diǎn)路；如果d=2，那么T?K1,n-1，即n頂點(diǎn)星圖。因此，在以下內(nèi)容中，假設(shè)3≤d≤n-2。令Tn,d={T:T為直徑為d的n頂點(diǎn)樹(shù)，3≤d≤n-2}。

1 引理

首先給出在結(jié)果證明中可能用到的引理。

引理1[14]令H,X,Y是三個(gè)連通的，成對(duì)的不相交圖。假設(shè)u,v是H的兩個(gè)頂點(diǎn)，u′,v′分別是X,Y的一個(gè)頂點(diǎn)。分別連接v和v′、u和u′得到圖G，連接v，v′，u′得到圖，連接u，v′，u′得到圖，那么S()＜S(G)或S()＜S(G)。

通過(guò)引理1，可得以下結(jié)論。

推論1 圖G的任意兩點(diǎn)v,u分別連接s,t個(gè)懸掛點(diǎn)的圖Gs,t見(jiàn)圖1，那么

圖1 圖Gs,t示意圖

令H1，H2是兩個(gè)連通圖，V(H1)?V(H2)={v}，H1vH2是滿(mǎn)足條件V(G)=V(H1)?V(H2)，V(H1)?V(H2)={v}和E(G)=E(H1)?E(H2)的圖。通過(guò)S(G)的定義可得以下結(jié)論。

引理2H為連通圖，Tl是l個(gè)頂點(diǎn)的樹(shù)且V(H)?V(Tl)={v}。那么S(HvTl)≥S(HvK1,l-1)

當(dāng)且僅當(dāng)HvTl?HvK1,l-1時(shí)等號(hào)成立，HvK1,l-1中頂點(diǎn)v為K1,l-1的中心。

引理3G是n頂點(diǎn)圖，v是G的一個(gè)懸掛點(diǎn)，u是與v相鄰的頂點(diǎn)，那么

證明 由S(G)的定義，有

引理4G是連通的非平凡圖，v是G中任一頂點(diǎn)。將兩條長(zhǎng)度分別為k,m(k≥m≥1)的路P=vv1v2…vk和Q=vu1u2…um的末端頂點(diǎn)連接到點(diǎn)v，可得，那么。

證明 利用引理3，可得

引理5 如果P=v0v1v2…vd是一條長(zhǎng)度為d的路，那么

其中，1≤j≤d-1。此外，若1≤i＜j≤d/2，則DP(vi)＞DP(vj),LP(vi)＞LP(vj)；若d/2≤i＜j≤d-1，則DP(vi)＜DP(vj),LP(vi)＜LP(vj)。

證明 依據(jù)D和L的定義，有

2 結(jié)論

該部分給出集類(lèi)Tn,d(3≤d≤n-2)中最小和第二小的S(G)所對(duì)應(yīng)的的樹(shù)。為更好地闡述結(jié)論，需定義如下一些樹(shù)，如圖2。

圖 2 Zn,d,i,j、Tn,d,i、Yn,d,i、Xn,d,i示意圖

Tn,d(p1,…,pd-1) 表示路Pd+1=v0v1…vd-1vd上任一點(diǎn)vi(1≤i≤d-1)連接pi個(gè)懸掛點(diǎn)所得n頂點(diǎn)樹(shù)，且。

定義

那么Tn,d,i=Tn,d,d-i。

Tn-1,d,i的一個(gè)懸掛點(diǎn)（v0,vd除外）上連接一個(gè)懸掛點(diǎn)到得到Xn,d,i，Tn+2,d,i的一個(gè)懸掛點(diǎn)（v0,vd除外）上連接n-d-2個(gè)懸掛點(diǎn)到得到Y(jié)n,d,i，那么，Xn,d,i=Xn,d,d-i，Yn,d,i=Yn,d,d-i。

定義

證明 只需證明j=i-1的情況。依據(jù)引理4取v=vi，兩條路分別為P=v0v1…vi,…vd，Q=vivi+1…vd，即可得以上結(jié)果。

注意到類(lèi)似的不等式對(duì)于Xn,d,i和Yn,d,i同樣成立。因此，當(dāng)，有，當(dāng)有。

通過(guò)引理6，可得以下結(jié)論。

引理7 假設(shè)3≤d≤n-3,那么

證明 由引理3,得

通過(guò)引理5，可得，當(dāng)且僅當(dāng)

因此，(i)式成立。

由引理5，知

故由引理3，得

因此，(ii)成立。

證明 令T=Zn,d,i,j，P=v0v1…vd-1vd是一條長(zhǎng)為d的路，d(v0)=d(vd)=1，且vd+1是T中與vj相鄰的一個(gè)懸掛點(diǎn)，所選T是使S(T)最小的樹(shù)。首先給出以下事實(shí)。

證明 注意到Zn,d,i,j-vd+1?Tn-1,d,i。如果，那么由引理3和5得

證明 注意到Zn,d,i,j-vd+1?Tn-1,d,i。如果，那么由引理3和6，可知

通過(guò)事實(shí)1，2，3，引理得證。

證明 令Pd+1=v0v1…vd-1vd是T中長(zhǎng)為d的路且d(v0)=d(vd)=1，

由于n≥d+3，Vd≠??？紤]如下兩種情況。

情況1 |Vd|≥2。

這種情況下，首先得到使S(T)≥S(T1)的樹(shù)T1，T1?Tn,d(p1,…,pd-1)，由引理2知當(dāng)且僅當(dāng)T?T1時(shí)等號(hào)成立。又T?Tn0,d，存在pi,pj≠0,1≤i＜j≤d-1。故由推論1可得樹(shù)T2?Zn,d,i,j使得S(T1)＞S(T2)，又由引理8，可得

情況2 |Vd|=1。

在這種情況下，假設(shè)vi∈Vd，N(vi){vi-1,vi+1}={x1,…,xs}，其中d(xj)≥2,1≤j≤r，且d(xr+1)=…=d(xs)=1，那么r≥1。令Ti(xj)是Ti(vi)的子樹(shù)且包含xj，。由引理2，通過(guò)連接sj個(gè)懸掛點(diǎn)到xj(1≤j≤s)可由Td+s+1,d,i得到樹(shù)T3，且S(T)≥S(T3)。通過(guò)推論1，可得樹(shù)使得S(T3)≥S(T4)。如果，那么由引理7可得。如果，那么由引理7可得。

通過(guò)引理6，7和9，可得以下結(jié)果。

定理1 (i)集合Tn,d(3≤d≤n-2)中使S(G)最小的樹(shù)為；

(ii)集合Tn,d(3≤d≤n-3)中使S(G)第二小的樹(shù)為。

3 小結(jié)

文章將固定直徑d(3≤d≤n-3)的樹(shù)劃分為四種圖類(lèi)，利用指標(biāo)S(G）的定義和圖類(lèi)間的轉(zhuǎn)化關(guān)系，最終得出在固定直徑的樹(shù)中使S(G）最小和第二小的分別對(duì)應(yīng)的樹(shù)。今后可研究在該條件下使指標(biāo)S(G)第三小時(shí)是否有唯一的樹(shù)存在。

[1]Dobrynin A A,Entringer R,Gutman I.Wiener index of trees：theory and applications[J].Acta Applicandae Mathematicae,2001,66(3)：211-249.

[2]Li S C,Song Y B.On the sum of all distances in bipartite graphs[J].Discrete Applied Mathematics,2014,169(22)：176-185.

[3]Liu M H,Liu B L.On the variable Wiener indices of trees with given maximum degree[J].Mathematical and Computer Modelling,2010,52(9/10)：1651-1659.

[4]Dobrynin A A,Gutman I,Klav?ar S,et al.Wiener index of hexagonal systems[J].Acta Applicandae Mathematica,2002,72(3)：247-294.

[5]Fischermann M,Gutman I,Hoffmann A,et al.Extremal chemical trees[J].Zeitschrift Fur Naturforschung Section A-a Journal of Physical Sciences,2002,57(1/2)：49-52.

[6]Gutman I,Potgieter J H.Wiener index and intermolecular forces[J].Journal of Serbian Chemical Society,1997,62：185-192.

[7]Ashrafi A R,Yousefi S.Computing the wiener index of a TUC 4 C 8(S)nanotorus[J].Match Communications in Mathematical&in Computer Chemistry,2007,57(2)：403-410.

[8]Deng H Y.The trees on n≥9 vertices with the first to seventeenth greatest Wiener indices are chemical trees[J].Match Communications in Mathematical&in Computer Chemistry,2007,57(2)：393-402.

[9]Aouchiche M,Hansen P.Distance spectra of graphs：A survey[J].Linear Algebra and Its Applications,2014,458(2)：301-386.

[10]Zhou B,Trinajsti? N.Mathematical properties of molecular descriptors based on distances[J].Croatica ChemicaActa,2010,83(2)：227-242.

[11]Zhou B,Trinajstic N.On the largest eigenvalue of the distance matrix of a connected graph[J].Chemical Physics Letters,2007,447(4/6)：384-387.

[12]Zhou B,Trinajstic N.Further results on the largest eigenvalues of the distance matrix and some distance based matrices of connected(molecular)graphs[J].Internet Electronic Journal of Molecular Design,2007,6(12)：375-384.

[13]Bondy J A,Murty U S R.Graph Theory with Applications[M].Macmillan,1976：237-238.

[14]Liu H Q,Lu M.A unified approach to extremal cacti for different indices[J].MATCH-Communications in Mathematical and in Computer Chemistry,2007,58(1)：183-194.

Sum of the squares of all distances in a tree with fixed diameter

ZHAO Hong-jin,GENG Xian-ya*
(School of Mathematics and Big Data,Anhui University of Science and Technology,Huainan Anhui232001,China)

Denote the sum of the squares of all distances between all pairs of vertices inGbywheredG(u,v)is the distance betweenuandvinGand the sum goes over all the pairs of vertices,LG(v)denotes the sum of the squares of all distances fromuinG.The trees with minimum and second-minimumS(G)among all the trees withnvertices and diameterdare obtained respectively.

tree;pendant vertex;diameter

O157.5

A

1004-4329（2017）03-005-05

10.14096/j.cnki.cn34-1069/n/1004-4329（2017）03-005-05

2017-03-17

國(guó)家自然科學(xué)基金（11401008,61672001）；中國(guó)博士后科學(xué)基金（2016M592030)資助。

趙紅錦（1990- ），女，碩士生，研究方向：圖論及其應(yīng)用。

耿顯亞（1981- ），男，博士，副教授，研究方向：代數(shù)圖論及其應(yīng)用。Email：gengxianya@sina.com。