胡俊偉, 邵燕靈

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

1 引 言

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

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

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

目前關于樹的Wiener極化指數(shù)的研究較多，但是對于含圈圖的Wiener極化指數(shù)問題的研究卻很少，本文將研究具有k個懸掛點且無1長懸掛路的n階單圈圖的Wiener極化指數(shù)，通過引出五種圖的變換，給出了這類圖的極大Wiener極化指數(shù)，并且刻畫了相應的極圖.

2 引理及圖的變換

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

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

引理2[4]設U=(V,E)是一個單圈圖，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,則

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

2.1 第I種圖變換

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

圖1 第I種圖變換

引理3 設n≥2k+c,圖U′是由圖U經(jīng)過第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或點u不在圈c上時,根據(jù)引理2，有

由于

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

故

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

情形2.c=4且點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.

當c=3且點u不在圈c上的情況已在情形1中證明，因此引理得證.

2.2 第II種圖變換

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

圖2 第II種圖變換

引理4 設c≥4或c=3,n=2k+3,m≤c, 圖U(n,k,c)是由U′(n,k,c)經(jīng)過第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′)分為三部分計算，第一部分

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

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

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

由引理1和引理2知

(1)當c≥7時，因

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)當c=6時，因Wp(U2)=Wp(U2′)=4k,Wp(U3)=Wp(U3′)=3,Wp(U1)>Wp(U1′),故WP(U)-WP(U′)>0.

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

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

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

綜上所述，引理得證.

2.3 第III種圖變換

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

圖3 第III種圖變換

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

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

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只在點v1處連接一些懸掛樹，其中這些懸掛樹可以是懸掛路，也可以是通過一條邊與一個類星圖中心連接，設這樣的類星圖有m個，將每一個類星圖以及與它直接連接的邊記做一個分支，每個分支上分別有k1,k2，…,km條懸掛路，在懸掛路不變的情況下，設圖U3是將U2上這m個分支的懸掛路均轉移到一個分支上的圖.稱圖U3是由U2經(jīng)過第IV種圖變換所得(如圖4所示).

圖4 第IV種圖變換

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

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

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

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

2.5 第V種圖變換

圖5 第V種圖變換

3 主要結論

定理1 設圖U是具有k個懸掛點且無1長懸掛路的n階單圈圖，c(U)≥4,則

等號成立當且僅當U=U(n,k,c)(如圖2所示).

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

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

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

綜上所述，定理得證.

定理2 設U是具有k個懸掛點且無1長懸掛路的n階單圈圖，c(U)=3,則

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

綜上所述，定理得證.

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

定理3 設U是具有k個懸掛點且無1長懸掛路的n階單圈圖，c(U)≥3,則