单圈图的Steiner(n-1)-Wiener指标

来金花，刘蒙蒙

(兰州交通大学 数理学院，兰州 730070)

拓扑指标是从化合物的结构图中衍生出来的一种数学不变量，常常被用来描述有机化合物的药理特征、物理特征以及化学特征.其中Wiener指标和Steinerk-Wiener指标是两个非常重要的拓扑指标.Wiener指标是由化学家Wiener[1]提出来的，作为一个重要的拓扑指标应用于化学研究中，它是研究有机化合物构造性关系的有用工具.大约在1976年，Wiener指标开始应用于数学文献中[2].自此以后，Wiener指标就得到了广泛的关注和研究，参见文献[3-10].作为对经典距离定义的推广，Chartrand等[11]提出了Steiner距离这一概念，2016年Li等[12]用Steiner距离的定义将Wiener指标拓展为Steinerk-Wiener指标.自此国内外专家对Steinerk-Wiener指标问题作了大量的研究.

2016年，Mao等[13]得到了图乘积的Steinerk-Wiener指标的计算式.Li等[12]在2016年确定了一些特殊图类的Steinerk-Wiener指标的计算式及树的Steinerk-Wiener指标的上下界，并给出了树的Steiner (n-1)-Wiener指标的计算式.对于给定直径的树，2018年Lu等[14]给出了Steinerk-Wiener指标的一个紧的下界，并刻画了达到此下界的极图.基于此，本文研究单圈图的Steiner (n-1)-Wiener指标，通过对S中不包含的点分情况讨论给出了单圈图Steiner (n-1)-Wiener指标的计算式，并对单圈图做变换确定单圈图Steiner (n-1)-Wiener指标的上界和下界，进而刻画达到上界和下界的极值图.

1 基本概念

本文中所有图都是简单连通图，定义G是点集为V(G)，边集为E(G)的简单连通图，其中|G|=|V(G)|.对于∀u,v∈V(G),dG(u,v)表示u，v两点之间的距离，即连接u，v最短路的长度.此外用Cn，Pn，Sn分别表示n阶的圈、路和星图.

定义1G的Wiener指标定义表示图G中任意两点的距离之和，即：

(1)

定义2对于S⊆V(G)，点集S的Steiner距离dG(S)表示G中包含点集S的最小连通子树的边数，即：

dG(S)=min{|E(T)|∶T是G的子树,S⊆V(T)}.

(2)

特别地，当S={u,v}时，dG(S)=dG(u,v).因此Steiner距离就是经典距离的一个自然推广.

定义3对于正整数k,2≤k≤n-1,G的Steinerk-Wiener指标SWk(G)表示V(G)中所有k子集S的Steiner距离之和，即：

(3)

当k=2时，Steiner 2-Wiener指标就是Wiener指标.

定义4设G为一个n阶单圈图，其中，圈Cg=v1v2…vgv1,G-E(Cg)的连通分支T1，T2，…，Tg都是树，则单圈图表示为G=Cg(T1,T2,…,Tg)；当非平凡连通分支数为1时记G=Cg(T).

2 单圈图Steiner(n-1)-Wiener指标的计算式

定理2.1设G=Cg(T1,T2,…,Tg)是一个n阶单圈图，|Ti|≥1，i=1,2,…,g.则有

SWn-1(G)=n(n-1)-m-p,

(4)

其中：p为G中悬挂点的个数；m为|Ti|=1的个数.

证明因为|S|=n-1，即去掉G中任意一个点，剩余所有的点都包含在S中.下面分3种情况讨论.

情形1:S中不包含的点是悬挂点.

显然，要把点集S中的点连接为一个边数最小的连通树需要n-2条边，即dG(S)=n-2.此时G中有p个悬挂点，则对SWn-1(G)的贡献为p(n-2).

情形2:S中不包含的点是圈上的点vi且|Ti|=1.

显然，要把点集S中的点连接为一个边数最小的连通树需要n-2条边，即dG(S)=n-2.此时G中|Ti|=1的点有m个，则对SWn-1(G)的贡献为m(n-2).

情形3:其他情况.

要把点集S连接为一个边数最小的连通树，则需要包含G中所有的点，即dG(S)=n-1.这样的点共有n-p-m个，则对SWn-1(G)的贡献为(n-p-m)(n-1).综上所述，可得

SWn-1(G)=p(n-2)+m(n-2)+(n-p-m)(n-1)=n(n-1)+(m+p)(n-2)-(m+p)(n-1)=n(n-1)-m-p.

注意在单圈图阶数给定的情况下，SWn-1(G)的大小只与m和p的大小有关.

引理2.1令G=Cg(T1,T2,…,Tg)是n阶单圈图|Ti|=li，i=1,2,…,g.则

SWn-1(Cg(Sl1,Sl2,…,Slg))≤SWn-1(G)≤SWn-1

(Cg(Pl1,Pl2,…,Plg)),

(5)

当且仅当G≅Cg(Sl1,Sl2,…,Slg)(G≅Cg(Pl1,Pl2,…,Plg))时，左(右)边等号成立.

证明为了方便，令G1=Cg(Sl1,Sl2,…,Slg)，G2=Cg(Pl1,Pl2,…,Plg).由定理2.1知，SWn-1(G)的大小只与p的大小有关.令G1、G2、G中悬挂点的个数分别为p1、p2、p.显然，p1≥p≥p2.则有

SWn-1(G1)≤SWn-1(G)≤SWn-1(G2).

当且仅当G≅G1(G≅G2)时，左(右)边等号成立.

3 单圈图Steiner (n-1)-Wiener指标的下界及其极图

这部分给出n阶单圈图的最小Steiner (n-1)-Wiener指标，并刻画了达到下界时的极图.

引理3.1令G=Cg(Sl1,Sl2,…,Slg)是n阶单圈图，则有

SWn-1(G)≥SWn-1(Cg(Sn-g+1)),

(6)

当且仅当G≅Cg(Sn-g+1)(如图1所示)时等号成立.

证明当g=n时，有G≅Cg(Sn-g+1)，结论显然成立.

当g

SWn-1(G)≥SWn-1(Cg(Sn-g+1)),

当且仅当G≅Cg(Sn-g+1)时等号成立.

图1 图Cg(Sn-g+1)Fig.1 The graph of Cg(Sn-g+1)

当单圈图圈长固定时，由引理2.1，3.1直接可得单圈图的下界.即

定理3.1令G=Cg(T1,T2,…,Tg)是一个n阶单圈图.则有

SWn-1(G)≥SWn-1(Cg(Sn-g+1)),

(7)

当且仅当G≅Cg(Sn-g+1)时等号成立.

引理3.2令Cg(Sn-g+1)是n阶单圈图，g≠n.则有

SWn-1(Cg(Sn-g+1))=SWn-1(Cg-1(Sn-g+2)).

(8)

证明因为g≠n，在Cg(Sn-g+1)，Cg-1(Sn-g+2)中m+p=n-1为定值.则由定理2.1知,

SWn-1(Cg(Sn-g+1))=SWn-1(Cg-1(Sn-g+2))=n(n-1)-(n-1)=(n-1)2.

定理3.2令G=Cg(T1,T2,…,Tg)是一个n阶单圈图.则有

SWn-1(G)≥n(n-2),

(9)

当且仅当G≅Cn时等号成立.

证明当g=n时，m+p=n.则有

SWn-1(G)≥n(n-1)-n=n(n-2),

当且仅当G≅Cn时等号成立.

当3≤g

SWn-1(G)≥SWn-1(Cg(Sn-g+1))=(n-1)2,

当且仅当G≅Cg(Sn-g+1)时等号成立.

显然，(n-1)2>n(n-2).

综上，SWn-1(G)≥n(n-2)，当且仅当G≅Cn时等号成立.

4 单圈图Steiner (n-1)-Wiener指标的上界及其极图

这一部分中给出n阶单圈图的最大Steiner (n-1)-Wiener指标，并刻画了达到上界时的极图.

定理4.1令G=Cg(T1,T2,…,Tg)是n阶单圈图，且|Ti|=li，i=1,2,…,g.当单圈图圈长固定时，则有

SWn-1(G)≤n(n-1)-g,

(10)

当且仅当G≅Cg(Pl1,Pl2,…,Plg)时，等号成立.

证明当单圈图圈长固定且图中的悬挂分支为路时，m+p=g为定值.则由定理2.1，引理2.1知

SWn-1(G)≤n(n-1)-g,

当且仅当G≅Cg(Pl1,Pl2,…,Plg)时，等号成立.

定理4.2设G=Cg(T1,T2,…,Tg)是一个n阶单圈图.则有

SWn-1(G)≤n(n-1)-3,

(11)

当且仅当G≅C3(Pl1,Pl2,Pl3)(如图2所示)时等号成立.

证明由引理2.1，定理4.1知:

SWn-1(G)≤n(n-1)-g≤n(n-1)-3,

当且仅当G≅C3(Pl1,Pl2,Pl3)时等号成立.

图2 具有最大Steiner (n-1)-Wiener指标的单圈图Fig.2 The maximum unicyclic graph of Steiner (n-1)- Wiener index

5 结论

在现有国内外专家对此问题研究的基础上，首先给出了单圈图Steiner (n-1)-Wiener指标的计算式；其次，确定了单圈图Steiner (n-1)-Wiener指标的上、下界，并刻画了达到上、下界时的极图，对下一步研究简单连通图的Steinerk-Wiener指标具有很好的借鉴意义.