固定直徑樹的距離平方和問題

趙紅錦，耿顯亞

(安徽理工大學 數學與大數據學院，安徽 淮南 231001)

固定直徑樹的距離平方和問題

趙紅錦，耿顯亞*

(安徽理工大學 數學與大數據學院，安徽 淮南 231001)

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

樹；懸掛點；直徑

1947年Harold Wiener引入了第一個化學指標（現稱為Wiener指標）并發表了一系列的文章力證了有機化合物分子圖的Wiener指標與分子化合物的一系列物理化學指標間有著密切聯系。文中的圖均為樹圖，與樹的Wiener指標相關文章見文獻[1-6]。近來許多學者將研究目標放在尋找具有最小和第二小指標值所對應的圖上，并取得了一些成果見文獻[1,7,8]，且在Wiener指標之后引入了一個新指標S(G)，其定義如下：

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

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

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

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

1 引理

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

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

通過引理1，可得以下結論。

推論1 圖G的任意兩點v,u分別連接s,t個懸掛點的圖Gs,t見圖1，那么

圖1 圖Gs,t示意圖

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

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

當且僅當HvTl?HvK1,l-1時等號成立，HvK1,l-1中頂點v為K1,l-1的中心。

引理3G是n頂點圖，v是G的一個懸掛點，u是與v相鄰的頂點，那么

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

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

證明 利用引理3，可得

引理5 如果P=v0v1v2…vd是一條長度為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)。

證明 依據D和L的定義，有

2 結論

該部分給出集類Tn,d(3≤d≤n-2)中最小和第二小的S(G)所對應的的樹。為更好地闡述結論，需定義如下一些樹，如圖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上任一點vi(1≤i≤d-1)連接pi個懸掛點所得n頂點樹，且。

定義

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

Tn-1,d,i的一個懸掛點（v0,vd除外）上連接一個懸掛點到得到Xn,d,i，Tn+2,d,i的一個懸掛點（v0,vd除外）上連接n-d-2個懸掛點到得到Yn,d,i，那么，Xn,d,i=Xn,d,d-i，Yn,d,i=Yn,d,d-i。

定義

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

注意到類似的不等式對于Xn,d,i和Yn,d,i同樣成立。因此，當，有，當有。

通過引理6，可得以下結論。

引理7 假設3≤d≤n-3,那么

證明 由引理3,得

通過引理5，可得，當且僅當

因此，(i)式成立。

由引理5，知

故由引理3，得

因此，(ii)成立。

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

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

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

通過事實1，2，3，引理得證。

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

由于n≥d+3，Vd≠?。考慮如下兩種情況。

情況1 |Vd|≥2。

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

情況2 |Vd|=1。

在這種情況下，假設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)的子樹且包含xj，。由引理2，通過連接sj個懸掛點到xj(1≤j≤s)可由Td+s+1,d,i得到樹T3，且S(T)≥S(T3)。通過推論1，可得樹使得S(T3)≥S(T4)。如果，那么由引理7可得。如果，那么由引理7可得。

通過引理6，7和9，可得以下結果。

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

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

3 小結

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

[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

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

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

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