恰含k個(gè)懸掛點(diǎn)的單圈圖的極大Wiener極化指數(shù)*

胡俊偉, 邵燕靈

(中北大學(xué) 數(shù)學(xué)系,山西 太原 030051)

1 引 言

圖的Wiener極化指數(shù)是由Harold在1947年研究化學(xué)分子結(jié)構(gòu)提出的.目前，Wiener 極化指數(shù)已引起大家的廣泛關(guān)注[1-11].設(shè)U=(V,E)是一個(gè)簡(jiǎn)單連通圖，且|V|=n,|E|=m,稱(chēng)U為(n,m)圖.若m=n+c-1,則稱(chēng)U為c圈圖,特別當(dāng)c=1時(shí)，稱(chēng)U為單圈圖，并用c(U)表示U中圈的長(zhǎng)度.用dU(u,v)或d(u,v)表示圖U中u與v兩點(diǎn)之間的距離.用NU(v)表示點(diǎn)v的鄰點(diǎn)集合，則dU(v)=|NU(v)|為點(diǎn)v的度,特別的，如果dU(v)=1,則v稱(chēng)作U的懸掛點(diǎn)，一條i度懸掛路是一條內(nèi)部點(diǎn)度均為2且兩端點(diǎn)度分別為1和i(i≥3)的路.如果一個(gè)圖U是由一個(gè)頂點(diǎn)v連接若干條長(zhǎng)度至少為2的路所得到的圖，則稱(chēng)U為類(lèi)星圖，點(diǎn)v為U的中心點(diǎn).

圖U的Wiener極化指數(shù)定義為圖U中距離為3的點(diǎn)對(duì){u,v}的數(shù)目[1-2]，記為

Wp(U)=|{{u,v}|dU(u,v)=3,u,v∈V}|

目前關(guān)于樹(shù)的Wiener極化指數(shù)的研究較多，但是對(duì)于含圈圖的Wiener極化指數(shù)問(wèn)題的研究卻很少，本文將研究具有k個(gè)懸掛點(diǎn)且無(wú)1長(zhǎng)懸掛路的n階單圈圖的Wiener極化指數(shù)，通過(guò)引出五種圖的變換，給出了這類(lèi)圖的極大Wiener極化指數(shù)，并且刻畫(huà)了相應(yīng)的極圖.

2 引理及圖的變換

引理1[1]設(shè)T=(V,E)是一個(gè)樹(shù)圖，則

令mi,j是樹(shù)圖T中一端點(diǎn)度為i且另一端點(diǎn)度為j的邊的數(shù)目，則由引理1，有

引理2[4]設(shè)U=(V,E)是一個(gè)單圈圖，C是U中的圈.

(i)若c(U)=3且記V(C)={v1,v2,v3},則

(ii)若c(U)=4且記V(C)={v1,v2,v3,v4},則

(iii)若c(U)≥5,則

為證明本文結(jié)果，下面定義五種單圈圖的變換，并考慮變換前后單圈圖的Wiener極化指數(shù).

2.1 第I種圖變換

設(shè)n≥2k+c,U是如下圖所示的具有k個(gè)懸掛點(diǎn)且無(wú)1長(zhǎng)懸掛路的n階單圈圖，其中U1是U的含圈子圖，e=uv∈E(U),點(diǎn)v處連接k1條懸掛路.設(shè)圖U′=U/e是圖U通過(guò)對(duì)e收縮得到的，即在圖U中刪除邊e,將點(diǎn)u和v合并為一點(diǎn)，然后在點(diǎn)v連接的某條懸掛路上添加一個(gè)頂點(diǎn)得到.稱(chēng)圖U′是由圖U經(jīng)過(guò)第I種圖變換(縮邊變換)所得(如圖1所示).

圖1 第I種圖變換

引理3 設(shè)n≥2k+c,圖U′是由圖U經(jīng)過(guò)第I種圖變換(縮邊變換)所得(如圖1所示).若c≥4,或c≥3且u不在圖U的圈上，則Wp(U′)≥Wp(U).

證明令NU(u)/v={u1,u2,……,us}和NU(v)/u={v1,v2,……,vt}.考慮以下兩種情形.

情形1.c≥5或點(diǎn)u不在圈c上時(shí),根據(jù)引理2，有

由于

又由于dU(ui)≥2,dU(vi)≥2,則

故

因此，Wp(U′)-Wp(U)≥0.

情形2.c=4且點(diǎn)u在圈c上,根據(jù)引理2，有

同理由于

因此

1-(dU(u)-1)(dU(v)-1)+(2-dU(v))

由于dU(ui)≥2,dU(vi)=2,dU(u)≥3,則

故

(dU(v)-1)(dU(u)-1)+(dU(v)-3)

因此Wp(U′)-Wp(U)≥0.

當(dāng)c=3且點(diǎn)u不在圈c上的情況已在情形1中證明，因此引理得證.

2.2 第II種圖變換

設(shè)c≥4或c=3,n=2k+3,m≤c,U′(n,k,c)是在一個(gè)c長(zhǎng)圈的m個(gè)頂點(diǎn)v1,v2,…,vm處分別連接k1,k2，…,km條2長(zhǎng)或2長(zhǎng)以上的懸掛路所得的n階單圈圖，其中k=k1+k2+…+km,設(shè)U(n,k,c)是將U′(n,k,c)的k條懸掛路全部連接到c長(zhǎng)圈的一點(diǎn)處(如v1)所得的圖.稱(chēng)圖U(n,k,c)是由U′(n,k,c)經(jīng)過(guò)第II種圖變換所得(如圖2所示).

圖2 第II種圖變換

引理4 設(shè)c≥4或c=3,n=2k+3,m≤c, 圖U(n,k,c)是由U′(n,k,c)經(jīng)過(guò)第II種圖變換所得n階單圈圖(如圖2所示)，則Wp(U(n,k,c))>Wp(U′(n,k,c)).

證明分別記U=U(n,k,c),U′=U′(n,k,c).將Wp(U)和Wp(U′)分為三部分計(jì)算，第一部分

是懸掛路之間Wiener極化指數(shù)的值，第二部分

是懸掛樹(shù)到圈上Wiener極化指數(shù)的值，第三部分

是圈上Wiener極化指數(shù)的值，則

由引理1和引理2知

(1)當(dāng)c≥7時(shí)，因

Wp(U1) =(k1+k2+…+km)(k1+k2+…+km-1)+(n-2k1-2k2-…-2km-c)=

k(k-1)+n-2k-c=n+k2-3k-c

Wp(U2)=4(k1+k2+…+km)=4k

Wp(U3)=c

所以Wp(U)=n+k2+k.同理，

Wp(U1′)=k1k2+k2k3+…+km-1km+kmk1+k1(k1-1)+…+km(km-1)+

Wp(U2′)=4(k1+k2+…+km)=4k

Wp(U3′)=c

(2)當(dāng)c=6時(shí)，因Wp(U2)=Wp(U2′)=4k,Wp(U3)=Wp(U3′)=3,Wp(U1)>Wp(U1′),故WP(U)-WP(U′)>0.

(3)當(dāng)c=5時(shí)，因Wp(U2)=Wp(U2′)=4k,Wp(U3)=Wp(U3′)=0,Wp(U1)>Wp(U1′),故WP(U)-WP(U′)>0.

(4)當(dāng)c=4時(shí)，因Wp(U2)=Wp(U2′)=3k,Wp(U3)=Wp(U3′)=0,Wp(U1)>Wp(U1′),故WP(U)-WP(U′)>0.

(5)當(dāng)c=3,n=2k+3時(shí)，因Wp(U2)=Wp(U2′)=2k,Wp(U3)=Wp(U3′)=0,Wp(U1)>Wp(U1′),故WP(U)-WP(U′)>0.

綜上所述，引理得證.

2.3 第III種圖變換

設(shè)圖U1是具有k個(gè)懸掛點(diǎn)、圈長(zhǎng)為3且無(wú)1長(zhǎng)懸掛路的n階單圈圖(如圖3所示)，其中v1v2v3是一個(gè)3圈，3圈上每一點(diǎn)連接一些懸掛樹(shù)，其中這些懸掛樹(shù)可以是懸掛路，也可以是通過(guò)一條邊與一個(gè)類(lèi)星圖中心連接.設(shè)圖U2是將U1中3圈上點(diǎn)v2,v3處連接的懸掛樹(shù)全部移到點(diǎn)v1處所得的圖.稱(chēng)圖U2是由U1經(jīng)過(guò)第III種圖變換所得(如圖3所示).

圖3 第III種圖變換

引理5 設(shè)圖U2是由U1經(jīng)過(guò)第III種圖變換所得的n階單圈圖(如圖3所示)，則Wp(U2)>Wp(U1).

證明設(shè)在圖U1中，與v1點(diǎn)距離為1的點(diǎn)有a個(gè)，距離為2的點(diǎn)至少有a+m1(m1≥0)個(gè)；與v2點(diǎn)距離為1的點(diǎn)有b個(gè)，距離為2的點(diǎn)至少有b+m2(m2≥0)個(gè)；與v3點(diǎn)距離為1的點(diǎn)有c個(gè)，距離為2的點(diǎn)至少有c+m3(m3≥0)個(gè).則

Wp(U2) -Wp(U1)=(a+b+c+1)(a+b+c+m1+m2+m3)-ab-ac-bc-

(a+1)(a+m1)-(b+1)(b+m2)-(c+1)(c+m3)

因(a+b+c+1)(a+b+c+m1+m2+m3)=(a+m1)(a+b+c+1)+(b+m2)(a+b+c+1)+(c+m3)(a+b+c+1),所以Wp(U2)-Wp(U1)>0,引理得證.

2.4 第IV種圖變換

如圖4所示，圖U2只在點(diǎn)v1處連接一些懸掛樹(shù)，其中這些懸掛樹(shù)可以是懸掛路，也可以是通過(guò)一條邊與一個(gè)類(lèi)星圖中心連接，設(shè)這樣的類(lèi)星圖有m個(gè)，將每一個(gè)類(lèi)星圖以及與它直接連接的邊記做一個(gè)分支，每個(gè)分支上分別有k1,k2，…,km條懸掛路，在懸掛路不變的情況下，設(shè)圖U3是將U2上這m個(gè)分支的懸掛路均轉(zhuǎn)移到一個(gè)分支上的圖.稱(chēng)圖U3是由U2經(jīng)過(guò)第IV種圖變換所得(如圖4所示).

圖4 第IV種圖變換

引理6 設(shè)圖U3是由U2經(jīng)過(guò)第IV種圖變換所得的n階單圈圖(如圖4所示)，則Wp(U3)>Wp(U2).

證明假設(shè)第i個(gè)分支上的2長(zhǎng)懸掛路的數(shù)目是最多的，從除第i個(gè)分支的其他任意一個(gè)分支取一條懸掛路轉(zhuǎn)移到這個(gè)分支上，可知此時(shí)第i個(gè)分支上有ki+1條懸掛路，第j個(gè)分支上有kj-1條懸掛路，則Wiener極化指數(shù)變化為

ΔWp(U)=2ki-2(kj-1)=2(ki-kj)+2

由于ki-kj≥0,則ΔWp(U)>0,因此可知經(jīng)過(guò)變化后，圖的Wiener極化指數(shù)是增大的.依次將其他分支上的懸掛路均移到第i個(gè)分支上，可知Wiener極化指數(shù)是不斷增大的，直到將所有分支上的懸掛路都移到這一個(gè)分支上，此時(shí)圖的Wiener極化指數(shù)是最大的.證畢.

2.5 第V種圖變換

圖5 第V種圖變換

3 主要結(jié)論

定理1 設(shè)圖U是具有k個(gè)懸掛點(diǎn)且無(wú)1長(zhǎng)懸掛路的n階單圈圖，c(U)≥4,則

等號(hào)成立當(dāng)且僅當(dāng)U=U(n,k,c)(如圖2所示).

證明由引理3，圖U經(jīng)過(guò)第一種變換(縮邊變換)后，得到所有2長(zhǎng)以上的懸掛路均分布在圖U的圈上各點(diǎn)，再通過(guò)引理4，所有2長(zhǎng)以上的懸掛路均集中在圖U的圈上一點(diǎn)，用U(n,k,c)來(lái)表示所得到的圖.超過(guò)2長(zhǎng)懸掛路的點(diǎn)均可以轉(zhuǎn)移到其中的一條懸掛路上，因?yàn)樵谌﹂L(zhǎng)不變的情況下，這些點(diǎn)移動(dòng)到圈圖上的任何一個(gè)位置，都不會(huì)改變單圈圖Wiener極化指數(shù)的值.下面根據(jù)引理1、引理2分別進(jìn)行計(jì)算.

(iii)當(dāng)n=2k+6時(shí)，圈圖U(n,k,c)有c=4、c=5、c=6三種情況.計(jì)算得

(iv)當(dāng)n≥2k+7時(shí)，c≥7.當(dāng)c=7時(shí)，Wp(U(n,k,7))=n+k2+k,當(dāng)c>7時(shí)，圈長(zhǎng)的增加并不影響圖U的Wiener極化指數(shù)，則Wp(U(n,k,c))=n+k2+k(c≥7).

綜上所述，定理得證.

定理2 設(shè)U是具有k個(gè)懸掛點(diǎn)且無(wú)1長(zhǎng)懸掛路的n階單圈圖，c(U)=3,則

證明由引理3，圖U經(jīng)過(guò)第一種變換(縮邊變換)后，得到圈上每一點(diǎn)連接一些懸掛樹(shù)，其中這些懸掛樹(shù)可以是懸掛路，也可以是通過(guò)一條邊與一個(gè)類(lèi)星圖中心連接.通過(guò)引理4，將所有懸掛樹(shù)均集中在圖U的圈上一點(diǎn)，通過(guò)引理5，在懸掛點(diǎn)不變的情況下，將各分支上的懸掛路集中到一個(gè)分支上，用U(n,k,3)來(lái)表示所得到的圖.超過(guò)2長(zhǎng)懸掛路的點(diǎn)均可以轉(zhuǎn)移到其中的一條懸掛路上，因?yàn)樵谌﹂L(zhǎng)不變的情況下，這些點(diǎn)移動(dòng)到圈圖上的任何一個(gè)位置，都不會(huì)改變單圈圖Wiener極化指數(shù)的值.下面根據(jù)引理1、引理2分別進(jìn)行計(jì)算.

綜上所述，定理得證.

將定理2中c=3的情況與定理1中c≥4的情況在階數(shù)相同時(shí)分別進(jìn)行比較，顯然可得以下結(jié)論.

定理3 設(shè)U是具有k個(gè)懸掛點(diǎn)且無(wú)1長(zhǎng)懸掛路的n階單圈圖，c(U)≥3,則