恰有2个圈的双圈图的覆盖花费极小值

潘向峰

(安徽大学数学科学学院，安徽 合肥 230601)

陈海波

(长沙市岳麓实验中学，湖南 长沙 410208)

卢健

(安徽大学数学科学学院，安徽 合肥 230601)

只考虑简单连通图G=(VG,EG)，其中G的顶点集为VG={u1,u2,…,un},边集为EG={e1,e2,…,em}。若2个顶点相邻，则用符合～表示。设NG(x)={u:u～x,u∈VG}为图G当中顶点x的邻点集，顶点x的度为dG(x)=|NG(x)|。当dG(u)=1时，称顶点u是一个悬挂点。图G中顶点x和y之间的距离为2个顶点间最短路的长度，记为dG(x,y)。若图G为简单连通图，且有|EG|=|VG|+1，则称图G为双圈图。为了方便，在不会造成混淆时，一般会省略定义中的下标G。

Wiener指数是基于距离提出的一个拓扑指数，定义为所有点对之间距离的和，即：

1 基本概念

若x∈VG,令G-x表示图G删去顶点x和所有与x相邻的边后得到的新图。类似地，若X⊆EG，令G-X表示图G删去集合X中所有的边后得到的新图。记Cn,Pn和Sn分别为顶点数为n的圈，路和星图，星图Sn为一个中心点为u，余下的顶点皆为与u相邻的悬挂点组成的图。

图1 恰有2个圈的双圈图及极图

为了计算的简洁，笔者引用如下类似D(x)和Dw(x)的定义:

引理1[1]设G是一个简单连通图，x是G的一个割点，a和b是删除点x后分属2个连通分支的顶点，则有：

rG(a,b)=rG(a,x)+rG(x,b)

引理2 设T是一个以vi为根点，顶点个数为n的树，则对任意一点x∈V(T)及k≥0,取x距离根点vi更近的邻点x′,有：

DT(x)-(n+k)dT(x,vi)

证明 设T-x包含根点vi的部分共有k1个点，不含根点vi的部分共有k2个点，显然有k1+k2+1=n。则由定义有：

DT(x′)-(n+k)dT(x′,vi)=DT(x)-k1+k2-(n+k)(dT(x,vi)-1)

=DT(x)-(n+k)dT(x,vi)+n+k-k1+k2

>DT(x)-(n+k)dT(x,vi)

引理3[24]设G是一个连通图，v是其一个割点。G1和G2是G以v为公共点的2个子图，且G1∪G2=G。设n1=|VG1|,n2=|VG2|,则：

Kf(G)=Kf(G1)+Kf(G2)+(n1-1)RG2(v)+(n2-1)RG1(v)

图2 顶点v的σ-变换

定义1[7]设v为图G中一个度为p+1的顶点，vv1,vv2,…,vvp都是与v相邻的悬挂边，u是v的与顶点v1,v2,…,vp都不相同的邻点。删除边vv1,vv2,…,vvp并且添上新的边vv1,vv2,…,vvp构造一个新图G′=σ(G，v)，则称图G′是由图G通过σ-变换得来的(如图2)。

引理4 设G是一个顶点数为n≥6的简单连通图，G′=σ(G，v)是由图G经过σ-变换得到的，u是图G的一个割点，H是包含顶点u的子图(如图2)。则对x∈VH，有：

RG′(x)≤RG(x)Kf(G′)≤Kf(G)

证明 由定义，有：

显然RG′(x)≤RG(x)，等号成立当且仅当p=0。不失一般性，设|VH|=n1,则由引理3，有：

Kf(G)=Kf(H)+Kf(Tu)+(n1-1)Kfu(Tu)+(p+1)Kfu(H)

=Kf(H)+(p+1)Kfu(H)+2n1p+n1+p2

=Kf(H)+(p+1)Kfu(H)+n1p+n1+p2+p

于是：

Kf(G)-Kf(G′)-(n1-1)p≥0

引理5 设G是一个顶点数为n≥6的简单连通图，G′=σ(G,v)是由图G经过σ-变换得到的，u是图G的一个割点，如图2。设x∈{v1,v2,…,vp}，则当p≥1时，有：

证明 不失一般性，设|H|=n1。类似引理4的证明，由定义有：

Kf(G)=Kf(H)+(p+1)Kfu(H)+2n1p+n1+p2

同时有DTu(u)=1+2p,故可得：

+4n1+4n1p+2p2+6p+1-4n

(1)

同理：

Kf(G′)=Kf(H)+(p+1)Kfu(H)+(n1+1)p+n1+p2

+3n1+2n1p+2p2+6p+2-2n

(2)

又n1+p+1=n，由式(1)减去(2)有：

Δ=n1(2p-1)-2p-3

经过简单计算可知，当n1≥3,n=n1+p+1≥6时，Δ>0，从而引理5得证。

图3 β-变换

定义2[7]设u,v是图G的2个顶点，u1,u2,…,us是与u相邻的悬挂点，v1,v2,…,vt是与v相邻的悬挂点。图G′和图G″是2个由图G通过β-变换得到的图，具体为G′=G-{vv1,vv2,…,vvt}+{uv1,uv2,…,uvt},G″=G-{uv1,uv2,…,uvs}+{vv1,vv2,…,vvs}(如图3)。

引理6 设G′，G″是由图G经过β-变换得到的，G0是G的一个子图(如图3)。则对x∈VG0,有RG′≤RG(x)或RG″(x)≤RG(x)，且有Kf(G′)≤Kf(G)或Kf(G″)≤Kf(G)。

证明 由定义，有：

同样，可得：

若RG(x)-RG′(x)=tr(x,v)-tr(x,u)<0,则RG(x)-RG″(x)=s(r(x,u)-r(x,v))>0。用类似的方法可得，若Kf(G′)>Kf(G),则Kf(G″)≤Kf(G)

引理7[25]设G是一个简单连通图，边数为m。则对x,y∈VG,有：

引理8[26]设T是一个边数为m的树，则对x∈VT,有Dw(x)=2D(x)-m。

2 主要结果

2.1 首达时间和覆盖花费与图不变量之间的关系

结论1 设G是属于B(p,l,q)中的一个双圈图，x是圈Cp,Cq或路Pl上的一点，则：

Rw(x)=2R(x)+r(x,u)+r(x,v)-(n-p-q-l+2)

证明 通过对顶点个数n用数学归纳法来证明。当n=p+q+l-2时，双圈图G中除了顶点u,v的度为3，其余顶点的度都为2。因此：

一方面，通过引理1有：

另一方面：

结合可得：

=2RG(x)+r(x,u)+r(x,v)-(n-p-q-l+2)

更一般地，对双圈图B(p,l,q)上每一个点，可以得到以下关系。

结论2 设图G是B(p,l,q)中的一个双圈图，则对x∈VTk，有:

证明 首先：

结合引理1可得：

(3)

又：

=(n-nk)dG(x,vk)+RG(vk)-DTk(vk)+DTk(x)

(4)

因此，综合考虑式(3)、(4)以及引理9和结论1，可得：

结论3 设图G是B(p,l,q)中的一个双圈图，则对x∈VTi,y∈VTj,有：

Hxy=(n+1)r(x,y)+RG(y)-RG(x)+2(dG(y,vj)-dG(x,vi))

证明 由于双圈图|EG|=n+1。因此由引理7及结论3可知：

=(n+1)r(x,y)+RG(y)-RG(x)+2(dG(y,vj)-dG(x,vi))

结论4 设图G是B(p,l,q)中的一个双圈图，则对x∈VTi,有：

证明 由定义及结论3，有：

2.2 CC(x)在双圈图B(p,l,q)中的极小值

证明 首先由结论4及等式(4)可得：

CC(x)=DTi(x)-(n+ni)dG(x,vi)+RG(vi)-DTi(vi)+2Kf(G)

(5)

图4 将悬挂点x变为顶点v的邻点

由式(3)可知，顶点x的选取只与DTi(x)-(n+nTi)dG(x,vi)有关，再由引理2可知，顶点x为分支Ti上的悬挂点时，CC(x)的值将取得极小值。不失一般性，不妨设|VCq|≤|VCp|,取vi∈VCq，则由结论4及引理4，5和6可知，除Cp、Cq及路Pl上的点及顶点x外，其余顶点皆为同一个邻点的悬挂点，且该共同邻点在路Pl上时，CC(x)将取得极小值，这里取共同邻点为v如图4中的G1。

断言1 设G2是将图G1中包含x的所有悬挂点皆与v相邻构成的新图，则CCG2(x)

设H是G1-Cq-x+v的导出子图，由引理10有：

同时，由引理3有：

Kf(G1)=Kf(G-x)+1+(n-2)+RG-x(vi)

Kf(G2)=Kf(G-x)+1+(n-2)+RG-x(v)

因此:

=(2n-3q-2)r(vi,v)-3

由RG(x)和Kf(G)的定义可得：

因此：

首先由Kf(G)的定义及引理3有：

同样由定义有：

再由结论4与引理10可得：

同理，可得：

因此：

由于3≤q≤n-2易知当n≥14时，Δ>0。重复以上过程，即可得证。

综上可得定理1成立。