只有一条最长路的树的Wiener指标

宋梦华

(集美大学理学院，福建 厦门 361021)

0 引言

本文考虑的图都是简单的连通图.令G是一个简单图，以V(G)、E(G)分别表示图G的顶点集和边集．用degG(v)表示图G中v的度，即与v关联的边的个数．以dG(u，v)表示图G中顶点u和v之间的距离，用dG(u)表示图G中其他点与u的距离之和，以diam(G)表示图G的直径．令T1n表示所有只有一条最长路的n阶树的集合．令Tn，d表示所有直径为d的n阶树的集合，令T1n，d表示直径为d且只有一条最长路的n阶树的集合，以K1，n-1和Pn分别表示n个顶点的星和路．在一个树中，度为1点叫做悬挂点．若一个树去掉所有的悬挂点后得到一条路，则该树称为毛毛虫树．用Cd(a1，a2，…，an)表示由路Pn=v1v2…vn给顶点vi添加ai条悬挂边所得到的直径为d的毛毛虫树，其中ai≥0，i=1，2，…，n，n-1≤d≤n+1，显然当a1≠0且an≠0时，d=n+1．毛毛虫树C5(1，3，0，1)(见图1)恰有一条最长路．本文用Ep表示树T中所有悬挂边的集合，用Enp表示树T中所有非悬挂边的集合．

图 1 毛毛虫树 C5(1，3，0，1)Fig.1 Caterpillar C5(1，3，0，1)

图G的Wiener指标定义如下;

这一概念最早由化学家Wiener在文献 [1]中提出，而当G是一棵树T时，文献 [1]也给出了Wie-ner指标的计算公式

其中e取遍树T中所有边，n1(e)和n2(e)分别表示T-e的两个分支的顶点个数．

Wiener指标在理论化学中被广泛应用于描述分子结构．2001年，文献 [2]详细总结了有关树的Wiener指标的性质及结论．自2002年，许多学者给出了一些有特殊条件的树的Wiener指标的结论，例如:对给定匹配数的树的Wiener指标的研究[3]，对给定直径的树的Wiener指标的研究[4-6]，以及限定某些度的条件的树的Wiener指标的极值图[7-10]．

关于树的Wiener指标的一个重要研究方向是对于各类树按其Wiener指标的大小排序，如:文献[11]给出了9阶以上的树的Wiener指标从第一到第十七的最大排序;文献 [12]给出了树的Wiener指标从第一小到第十五小的排序;文献[13]对有完美匹配的树按其最小Wiener指标排出从第一小到第八小的树;文献 [14]对每个点的度都是奇数的树按Wiener指标由小到大进行了排序.

注意到每一个树都至少有一条最长路，这条最长路的长度恰为树的直径，Wiener指标又是以距离度量的.目前对于树的Wiener指标的研究已有比较成熟的结果，然而对于只有一条最长路的树的Wiener指标的研究却非常少．本文主要确定了T1n中Wiener指标从第一小至第五小的树 (见定理1)，这有利于人们了解Wiener指标与只有一条最长路的树的结构之间的关系．

1 若干预备引理

令 Cn，d表示给定一条路 P =y1y2……yd-1，给点 y1，yd-1分别添加一条悬挂边，给y[d/2]添加n-d-1条悬挂边所得到的图 (见图2)，即 Cn，d=Cd(1，0，…，0，n-d-1，0，…，0，1)．文献 [5]给出了直径为d的 n阶树具有最小Wiener指标的图．

图 2 毛毛虫树 Cn，dFig.2 Caterpillar Cn，d

引理1[5]如果 T ∈ Tn，d(2 ≤ d≤ n-1)，那么W(T)≥W(Cn，d)，其中等号成立当且仅当T≅Cn，d．

对于只有一条最长路的树，给出下面几个简明的引理．

引理2 令T∈T1n，其中n≥6．设P=y0y1…ylyl+1是T中唯一一条最长路，那么degT(y1)=degT(yl)=2．

证明 假设y1，yl其中一个度不为2，不失一般性．令degT(yl)≥3，则存在一点x∈V(T)与点yl相邻，但不在路P上．因此P'=y0y1…ylx是T中除P以外的另外一条最长路，与T∈T1n矛盾，故degT(y1)=degT(yl)=2．

引理3 对任意的T∈T1n，5，T 是C5(1，s，t，1)(s≥0，t≥0)这种形式，其中s〉t+1，t〉0，则有W(C5(1，s-1，t+1，1))〉 W(C5(1，s，t，1))．

证明 对任意的T∈T1n，5，由于只有一条最长路，由引理2易知T只能是毛毛虫树，且T是C5(1，s，t，1)(s≥0，t≥0)这种形式．

设e1，e2，e3是如图3所示的树C5(1，s，t，1)中的三条非悬挂边，e'1，e'2，e'3是如图3所示的树C5(1，s-1，t+1，1)中的三条非悬挂边，由式 (2)得:

4(n-2)+(s+2)(t+4)．故 W(C5(1，s-1，t+1，1))-W(C5(1，s，t，1))=s-t-1 ，又因为 s〉t+1，所以有 W(C5(1，s-1，t+1，1))〉 W(C5(1，s，t，1))．

图 3 毛毛虫树 C5(1，s，t，1)和 C5(1，s-1，t+1，1)Fig.3 Caterpillar C5(1，s，t，1)and C5(1，s-1，t+1，1)

引理 4 当 n≥6 时，有 W(Cn，n-2)〉 W(Cn，n-3)〉 … 〉 W(Cn，5)〉 W(Cn，4)．

证明 只需证明W(Cn，d+1)〉W(Cn，d)．令u表示图Cn，d+1中最长路的端点yd+1(如图4)，令v表示图Cn，d中与y[d=2]相邻的某一个悬挂点 (如图4)．显然 Cn，d+1-u与 Cn，d-v同构．由式 (1)得:，所以有

图 4 毛毛虫树 C6(1，0，2，0，1)和 C5(1，3，0，1)Fig.4 Caterpillar C6(1，0，2，0，1)and C5(1，3，0，1)

2 主要结论

定理 1 令 T ∈ T1n{Cn，4，Cn，5，C5(1，n-7，1，1)，C5(1，n-8，2，1)，Cn，6}，其中 n 〉 19，则有W(Cn，4)〈 W(Cn，5)〈 W(C5(1，n-7，1，1))〈 W(C5(1，n-8，2，1))〈 W(Cn，6)〈 W(T)．

证明 首先，找出T1n中Wiener指标最小及第二小的树．令T∈T1n，由引理2知diam(T)≥4，故集合T1n存在以下划分:

由引理2易知集合T1n，4只包含一个树 Cn，4，即

其次，找出T1n中Wiener指标第三小、第四小、第五小的树．对任意的T∈T1n，5，由引理 3 可以对所有d=5的只有一条最长路的n阶树进行排序:W(C5(1，(n-6)/2+1，(n-6)/2-1，1))〉W(C5(1，(n-6)/2+2，(n-6)/2-2，1))〉 … 〉 W(C5(1，n-8，2，1))〉 W(C5(1，n-7，1，1))〉W(Cn，5)，因为 Cn，6是集合中使Wiener指标取最小值的树．由引理4可进一步推知Cn，6也是集合中使Wiener指标最小的树，且W(Cn，6)〉W(Cn，5)．因此要找T1n中Wiener指标第三小、第四小、第五小的树，只需用 Cn，6与 T1n，5中第二小、第三小、第四小的树比较．由式 (2)可得:4)(n-1)+4(n-2)+4(n-4)，由于 W(Cn，6)-W(C5(1，n-7，1，1))=n-1 〉 0 ，所以 C5(1，n-7，1，1)是 T1n中 Wiener指标第三小的树．由于 W(Cn，6)-W(C5(1，n-8，2，1))=8 〉 0 ，所以 C5(1，n-8，2，1)是T1n中 Wiener指标第四小的树．由于 W(Cn，6)-W(C5(1，n-9，3，1))=19-n ，所以当 n 〉19 时，Cn，6是 T1n中 Wiener指标第五小的树．故当 n 〉 19 时，有 W(Cn，4) 〈 W(Cn，5) 〈 W(C5(1，n-7，1，1)) 〈 W(C5(1，n-8，2，1)) 〈W(Cn，6)〈 W(T)．

[1]WIENER H.Structual determination of paraffin boiling points [J].J Amer Chem Soc，1947，69:17-20.

[2]DOBRYNIN A A，ENTRINGER R，GUTMAN I.Wiener index of trees:theory and applications[J].Acta Appl Math，2001，66:211-249.

[3]DU Z，ZHOU B.Minimum Wiener indices of trees and unicyclic graphs of given matching number[J].Match Commun Math Comput Chem，2010，63:101-112.

[4]LIU H，PAN X F.On the Wiener index of trees with fixed diameter[J].Match Commun Math Comput Chem，2008，60:85-94.

[5]WANG S，GUO X.Trees with extremal Wiener indices [J].Match Commun Math Comput Chem，2008，60:609-622.

[6]YOU Z，LIU B.Note on the minimal Wiener index of connected graphs with n vertices and radius r[J].Match Commun Math Comput Chem，2011，66:343-344.

[7]LIN H.Extremal Wiener index of trees with all degrees odd [J].Match Commun Math Comput Chem，2013，70:287-292.

[8]SCHMUCK N S，WAGNER S G，WANG H.Greedy trees，caterpillars，and Wiener-type graph invariants[J].Match Commun Math Comput Chem，2012，68:273-292.

[9]ZHANG X D.The Wiener index of trees with given degree sequences[J].Match Commun Math Comput Chem，2008，60:623-644.

[10]ZHANG X D，LIU Y，HAN M X.Maximum Wiener index of trees with given degree sequence[J].Match Commun Math Comput Chem，2010，64:661-682.

[11]LIU M H，LIU B L，LI Q.Erratum to the trees on n≥9 vertices with the first to seventeenth greatest Wiener indices are chemical trees[J].Match Commun Math Comput Chem，2010，64:743-756.

[12]DONG H，GUO X.Ordering trees by their Wiener indices[J].Match Commun Math Comput Chem，2006，56:527-540.

[13]LIN W，WANG J，XU J.Ordering trees with perfect matchings by their indices[J].Match Commun Math Comput Chem，2012，67:337-345.

[14]FURTULA B，GUTMAN I，LIN H.More trees with all degrees odd having extremal Wiener index [J].Match Commun Math Comput Chem，2013，70:293-296.