恰有2個圈的雙圈圖的覆蓋花費極小值

潘向峰

(安徽大學數(shù)學科學學院，安徽 合肥 230601)

陳海波

(長沙市岳麓實驗中學，湖南 長沙 410208)

盧健

(安徽大學數(shù)學科學學院，安徽 合肥 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指數(shù)是基于距離提出的一個拓撲指數(shù)，定義為所有點對之間距離的和，即：

1 基本概念

若x∈VG,令G-x表示圖G刪去頂點x和所有與x相鄰的邊后得到的新圖。類似地，若X?EG，令G-X表示圖G刪去集合X中所有的邊后得到的新圖。記Cn,Pn和Sn分別為頂點數(shù)為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為根點，頂點個數(shù)為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是一個頂點數(shù)為n≥6的簡單連通圖，G′=σ(G，v)是由圖G經(jīng)過σ-變換得到的，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是一個頂點數(shù)為n≥6的簡單連通圖，G′=σ(G,v)是由圖G經(jīng)過σ-變換得到的，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

經(jīng)過簡單計算可知，當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經(jīng)過β-變換得到的，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是一個簡單連通圖，邊數(shù)為m。則對x,y∈VG,有：

引理8[26]設T是一個邊數(shù)為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)

證明 通過對頂點個數(shù)n用數(shù)學歸納法來證明。當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變?yōu)轫旤cv的鄰點

由式(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成立。