毛虫树的Harary指数

欧阳庚旭

(上海电机学院 文理教学部，上海 201306)

设图G=(V,E)是一个简单无向连通图，其中V(G)和E(G)分别是图G的顶点集和边集.当连通图G满足|E(G)|=|V(G)|+1时，称G是树，记为T.顶点v的度指的是与v相邻的顶点的数目，记为d(v).度为1的顶点称为悬挂点，与悬挂点相邻的边称为悬挂边. 顶点u,v之间的距离指的是u与v之间最短路所含边的数目，记为d(u,v).图G中任意两顶点距离的最大值称为图的直径，记为dG,简记为d.n阶路和星图分别记为Pn,Sn.文中未给出的定义和记号参见文献[1].

1 固定直径的毛虫树的Harary指数的极值图

图1 毛虫树

假设H1,H2是两个连通图，记H1vH2是一个新的图，且满足

V(H1vH2)=V(H1)∪V(H2)，

有

E(H1vH2)=E(H1)∪E(H2)，V(H1)∩V(H2)={v}.

引理1[6]假设H是一个连通图，Tl是一个n阶树，且

V(H)∩V(Tl)={v}，

则

H(HvTl)≤H(HvSl)，

其中：HvSl是由H和星图Sl的中心在顶点连接v而成的图，等号成立当且仅当Tl≅Sl.

引理3[7]假设图G是一个非平凡的连通图，且v∈V(G)，Gk,l记为图G在顶点v处添加两条长分别为k和l的路Pk=vv1v2…vk，Pl=vu1u2…ul而得到的图G，若k≥l≥1，则

H(Gk,l)>H(Gk+1,l-1).

定理1对于任意阶数为n、直径为d的非毛虫树T，则一定存在毛虫树

使得

H(T′)>H(T).

证明假设u,v是非毛虫树T中距离最大的两个顶点，则

d(u,v)=d，

d(u)=d(v)=1，

且在顶点u,v之间存在唯一路P,记P=ux1x2…,xd-1v，对于路P中的任意顶点xi，1≤i≤d-1,不妨设在T中与xi相接的树的阶数为ni+1，在xi处将ni+1阶树替换为Sni+1.由引理1可知，图的Harary指数将变大，不断重复上述过程，直到非毛虫树T变成毛虫树

有

H(T′)>H(T).

时成立.

证明首先证明主路只有一个顶点的度大于2.反之，则存在ni>0,nj>0,1≤i,j≤d-1.由引理2可知，将vi的ni个悬挂边往vj上移或者将vj的nj个悬挂边往vi上移得到新的树的Harary指数将变大，不断重复上述过程，最终可得主路只有一个顶点度大于2的毛虫树.

2 似双星树的Harary指数的极值图

图2 似双星树T(p,d,q)

引理4[8-10]假设T是任意一个n阶树，有

左边等号当且仅当T≅Pn时成立，右边等号当且仅当T≅Sn时成立.

引理5对任意的整数对(n,d)，其中d≥2,n≥d+1，有

证明根据图的Harary指数的定义和引理4，将树T(p,d,q)的顶点分成3部分：第一部分顶点{x1}的p个悬挂点、第二部分顶点xd-1的q个悬挂点、第三部分路Pd-1上的d-1个顶点，有

引理6当树T(p,d,q)的阶数n和直径d固定时，有

H(T(p,d,q))≤H(T(p-1,d,q+1)).

证明由引理5可得

等号当且仅当d=2，即T(p,d,q)≅Sn时成立.

由引理5直接计算可得

引理7当树T(1,d,n-d)的阶数n固定时，有

H(T(1,d,n-d))≤H(T(1,d-1,n+1-d)).

证明由上面的公式计算得

等号当且仅当d=2，即T(p,d,q)≅Sn时成立.

由引理6、定理3和引理7，可得定理4.

定理4T(1,2,n-2)≅Sn是树T(p,d,q)中取得最大Harary指数的极图，T(1,n-1,1)≅Pn是树T(p,d,q)中取得最小Harary指数的极图.