具有完美匹配树图的外围维纳指标的上（下）界

发布时间：2021-04-15 08:03

　　设T为具有n个顶点的树图,树图T的外围维纳指标为T中所有外围顶点对之间的距离之和,即PW （T）=■d （u, v）,其中P（T）为树图的所有外围顶点构成的集合.本文分别给出了具有完美匹配的树图的外围维纳指标的上界和下界,以及外围顶点数给定的具有完美匹配的树图的外围维纳指标的上界和下界. 

【文章来源】：闽南师范大学学报(自然科学版). 2020,33(03)

【文章页数】：6 页

【部分图文】：

引理2证明的示意图Fig.1AgraphinLemma2wd（v）-1

v1v2v3v4v5图4T3的示意图Fig.4T3diagram第3期雷思宇：具有完美匹配树图的外围维纳指标的上（下）界2.2完美匹配树图的外围维纳指标的上（下）界文献[3]证明了树图的外围维纳指标的上（下）界，下面先给出具有完美匹配的树图的外围维纳指标的下界.定理4若G∈T(2m,m)，m≥2，则1)若m≥2时，PW(G)≥3，等号成立当且仅当GP3；2)若m≥3时，PW(G)≥4，等号成立当且仅当GT3.证明1）因为m≥2，所以至少有两条边，即d(G)≥2.若d(G)=2，则GSn，由引理2可得，任意悬挂点的关联顶点的度应为2，故此时Sn=P2，但是显然P2不具有完美匹配，故矛盾，所以d(G)≥3.根据引理3，有PW(G)≥d(G)≥3.下面讨论等号成立的情况.PW(G)=3时，一定有d(G)=3，因为若d(G)≥4，则由引理3知PW(G)≥d(G)≥4，矛盾；若d(G)=2，则GSn，而由引理1可知PW(Sn)=(n-1)(n-2)，这时不存在顶点数n使得Sn的外围维纳指标为3，矛盾.因为d(G)=3，根据引理2直径路径两侧的悬挂点所关联的顶点的度应为2，所以此时有GP3，其匹配数m=2.即等号成立当且仅当GP3.得证.2）图T3见图4.因为m≥3，则d(G)≥2.若d(G)=2，同1）中的证明可知，矛盾，故d(G)≥3.若d(G)=3，由1）中等号成立条件证明可知，GP3,m=2，矛盾.故d(G)≥4，所以由引理3有PW(G)≥d(G)≥4.下面讨论等号成立的情况.

，不存在顶点数n使得Sn的外围维纳指标为4，矛盾.因为d(G)=4，所以会存在一条直径，其顶点从左往右编号分别为v1v2v3v4v5，根据引理2，顶点v2,v4其度一定为2，若存在完美匹配，悬挂边会在完美匹配中，则还有顶点v3没被匹配，此时若在顶点v3上添加长度大于或等于2的路径，则P(||G)≥3，有PW(G)>4，故顶点v3上只能添加1条悬挂边，此时匹配数m=3.即等号成立当且仅当GT3.得证.2m-2kk—2k—2图3T2的示意图Fig.3T2diagram图2T1的示意图Fig.2T1diagramk-135


本文编号：3138953