三類BC樹的類Wiener指標

楊 雨 ，王文虎，趙 勇

(1.平頂山學院 國際教育交流學院，河南 平頂山 116026；2.平頂山學院 軟件學院，河南 平頂山116026；3.北京航空航天大學 航空科學與工程學院，北京100191)

三類BC樹的類Wiener指標

楊 雨1，王文虎2，趙 勇3

(1.平頂山學院 國際教育交流學院，河南 平頂山 116026；2.平頂山學院 軟件學院，河南 平頂山116026；3.北京航空航天大學 航空科學與工程學院，北京100191)

所有n頂點樹中，星形樹wiener指標最小，路徑樹nP的wiener指標最大；提出了類wiener-1指標和類wiener-2指標的概念，證明了對任一棵BC樹的類wiener-1指標大于等于它的類wiener-2 指標；并給出了星形BC樹，k擴展星形BC樹和毛蟲BC樹的類wiener-1指標和類wiener-2指標間的關(guān)系.

BC樹；類wiener-1指標；類wiener-2指標；星形BC樹；k擴展星形BC樹；毛蟲BC樹

Wiener指標作為一個重要的拓撲指數(shù)應(yīng)用于化學研究中，科學家們發(fā)現(xiàn)很多化合物的物理和化學性質(zhì)與它們的拓撲性質(zhì)密切相關(guān). wiener指標就是一個與化合物的物理化學性質(zhì)密切相關(guān)的拓撲指數(shù)，化學領(lǐng)域?qū)ζ溥M行了深入的研究，隨后數(shù)學家也開始關(guān)注這一指標，并給予了許多數(shù)學方面的解釋和研究[1-7].

Harary 和 Plummer在文獻[8]中研究圖的核的過程中首先提出了BC樹的概念，T是一顆BC樹，當且僅當它二可染色且任意兩片葉子具有相同的顏色. Entringer[9]和Lovasz[10]等證明了所有n頂點的樹中，星形樹K1,n?1(是唯一)的wiener指標最小，路徑樹nP(是唯一)的wiener指標最大. 本文提出了類Wiener-1指標和類Wiener-2指標的概念，并研究它在BC樹上的一些性質(zhì).

下面給出一些定義. 樹 T=(V, E)為連通無環(huán)簡單圖，記頂點度為1的點為葉子，記連接T上的任2個頂點vi到vj的路徑為 pT(vi, vj)，vi和vj之間的距離 dT(vi, vj)就是連接vi和vj的路徑 pT(vi, vj)的邊的個數(shù). 對于T的一個頂點v，定義頂點v的距離為即頂點v到T的其它所有頂點的距為T的wiener指標，即任2個無序頂點對之間的距離和；定義頂點v的類wiener-1距離為定義頂點v的類wiener-2距離為 gWiener?2,T(v)=離和，定義樹T的類wiener-1指標為任兩個無序的距離為偶數(shù)的頂點對間的距離和，簡記為定義樹T的類wiener-2指標為任兩個無序的距離為奇數(shù)的頂點對間的距離和，簡記為

1 BC樹的類Wiener-1指標與類Wiener-2指標的關(guān)系

前面定義了類wiener-1指標、類wiener-1距離、類wiener-2指標和類wiener-2距離，下面給出這些圖參數(shù)在BC樹上的相應(yīng)性質(zhì).

定理1[9-10]所有n頂點樹中，星形樹K1,n?1(是唯一)的wiener指標最小，其值為 (n?1)2；路徑樹 Pn(唯一的)的wiener指標最大，其值為 (n3?n) 6.

定理2 設(shè)T為任意一個n頂點的BC樹，則 σWiener?2(T )≤ σWiener?1(T).

證明：對于BC樹T，總能找到一個分裂點v，使得每次在v分裂后的兩棵樹都為BC樹，且其中一個為星形BC樹，直到最后得到的兩棵BC樹都為星形BC樹為止.

設(shè)T′為含p+2(p≥1)個頂點的星形BC樹，記：

因為T′是BC樹，顯然N1≥N2， gWiener?2,T′(v)≤ gWiener?1,T′(v). 又因為BC樹T中的任2個頂點對要么都在T′中，要么都在T′中，要么一個在T′中一個在T′中.

下面對n進行歸納證明. n=3, 4, 5時的BC樹顯然都滿足 σWiener?2(T )≤σWiener?1(T). 假設(shè)對于頂點個數(shù)小于n的BC樹定理成立，下面證明頂點數(shù)為n時定理也成立.

由分析知，T的偶(奇)距離頂點對由4部分構(gòu)成：T′中的偶(奇)距離頂點對、T′中的偶(奇)距離頂點對、T′中含v的偶距離頂點對與T′中含v的偶(奇)距離頂點對組合而成的偶(奇)距離頂點對、T′中含v的奇距離頂點對與T′中含v的奇(偶)距離頂點對組合而成的偶(奇)距離頂點對.

因此，T的由BC樹T′和T′兩部分組合且含頂點v的偶距離無序頂點對的距離和為：

T的由BC樹T′和T′兩部分組合且含頂點v的奇距離無序頂點對的距離和為：

所以

定理得證.

2 三類BC樹的類Wiener-1指標和類Wiener-2指標的特性

2.1 星形和路徑BC樹的類Wiener指標

定理3 所有n頂點BC樹中，星形BC樹K1,n?1的類wiener-2指標最小，其值為n-1；類wiener-2指標的最大值為 (n3?n )12，路徑BC樹Pn?1能達到這個最大值，但不是唯一的BC樹.

證明：n頂點樹有n-1條邊，所以任意一棵n頂點BC樹的類wiener-2指標大于等于n-1，而星形BC樹K1,n?1的類wiener-2指標為n-1，故星形BC樹K1,n?1的類wiener-2指標最小. 下面證明其它n頂點BC樹不能達到此最小值.

設(shè)x為任一n頂點BC樹T的一片葉子，v為其鄰居頂點，如果其它所有的頂點距離葉子頂點x的距離為2(如果有距離大于2的頂點存在則會出現(xiàn)距離為3的頂點對)，則它們必須是v的鄰居，因此T只能是星形BC樹.

由定理4(下文將給出證明)可知，n頂點的偶擴星形BC樹也能達到這個最大值，因此它不是唯一的. 2.2 k擴星形BC樹類Wiener-1指標與類Wiener-2指標的性質(zhì)

如果一棵樹是由星形樹K1,n?1出發(fā)，每條邊都為再往外延伸k倍的距離而形成的，則稱這樣的樹為n-1個分支的k擴星形樹，記為 Kk；把頂點度為n-1的那個頂點定義為根節(jié)點，把距離根節(jié)點的距離定義為

1,n?1該頂點的層數(shù)，由此可知，當k=1時即為星形樹.

定理4 設(shè)T為n-1(n≥4)個分支的k擴星形BC樹，當k為偶數(shù)時則σWiener~1(T) =σWiener~2(T)，當k為奇數(shù)時，則 σWiener?2(T) < σWiener?1(T )≠且σWiener?1(T ) = σWiener?2(T)+(k +1)(n ?1)(n ? 3)2.

證明： 2個分支的k擴星形BC樹，為一條路徑BC樹，而路徑BC樹的類wiener-1指標與類wiener-2指標是相等的，故限定n≥4.

當k為偶數(shù)時，將n-1(n≥4)個分支的k擴星形BC樹按下列方法進行分裂：

任選一條從葉節(jié)點到根節(jié)點的路徑，按從葉節(jié)點到根節(jié)點的方向依次選取長為2的路徑，k為偶數(shù)時第一次分裂后的T′和T′，如圖1所示，可知σWiener?2(T ′) = σWiener?1(T ′)，p=1且 N1=N2，此處符號p, N1,N2的定義與定理2中相同，故由定理2中式(1)可知 σWiener?2(T) ? σWiener?1(T) = σWiener?2(T′) ? σWiener?1(T′)，即T的類wiener-1指標與類wiener-2指標的差與T′的類wiener-1指標與類wiener-2指標的差相同.

繼續(xù)上面的過程，直到把從葉節(jié)點到根節(jié)點的這條路徑刪完，設(shè)此時的BC樹為T0，很顯然：

再對其余的從葉節(jié)點到根節(jié)點的路徑做同樣的操作，直到將T分裂成一個2個分支的偶擴星形BC樹為止；記2個分支的偶擴星形BC樹為則而路徑BC樹的類wiener-1指標與類wiener-2指標相同，即成立.

當k為奇數(shù)時，依照上面的分裂方法，同樣由式(1)可知第一次分裂后有：

直到把T變成這樣一顆n-1個分支的BC樹(有一個葉子在第一層，其余n-2個葉子在第k層). 記此時的BC樹為T1， 如圖2所示，則可得：

然后再對T1重復上面的過程，直至將T變?yōu)橐粋€星形BC樹K1,n?1，此時有：

圖1 k (k為偶)擴星形BC樹分裂

圖2 k (k為奇)擴星形BC樹分裂

2.3 毛蟲星形BC樹類Wiener-1指標與類Wiener-2指標的性質(zhì)

如果樹T有一條路徑，使得T的每個頂點如果不在該路徑上，則一定與路徑上的某個頂點相鄰，則稱此樹為毛蟲樹; 若T是一棵BC樹，且T同時也是一棵毛蟲樹，則稱T為一棵毛蟲BC樹，圖3是一棵直徑長度為l的毛蟲BC樹.

圖3 直徑長度為l的毛蟲BC樹

定理5 設(shè)T是一棵直徑長度為l的毛蟲BC樹，則σWiener?1(T) >σWiener?2(T )，且

證明：將毛蟲BC樹T按從左到右的順序進行分裂，只需分裂(l?2)2次即可，每次分裂后的p值為pi=ni? 2(i=1,2…(l?2)2)， 因為T為毛蟲BC樹，故每次分裂出來的兩部分中的一部分Ti′為星形BC樹 K1,ni?1(i=1,2…(l?2)2)，另一部分Ti′(i=1,2…(l?2)2)仍然為毛蟲BC樹，每次的分裂點記為vi

定理6 設(shè)毛蟲BC樹T的結(jié)構(gòu)同圖3，如果各部分的葉子數(shù)滿足第i部分與第部分的葉子數(shù)的和保持不變(i=1,2…l4)，(l=4k時); 第i部分與第部分的葉子數(shù)的和保持不變(i=1,2…(l?2)4)，且第(l+2)4部分的葉子數(shù)目保持不變(l=4k+2時)，則類wiener-2指標的值保持不變.

證明：按定理5中毛蟲BC樹分裂的方式來計算它的類wiener-2指標，可得毛蟲BC樹的類wiener-2指標為：

若l=4k，則式(3)為：

即：

若l=4k+2，則：

本文提出了類wiener-1指標和類wiener-2指標的概念，并得到了其在一般BC樹及三類特殊BC樹上比較好的特殊性質(zhì)，由于樹的形態(tài)很多，類wiener指標在特殊樹或一般樹上是否具有特殊的性質(zhì)及該指標在化學領(lǐng)域的特性值得進一步探討.

[1] WAGNER S G. A class of trees and its Wiener index[J]. Acta Appl Math, 2006 (91): 119-132.

[2] LUKOBITS I. A note on a formula for the hyper-Wiener index of some trees[J]. Computers chem, 1999, 19(1): 27-31.

[3] LI XINHUA, LI ZUGUANG, HU MAOLIN. A novel set of Wiener indices [J]. Journal of molecular graphics and modeling, 2003 (22): 161-172.

[4] WANGHUA, YU GUANG. All but 49 Numbersare Wiener Indices of Trees[J]. Acta.Appl.Math, 2006 (92): 15-20.

[5] BEREG S, WANG HAO. Wiener indices of balanced binary trees[J]. Discrete Applied Mathematics, 2007 (155): 457-467.

[6] 牛志勇. 關(guān)于圖的Wiener指標若干問題的研究[D]. 上海: 上海交通大學, 2007.

[7] 杜永軍. 關(guān)于Wiener指標的研究[D]. 西安: 西北工業(yè)大學, 2007.

[8] HARARY, PLUMMER F, M.D. On the core of a graph[J]. Proc. London Math. Soc.(3). 1967(17): 305-314.

[9] ENTRINGER R C, JACKSON D E, SNYDER D A. Distance in graphs[J]. Czechoslovak Math, 1976, 26(101): 283-296.

[10] LOVASZ L. Combinatorial Problems and Exercises[M]. second ed. Amsterdam: Notth-Holland, 1993.

(責任編輯：陳 丹)

Properties of Similar Wiener Index of Three Types of BC-tree

YANG Yu1, WANG Wen-hu2, ZHAO Yong3
(1.College of International Education & Exchange, Pingdingshan University, Pingdingshan 467000,China; 2.College of Software, Pingdingshan University, Pingdingshan 467000, China; 3. Schoolof Aeronautics Science & Engineering, Beijing university of Aeronautics and Astronautics, Beijing 100191, China)

The wiener index is maximized by star tree and minimized by path tree on n vertices trees. In this paper, we give out the concepts of similar wiener-1 index and similar wiener-2 index, and also prove out the similar wiener-1 index of BC-tree is not smaller than its similar wiener-2 index; meanwhile, we give out the relationship between similar wiener-1 index and similar wiener-2 index of star-BC-tree, k-extended star BC-tree and caterpillar-BC-tree.

BC Tree; Similar wiener-1 index; Similar wiener-2 index; Star-BC-tree; K-extended star BC-tree; Aterpillar-BC-tree

O157.5

A

1009-2854(2011)05-0019-06

2011-04-08;

2011-04-26

楊 雨(1983— ), 男, 河南南陽人, 平頂山學院國際教育交流學院助教.