三类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指标间的关系.

BC树；类wiener-1指标；类wiener-2指标；星形BC树；k扩展星形BC树；毛虫BC树

Wiener指标作为一个重要的拓扑指数应用于化学研究中，科学家们发现很多化合物的物理和化学性质与它们的拓扑性质密切相关. wiener指标就是一个与化合物的物理化学性质密切相关的拓扑指数，化学领域对其进行了深入的研究，随后数学家也开始关注这一指标，并给予了许多数学方面的解释和研究[1-7].

Harary 和 Plummer在文献[8]中研究图的核的过程中首先提出了BC树的概念，T是一颗BC树，当且仅当它二可染色且任意两片叶子具有相同的颜色. Entringer[9]和Lovasz[10]等证明了所有n顶点的树中，星形树K1,n−1(是唯一)的wiener指标最小，路径树nP(是唯一)的wiener指标最大. 本文提出了类Wiener-1指标和类Wiener-2指标的概念，并研究它在BC树上的一些性质.

下面给出一些定义. 树 T=(V, E)为连通无环简单图，记顶点度为1的点为叶子，记连接T上的任2个顶点vi到vj的路径为 pT(vi, vj)，vi和vj之间的距离 dT(vi, vj)就是连接vi和vj的路径 pT(vi, vj)的边的个数. 对于T的一个顶点v，定义顶点v的距离为即顶点v到T的其它所有顶点的距为T的wiener指标，即任2个无序顶点对之间的距离和；定义顶点v的类wiener-1距离为定义顶点v的类wiener-2距离为 gWiener−2,T(v)=离和，定义树T的类wiener-1指标为任两个无序的距离为偶数的顶点对间的距离和，简记为定义树T的类wiener-2指标为任两个无序的距离为奇数的顶点对间的距离和，简记为

1 BC树的类Wiener-1指标与类Wiener-2指标的关系

前面定义了类wiener-1指标、类wiener-1距离、类wiener-2指标和类wiener-2距离，下面给出这些图参数在BC树上的相应性质.

定理1[9-10]所有n顶点树中，星形树K1,n−1(是唯一)的wiener指标最小，其值为 (n−1)2；路径树 Pn(唯一的)的wiener指标最大，其值为 (n3−n) 6.

定理2 设T为任意一个n顶点的BC树，则 σWiener−2(T )≤ σWiener−1(T).

证明：对于BC树T，总能找到一个分裂点v，使得每次在v分裂后的两棵树都为BC树，且其中一个为星形BC树，直到最后得到的两棵BC树都为星形BC树为止.

设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). 假设对于顶点个数小于n的BC树定理成立，下面证明顶点数为n时定理也成立.

由分析知，T的偶(奇)距离顶点对由4部分构成：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树不能达到此最小值.

设x为任一n顶点BC树T的一片叶子，v为其邻居顶点，如果其它所有的顶点距离叶子顶点x的距离为2(如果有距离大于2的顶点存在则会出现距离为3的顶点对)，则它们必须是v的邻居，因此T只能是星形BC树.

由定理4(下文将给出证明)可知，n顶点的偶扩星形BC树也能达到这个最大值，因此它不是唯一的. 2.2 k扩星形BC树类Wiener-1指标与类Wiener-2指标的性质

如果一棵树是由星形树K1,n−1出发，每条边都为再往外延伸k倍的距离而形成的，则称这样的树为n-1个分支的k扩星形树，记为 Kk；把顶点度为n-1的那个顶点定义为根节点，把距离根节点的距离定义为

1,n−1该顶点的层数，由此可知，当k=1时即为星形树.

定理4 设T为n-1(n≥4)个分支的k扩星形BC树，当k为偶数时则σWiener~1(T) =σWiener~2(T)，当k为奇数时，则 σ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为偶数时，将n-1(n≥4)个分支的k扩星形BC树按下列方法进行分裂：

任选一条从叶节点到根节点的路径，按从叶节点到根节点的方向依次选取长为2的路径，k为偶数时第一次分裂后的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指标的差相同.

继续上面的过程，直到把从叶节点到根节点的这条路径删完，设此时的BC树为T0，很显然：

再对其余的从叶节点到根节点的路径做同样的操作，直到将T分裂成一个2个分支的偶扩星形BC树为止；记2个分支的偶扩星形BC树为则而路径BC树的类wiener-1指标与类wiener-2指标相同，即成立.

当k为奇数时，依照上面的分裂方法，同样由式(1)可知第一次分裂后有：

直到把T变成这样一颗n-1个分支的BC树(有一个叶子在第一层，其余n-2个叶子在第k层). 记此时的BC树为T1， 如图2所示，则可得：

然后再对T1重复上面的过程，直至将T变为一个星形BC树K1,n−1，此时有：

图1 k (k为偶)扩星形BC树分裂

图2 k (k为奇)扩星形BC树分裂

2.3 毛虫星形BC树类Wiener-1指标与类Wiener-2指标的性质

如果树T有一条路径，使得T的每个顶点如果不在该路径上，则一定与路径上的某个顶点相邻，则称此树为毛虫树; 若T是一棵BC树，且T同时也是一棵毛虫树，则称T为一棵毛虫BC树，图3是一棵直径长度为l的毛虫BC树.

图3 直径长度为l的毛虫BC树

定理5 设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 设毛虫BC树T的结构同图3，如果各部分的叶子数满足第i部分与第部分的叶子数的和保持不变(i=1,2…l4)，(l=4k时); 第i部分与第部分的叶子数的和保持不变(i=1,2…(l−2)4)，且第(l+2)4部分的叶子数目保持不变(l=4k+2时)，则类wiener-2指标的值保持不变.

证明：按定理5中毛虫BC树分裂的方式来计算它的类wiener-2指标，可得毛虫BC树的类wiener-2指标为：

若l=4k，则式(3)为：

即：

若l=4k+2，则：

本文提出了类wiener-1指标和类wiener-2指标的概念，并得到了其在一般BC树及三类特殊BC树上比较好的特殊性质，由于树的形态很多，类wiener指标在特殊树或一般树上是否具有特殊的性质及该指标在化学领域的特性值得进一步探讨.

[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] 牛志勇. 关于图的Wiener指标若干问题的研究[D]. 上海: 上海交通大学, 2007.

[7] 杜永军. 关于Wiener指标的研究[D]. 西安: 西北工业大学, 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— ), 男, 河南南阳人, 平顶山学院国际教育交流学院助教.