樹的度距離排序

摘要：本文討論了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}。……