橄榄树距离和及平均距离的求解

卢永红，刘宏英

(山西大同大学数学与计算机科学学院，山西大同 037009）

橄榄树距离和及平均距离的求解

卢永红，刘宏英

(山西大同大学数学与计算机科学学院，山西大同 037009）

树是图论中一个极其有趣且重要的研究课题，有着较好的应用价值和广阔的研究前景，由于其本身的多样性，使得研究者们纷纷沉醉其中.本文求出了一类树——橄榄树的距离和及平均距离.

橄榄树 距离和 平均距离

1 预备知识

W（G）和W（G）作为图的重要参数，在结构化学[2]、建筑学[3]、通讯网络等领域都有重要应用，在理论研究方面亦有丰硕的研究成果，可参看文献[4-9].

定义1 设T是以v为根的树，若T在v的分支分别是T1，T2，…，Tk，其中Ti是长为i的路 (i＝1，2，…，k)，则称T是一棵橄榄树(olive tree).在v的分支数为n的橄榄树记为OT（n）.OT（4）见图1.

定义2 一个图的顶点集V若能分为两个非空子集X和Y，使X∪Y＝V，X∩Y＝Ø，且G的每条边的两个端点分居在X和Y中，则称此图为二分图.对于简单二分图G=(X,Y;E)，若对任意xi∈X, yj∈Y,有(xi,yi)∈E，则称G为完备二分图.若，这样的完备二分图记作Km,n.

定义3 K1,n称为星(star).星S7见图2.

图2 星S7

图1 橄榄树OT(4)

在本文中主要计算橄榄树OT(n)的距离和及平均距离.

2 主要结果

定理:橄榄树OT(n)的距离和为

3 证明

求距离为i(i=1,2,…,n-2)的点对数ni，两点在同一分支的点对数为1+2+…+(n-i+1)，两点在不同分支的点对数为(n-i+2)[1+2+…+(i-2)]+(i-1)，此二项之和为

上式中和号上下标[]为取整符号，下同.

求距离为n的点对数，

[1]Bondy JA，Murty U SR.Graph Theory with Applications[M].London:Macmillan Press，1976.

[2]Wiener H.Structural determination of paraffin boiling points[J].Amer Chem Soc，1947，69(2):17-20.

[3]Doyle JK.Mean distance in a graph[J].Discrete Math，1977，17(2):147-154.

[4]Chung FR K.The average distance and the independence number[J].Journal of Graph theory，1988，12(5):229-235.

[5]卢永红，杨爱民，管宏生.均匀θ-图边距离和的求解[J].山西大同大学学报:自然科学版，2009，25(4):5-9.

[6]王仲梅，孟献青，王世英.(mg+1，m f)-图的(g，f)-因子分解[J].山西大同大学学报:自然科学版，2009，25(5):4－5.

[7]闫瑞华，许三星.圈长为3的k圈图laplacian矩阵谱的界[J].山西大同大学学报:自然科学版，2007，23(2):11－13.

[8]李秀兰，王振义.图的谱半径的上界[J].山西大同大学学报:自然科学版，2007，23(1):3－4.

[9]刘小兰，许三星.与k4-e有关的一类图的邻点可区别全染色[J].山西大同大学学报:自然科学版，2009，25(1):13－15.

The Solution of the Sum of All Distances and Average Distance on Olive Trees

LU Yong-hong，LIU Hong-ying
(School of Mathematical and Computer Sciences，Shanxi Datong University，Datong Shanxi，037009)

As an important direction of graph theory，the research on tree has been a great active branch according to its application，It has remarkable theoretic and applied value.And because of itsmultiple and flexibilitymany researchers have fall in it.This paper has calculated the sum of all distances and average distance on olive trees.

olive tree;the sum of distance;average distance

O157.5

A

〔编辑 高海〕

1674－0874（2010）02－0015－03

2010-01-08

卢永红(1977-)，女，山西朔州人，硕士，讲师，研究方向:图论及其应用.