一類圖變換對其維納指標(biāo)與離心率之差的影響

林雅津,王月卿

（1.閩南師范大學(xué)數(shù)學(xué)與統(tǒng)計學(xué)院,福建漳州363000；2.閩南師范大學(xué)計算機(jī)學(xué)院,福建 漳州363000）

本文所討論的均為簡單連通圖，設(shè)G=(V(G),E(G))，其中頂點集為V(G)，邊集為E(G).用n(G)和m(G)分別表示圖G的頂點數(shù)和邊數(shù).對任意u,v∈V(G)，用dG(u,v)表示G中u和v之間的最短距離.用dG(v)表示頂點v到G中其余頂點的距離之和，即分別用deg(v)和ω(G)表示頂點v的度和圖G的連通分支個數(shù).若邊e∈E(G)滿足ω(G-e)>ω(G)，則稱e為連通圖G的一條割邊.對于圖G的某一割邊e=uv∈E(G)，分別用n(Gu)，n(Gv)表示G中分布在e兩側(cè)的頂點數(shù)目.

圖的維納指標(biāo)是1947年由著名的化學(xué)家Wiener[1]提出的基于距離不變量的拓?fù)渲笜?biāo)，其定義是圖中所有不同頂點對間的距離和，即

關(guān)于圖維納指標(biāo)的研究和進(jìn)展可參考文獻(xiàn)[1-6].

對v∈V(G)，頂點v在G中的離心率εG(v)是v與G中其他任意點的最大距離,即

定義G中最大的頂點離心率為直徑，用diam(G)表示；最小的頂點離心率為半徑，用rad(G)表示.

圖G的離心率為G中所有點的離心率之和，用ε(G)表示.因此

關(guān)于圖的總離心率和平均離心率的研究和進(jìn)展可參考文獻(xiàn)[7-9].若e∈E(G)，令G?e表示圖G通過收縮邊e之后而得到的圖，顯然n(G)=n(G?e)+1，如圖1所示.

圖1 圖G和G?eFig.1 The graph G and graph G?e

1 預(yù)備知識

Darabi[10]研究了G和G?e的維納指標(biāo)和離心率之間差的關(guān)系，得到了以下結(jié)論.

定理1[10]設(shè)G為具有n(G)≥3個頂點的簡單連通圖，e∈E(G)是G的某一割邊,則

同時提出了以下猜想.

猜想1[11]設(shè)G為具有n(G)≥3個頂點的簡單連通圖，則對于任意e∈E(G)，有

Das[11]證明了上述猜想.

本文進(jìn)一步研究圖的變換對其W(G)-ε(G)的影響.設(shè)G為簡單連通圖，對e∈E(G)，G'為G通過收縮邊e=uv成為一個新點eu并在eu上添加一個懸掛邊euev而得到的圖，如圖2所示.

圖2 圖G和G'Fig.2 The graph G and graph G'

顯然圖G'對比文獻(xiàn)[11]中的圖G?e來說，保持了頂點數(shù)的不變，即n(G)=n(G')=n.本文研究并討論了當(dāng)e是圖G（n(G)≥3）的割邊時，給出了不同情況下W(G')-ε(G')和W(G)-ε(G)之間的大小關(guān)系.

在給出結(jié)論前，先分析圖G和圖G'的一些性質(zhì).

如圖2，令割邊e=uv，令G-uv=Gu∪Gv，這里Gu和Gv是分別包含u和v的分支，n(Gu)和n(Gv)分別表示兩個分支的頂點數(shù)，不妨設(shè)n(Gu)≥n(Gv).則

對于G',有

因此W(G)-W(G')=n(Gu)n(Gv)-n+1.

比較圖G'和圖G，點u在G'對應(yīng)點eu；點v在G'對應(yīng)點ev，且保持頂點離心率不變，即εG(v)=εG'(ev).因此變換成G'后離心率最多減少n-1，即

當(dāng)n(Gv)=2 時，W(G)-W(G')=n-3.將Gu中的點分為S1,S2,…,Si(i=2,…n-3)類，Si表示Gu中與u距離為i的頂點集.點v在G'中對應(yīng)點ev使得離心率不發(fā)生改變，并且當(dāng)點u存在屬于Gu的離心點時，也有點u在G'中對應(yīng)的點eu的離心率不發(fā)生改變.

當(dāng)n(Gv)≥3，由于n(Gu)≥n(Gv)，因此n(G)=n≥6 且W(G)-W(G')≥2n-8，等號成立當(dāng)且僅當(dāng)n(Gv)=3.又因為ε(G)-ε(G')≤n-1，所以

等式成立當(dāng)且僅當(dāng)n=7.

引理1設(shè)G為簡單連通圖，e∈E(G)為G的某一割邊，G和G'如圖2所示.若εGu(u)≥4，則對任意x∈S1，有εGu(x)≥3=dG(x,w).

證明（反證法）假設(shè)?x∈S1，使得εGu(x)≤2，即對任意y∈Gu，都有d(x,y)≤2.因為εGu(u)≥4，令u1為u的離心點，即d(u,u1)≥4.取y=u1，則d(x,u1)≤2，因為d(u,x)=1，所以有

又因為εGu(u)=d(u,u1)≥4，與式（2）矛盾，結(jié)論成立.

引理2設(shè)G為簡單連通圖，e∈E(G)為G的一割邊，G和G'如圖2所示.若εGu(u)≥6，則

1）對任意x∈S1，有εGu(x)>3=dG(x,w)；

2）對任意y∈S2，有εGu(y)≥4=dG(y,w).

證明由定理1可知，1）顯然成立，接下來對2）進(jìn)行證明.

（反證法）假設(shè)?y∈S2，使得εGu(y)≤3，即對任意y1∈Gu，都有d(y,y1)≤3.因為εGu(u)≥6，令u1為u的離心點，即d(u,u1)≥6.取y1=u1，則d(y,u1)≤3，因為d(u,y)=2，所以有

又因為εGu(u)=d(u,u1)≥6，與（3）矛盾，結(jié)論成立.

2 主要結(jié)論

以下給出不同情況下W(G')-ε(G')與W(G)-ε(G)之間的大小關(guān)系，如圖2所示.不妨設(shè)n(Gu)≥n(Gv)，接下來按n(Gv)大小進(jìn)行分類.當(dāng)n(Gv)=1，顯然有W(G)-ε(G)=W(G')-ε(G').以下討論n(Gv)≥2的情況，其中n(Gv)=2時如圖3所示.

圖3 n(Gv)=2的圖GFig.3 The graph G of n(Gv)=2

顯然對任意x∈Si，都有

因此若Gu中的點在G中的離心點只有w時，變換成G'后頂點離心率將會減少1.若Gu中的點在G中存在離心點是屬于Gu中的話，變換成G'后頂點離心率將會保持不變.

定理2設(shè)G簡單連通圖，e=uv為G的某一割邊，G'為收縮G中邊e=uv成為一個點eu，并在eu上添加懸掛邊euev而得到的圖，如圖2所示.則以下六種情況都有W(G)-ε(G)

1）當(dāng)n(Gv)=2，εG(u)=2，且deg(u)=n-2；

2）當(dāng)n(Gv)=2，εG(u)=2，deg(u)≤n-3且diam(Gu)=2；

3）當(dāng)n(Gv)=2，εG(u)=2，deg(u)≤n-3，diam(Gu)=3且對?x∈S1都有εGu(x)=2；

4）當(dāng)n(Gv)=2，εG(u)=3，deg(u)≤n-4，diam(Gu)=3且對?x∈S1都有εGu(x)=2；

5）當(dāng)n(Gv)=2，εG(u)=3，deg(u)≤n-4，diam(Gu)=4 且對?x∈S1都有εGu(x)=2，對?y∈S2，都有2≤εGu(y)≤3；

6）當(dāng)n(Gv)=3，n=6且圖G?P6.

證明1）因為n(Gv)=2，εG(u)=2，且deg(u)=n-2.如圖4，此時u的離心點只有w.對?x∈S1，有εG(x)=dG(x,w)=3.因此εG'(x)=dG'(x,w)=2，又εG(u)=d(u,w)=2，所以由式（4）有εG'(eu)=1.由此可知在這種情況下，G變換成G'后只有一個頂點v的離心率不發(fā)生改變，即ε(G)-ε(G')=n-1.因此有

圖4 deg(u)=n-2時的圖GFig.4 The graph G of deg(u)=n-2

2）當(dāng)deg(u)≤n-3，又εG(u)=2，所以u在圖G中至少有兩個離心點.當(dāng)diam(Gu)=2 時，即?x∈V(Gu)/{u}，有εGu(x)≤2.又因為dG(x,w)≥3，因此εG(x)≥3 且x在G中的離心點均為w，故εG'(x)=εG(x)-1，由式（4）可知G變 換成G' 后只有兩個頂點u,v的離心率不發(fā)生改變，即ε(G)-ε(G')=n-2.所以有

結(jié)論成立.

3)當(dāng)deg(u)≤n-3，diam(Gu)=3，且對?x∈S1，都有εGu(x)=2時,有εG(x)=dG(x,w)=3,則由式（4）顯然可知對任意x∈S1，都有εG'(x)=εG(x)-1=2.又因為diam(Gu)=3，因此對任意的εGu(y)=3 成立時，都有y∈S2，因此有εG(y)=dG(y,w)=4=dG'(y,w)+1，所以εG'(y)<εG(y).因此對任意y∈S2都有εG'(y)<εG(y),所以G變換成G'后只有兩個頂點u,v的離心率不發(fā)生改變，即ε(G)-ε(G')=n-2，所以有

結(jié)論成立.

4）當(dāng)εG(u)=3，deg(u)≤n-4，diam(Gu)=3，且對?x∈S1，都有εGu(x)=2時,有εG(x)=dG(x,w)=3，則顯然可知對任意x∈S1，都有εG'(x)=dG'(x,w)=2<εG(x).又因為diam(Gu)=3,即對任意的εGu(y)=3 成立時，都有y∈S2∪S3，因此有εG(y)=dG(y,w)=dG'(y,w)+1，所以對任意的y∈S2∪S3，都有εG'(y)<εG(y).因此G變換成G'只有u,v兩個點的離心率不發(fā)生改變，即ε(G)-ε(G')-n=2，所以有

結(jié)論成立.

5）當(dāng)εG(u)=3，deg(u)≤n-4，diam(Gu)=4 時，且對?x∈S1，都有εGu(x)=2，對?y∈S2，有2≤εGu(y)≤3 時，有εG(x)=dG(x,w)=3，3≤εG(y)=dG(y,w)≤4.則可知對任意的x∈S1，都有εG'(x)=dG'(x,w)=2<εG(x)；對任意y∈S2，都有εG'(y)=dG'(y,w)=εG(x)-1.又因為diam(Gu)=3，即對任意的εGu(z)=4 成立時，都有z∈S3，所以對任意z∈S3有εG'(z)<εG(z).因此G變換成G'之后只有u,v兩個點的離心率不發(fā)生改變，即ε(G)-ε(G')=n-2，所以有

結(jié)論成立.

6）當(dāng)n(Gv)=3，n=6 時，即n(Gu)=n(Gv)=3，這時有W(G)-W(G')=4.又因為圖G?P6，顯然ε(G)-ε(G')=5.所以有

結(jié)論成立.

定理3設(shè)G簡單連通圖，e=uv為G的某一割邊，G'為收縮G中邊e=uv成為一個點eu，并在eu上添加懸掛邊euev而得到的圖，如圖2所示.則以下五種情況都有W(G)-ε(G)=W(G')-ε(G')成立：

1）當(dāng)n(Gv)=2，εG(u)=2，deg(u)≤n-3，diam(Gu)=3且有且只有一個點x∈S1，使得εGu(x)=3；

2）當(dāng)n(Gv)=2，εG(u)=3，diam(Gu)=3且有且只有一個點x∈S1，使得εGu(x)=3；

3）當(dāng)n(Gv)=2，εG(u)=3，diam(Gu)=4，?x∈S2，有εGu(x)≤3，且有且只有一個點y∈S1，使得3≤εGu(y)≤4；

4）當(dāng)n(Gv)=2，4≤εG(u)≤5，且G?{P7,P8}；

5）當(dāng)n(Gv)≥3，且n=7.

證明1）當(dāng)εG(u)=2，deg(u)≤n-3且diam(Gu)=3時，對任意x∈Gu，都有εGu(x)≤3.又由式（4）可知對任意x∈Gu，都有εG(x)≥3 且等式成立當(dāng)且僅當(dāng)x∈S1.因此變換成G'后S2中任意點的離心率均減少1.又因為有且只有一個點x∈S1，使得εGu(x)=3，即S1中的點除了x之外的其余點離心率均為2.因此變換成G'后S1中除了x之外的其余點的離心率均減少1.又點u,v的離心率均不發(fā)生改變，所以G變換成G'之后離心率減少了n-3，即ε(G)-ε(G')=n-3.所以有

結(jié)論成立.

2）當(dāng)εG(u)=3，diam(Gu)=3，且有且只有一個點x∈S1，使得εGu(x)=3時，有εG(x)=εGu(x)=3.又由1）的證明顯然可知，G變換成G'之后離心率減少了n-3，即ε(G)-ε(G')=n-3.所以有

結(jié)論成立.

3）當(dāng)εG(u)=3，diam(Gu)=4，對任意的x∈S2，都有εGu(x)≤3，且有且只有一個點y∈S1，使得3≤εGu(y)≤4時，由式（4）可知，S2和S3中所有點的離心率在G變換成G'之后均減少1.又因為有且只有一個點y∈S1，使得3≤εGu(y)≤4，所以由1）的證明可知，G變換成G'之后離心率減少了n-3，即ε(G)-ε(G')=n-3.所以有

結(jié)論成立.

4）當(dāng)4≤εG(u)≤5，由引理1 可知，對任意x∈S1都有εGu(x)≥3，因此由式（4）可知G變換成G'后S1中任意點的離心率均不發(fā)生改變.又因為G?{P7,P8}，所以有|S1|=1，且由式（4）可知，任意y∈Gu/{S1,u}都有εG(y)=εG'(y)+1.因此G變換成G'之后恰好有三個頂點離心率不發(fā)生改變，所以離心率減少了n-3，即ε(G)-ε(G')=n-3.所以有

結(jié)論成立.

5）當(dāng)n=7時，由式（1）有

結(jié)論成立.

注1下面分別給出滿足上述條件的圖例.

滿足條件1），如圖5.

圖5 滿足條件1)的圖GFig.5 A graph G that satisfies the condition 1)

此時，W(G)-ε(G)=44-23=21，而W(G')-ε(G')=40-19=21，所以有W(G)-ε(G)=W(G')-ε(G').

滿足條件2），如圖6.

圖6 滿足條件2)的圖GFig.6 A graph G that satisfies the condition 2)

此時，W(G)-ε(G)=63-31=32，而W(G')-ε(G')=58-26=32，所以有W(G)-ε(G)=W(G')-ε(G').

滿足條件3），如圖7.

圖7 滿足條件3)的圖GFig.7 A graph G that satisfies the condition 3)

此時，W(G)-ε(G)=50-28=22，而W(G')-ε(G')=46-24=22，所以有W(G)-ε(G)=W(G')-ε(G').

滿足條件4），如圖8.

圖8 滿足條件4)的圖GFig.8 A graph G that satisfies the condition 4)

此時，W(G)-ε(G)=56-33=23，而W(G')-ε(G')=52-29=23，所以有W(G)-ε(G)=W(G')-ε(G').

滿足條件5），如圖9.

圖9 滿足條件5)的圖GFig.9 A graph G that satisfies the condition 5)

此時，W(G)-ε(G)=43-23=20，而W(G')-ε(G')=37-17=20，所以有W(G)-ε(G)=W(G')-ε(G').

定理4設(shè)G簡單連通圖，e=uv為G的某一割邊，G'為收縮G中邊e=uv成為一個點eu，并在eu上添加懸掛邊euev而得到的圖，如圖2所示.則以下八種情況都有W(G)-ε(G)>W(G')-ε(G')成立：

1）當(dāng)n(Gv)=2，εG(u)=2，deg(u)≤n-3，diam(Gu)=3 且至少有兩個點x,y∈S1，使得εGu(x)=εGu(y)=3；

2）當(dāng)n(Gv)=2，εG(u)=2，deg(u)≤n-4，diam(Gu)=4；

3）當(dāng)n(Gv)=2，εG(u)=3，diam(Gu)=3且至少有兩個點x,y∈S1，使得εGu(x)=εGu(y)=3；

4）當(dāng)n(Gv)=2，εG(u)=3，diam(Gu)=4且至少有兩個點x∈S2，使得εGu(x)=4；

5）當(dāng)n(Gv)=2，εG(u)=3，5≤diam(Gu)≤6；

6）當(dāng)n(Gv)=2，4≤εG(u)≤5，且3≤deg(u)≤n-5(n≥8)；

7）當(dāng)n(Gv)=2，εG(u)≥6；

8）當(dāng)n(Gv)≥3，且n≥8.

證明1）當(dāng)n(Gv)=2，εG(u)=2，deg(u)≤n-4，diam(Gu)=3且至少有兩個點x,y∈S1，使得εGu(x)=εGu(y)=3 時，由式（4）可知G變換成G'后x,y的離心率不會發(fā)生改變.又因為點u,v的離心率也不發(fā)生改變，所以G變換成G'后至少有四個點的離心率不發(fā)生改變，因此ε(G)-ε(G')≤n-4，所以有

2）當(dāng)n(Gv)=2，diam(Gu)=4 時，因為S1里的任意點的離心率均小于等于3，所以一定?x∈S2，使得εGu(x)=4.并且x在Gu中的離心點都在S2中，顯然dG(x,w)=dG(x,u)+dG(u,w)=εGu(x)=4，因此有εG(x)=εGu(x)=εG'(x)=4.假設(shè)點y∈S2，使得εGu(x)=dG(x,y)=4，則點y的離心率也為4 且離心點為x.所以G變換成G'后至少有四個點的離心率不會發(fā)生改變，因此ε(G)-ε(G')≤n-4，所以有

結(jié)論成立.

3）當(dāng)n(Gv)=2，εG(u)=3，diam(Gu)=3 且至少兩個點x,y∈S1，使得εGu(x)=εGu(y)=3 時，由1）的證明顯然可知G變換成G'后至少有四個點的離心率不發(fā)生改變，因此ε(G)-ε(G')≤n-4，所以有

結(jié)論成立.

4）當(dāng)n(Gv)=2，εG(u)=3，diam(Gu)=4 且至少存在一個點x∈S2，使得εGu(x)=4 時，顯然點x對應(yīng)的離心點不可能在S1中，這時我們分兩種情況討論.①若點x對應(yīng)的離心點y∈S2，則顯然有εGu(y)=4，所以G變換成G'后至少有四個點的離心率不會發(fā)生改變，因此ε(G)-ε(G')≤n-4，所以有

②若點x對應(yīng)的離心點y∈S3，則顯然存在z∈S1，使得dGu(y,z)=3.否則若dGu(y,z)≤2，則有εGu(x)=dGu(x,y)≤3 與εGu(x)=4 矛盾.所以G變換成G'后至少有四個點的離心率不會發(fā)生改變，因此ε(G)-ε(G')≤n-4，所以有

結(jié)論成立.

5）當(dāng)n(Gv)=2，εG(u)=3，5≤diam(Gu)≤6 時，①若diam(Gu)=5，因為對?x∈S2，都有εGu(x)≤5，且當(dāng)εGu(x)=dGu(x,y)=5 時，對應(yīng)的離心點y一定屬于S3中，因此有εGu(y)=5.所以顯然圖G變換成G'后至少有四個點的離心率不會發(fā)生改變，因此ε(G)-ε(G')≤n-4，所以有W(G)-ε(G)>W(G')-ε(G').若εGu(x)≤4，則所有εGu(x)=dGu(x,y)=5 都有x∈S3,且對應(yīng)的離心點y一定屬于S3中，因此有εGu(y)=5.所以顯然圖G變換成G'后至少有四個點的離心率不會發(fā)生改變，因此ε(G)-ε(G')≤n-4，所以有W(G)-ε(G)>W(G')-ε(G').

②若diam(Gu)=6，因為對任意x∈S1∪S2,有1≤εGu(x)≤5，所以一定存在x∈S3，使得εGu(x)=6.并且x在Gu中的離心點都在S3中，顯然dG(x,w)=dG(x,u)+dG(u,w)=εGu(x)=6，因此εG(x)=εGu(x)=εG'(x)=6.假設(shè)點y∈S3，使得εGu(x)=dG(x,y)=6，則點y的離心率也為6.所以G變換成G'后至少有四個點的離心率不會發(fā)生改變，因此ε(G)-ε(G')≤n-4，所以有

結(jié)論成立.

6）當(dāng)n(Gv)=2，4≤εG(u)≤5，且3≤deg(u)≤n-5(n≥8)時，有|S1|≥2，由引理1 可知，對任意x∈S1都有εGu(x)≥3，因此由式（4）可知G變換成G'后S1中任意點的離心率均不發(fā)生改變.又|S1|≥2，所以G變換成G'后至少有四個點的離心率不會發(fā)生改變，因此ε(G)-ε(G')≤n-4，所以有

結(jié)論成立.

7）當(dāng)n(Gv)=2，εG(u)≥6時，由定理2可知，對任意x∈S1都有εGu(x)>3，對任意y∈S2都有εGu(y)≥4.因此由式（4）可知G變換成G'后，S1和S2中任意點的離心率均不發(fā)生改變.又|S1∪S2|≥2，所以G變換成G'后至少有四個點的離心率不會發(fā)生改變，因此ε(G)-ε(G')≤n-4，所以有

結(jié)論成立.

8）當(dāng)n(Gv)≥3，n≥8時，由式（1）有

結(jié)論成立.