樹的度距離排序

摘要：本文討論了n階樹的度距離排序問題，確定了這個序中第五大至第二十大的樹及其相應的度距離。

關鍵詞：圖；度距離；樹；排序

1.引言

圖的度距離是化學圖論中，基于分子圖的定點間距離的拓撲指標，對刻畫分子圖以及建立分子結構與特征間的關系有著重要作用，同時被廣泛用于預測化合物的物理化學性質和生物活性。這類拓撲指標中還有較熟知的Wiener指標。本文是在前人對這類指標研究的基礎上，對圖的度距離做了進一步的研究。

本文將繼續考慮n階樹Tn中的度距離排序問題，利用圖的度距離的定義，借助于圖的變換，給出了Tn中具有第五小至第十三小度距離的樹，并確定了相應的度距離。文獻[5]中證明了路Pn是所有n階簡單連通圖中具有最大度距離的唯一圖。用Tn表示所有n階樹的集合。文獻[4]中研究了Tn中度距離序排序問題，并給出前四個樹。

圖G的度距離的定義是由Dobrynin和Kochetova[1]及Gutman[2]在1994年引入的一種新的拓撲指標，記作D′（G）.設G是一個n階圖，若u，v∈V（G），則u，v間的距離指的是連接u，v的最短路的長度，我們用d（u，v）表示。D′（G）=∑u∈V（G）deg（u）D（u|G）被稱為圖的度距離，其中deg（u）是頂點u在圖G中的度，D（u|G）是頂點u到G中所有頂點的距離之和，即D（u|G）=∑v∈V（G）d（u，v），特別的DG（u|v）表示在圖G中點u到點v的距離。我們用G-v表示在圖G中刪去點v及與它關聯的邊得到的圖，用Tn表示有n個頂點的樹，現對Tn作如下劃分：即Tn=∪n-1i=2Tin，且當i≠j時Tin∩Tjn=.其中Tin表示恰有i條懸掛邊的n階樹的集合，易知星圖K1，n-1為具有最多懸掛邊的唯一樹，懸掛邊數為n-1；路Pn是具有最少懸掛邊的唯一樹，懸掛邊樹為2，即Tn-1n={K1，n-1}，T2n={Pn}。

2.預備知識

參考文獻

[1]A.A.Dobrynin，A.A.Kochtova，Degree distance of a graph：a degree analogue of the wiener idex， J. Chem. Inf. Comput. Sci. vol.34（1994） 1082-1086.

[2]I.Gutman，Selected properties of the Schultz molecular topological index， J. Chem. Inf. Comput. Sci. Vol.34（1994） 1087-1089.

[3]何秀萍. 樹的度距離序[J]. 福州大學學報：自然科學版，2002，30（4）：479-481.

[4]何秀萍，常安.樹的最大度距離排序[J].福州大學學報：自然科學版，2010，38（5）：640-643.

[5]Tomescu I.Some extremal propeeties of the degree distance of a graph[J]. DiscreteAppl Math， 1999， 98： 159-163.