固定圍長與最大度的單圈圖的Wiener指數

武軍秀, 高玉斌

(中北大學數學學院, 山西 太原 030051)

0 引言

1947年,化學家Wiener提出了Wiener指數。目前,Wiener指數已取得了許多的研究成果。學者們不僅在特定圖類如單圈圖、樹圖、雙圈圖中刻畫了Wiener指數的極圖;還在固定圍長、最大度、最小度、懸掛點數等條件下刻畫了Wiener指數的極圖[6-10]。Chen H L等[7]提出了關于刻畫固定圍長和最大度的n階圖類中Wiener指數的極小圖的問題。為解決該問題,本文中從圍長與最大度均為3的單圈圖類入手,得到了此類圖Wiener指數的極小圖的一些結構性質。

1 引理

引理1.1[5]固定最大度的樹圖中,T∈T(Δ,Δ)為最小Wiener指數圖。

推論1.3設U′是U(3,3)中具有極小Wiener指數的圖,則U′∈U(T1,T2,T3)。

推論1.3的證明設U∈U(3,3),其圈上的頂點為vi(i=1,2,3),Ti為U在vi的分支,則至少存在一點vi使得d(vi)=3,根據引理1.1～1.2,經過圖變換,使得度為3的頂點vi所在的分支變為頂點數相同的Ti′∈T(1,3)時其Wiener指數變小,得證。

引理1.4[12]設G1,G2分別為n1,n2階連通圖,u∈V(G1),v∈V(G2),若G是通過粘合u,v兩點構成的圖,則W(G)=W(G1)+W(G2)+(|V(G2)|-1)D(u|G1)+(|V(G1)|-1)D(v|G2)。

引理1.5設a1,b1,c,d為任意正整數,滿足a1≤b1,則

得證。

2 準備工作

設U∈U(T1,T2,T3),v1,v2,v3∈V(C3),Ti是U在vi點的分支,記Ti的頂點數為ni(n=n1+n2+n3,n≥13),層數為ki,第ki層的頂點數為mi,滿足k2≥k1≥k3>0。選取分支T2,T3,討論圖變換對Wiener指數的影響。

2.1 圖變換設w為T2中第(k2-1)層最上邊的頂點,u,u1為T2中第k2層與w相鄰的頂點。若m3=2k3-1,則w1為T3中第k3層最上邊的頂點,d(w,w1)=k2+k3;若1≤m3≤2k3-1-1,則w1為T3中第(k3-1)層最上邊的頂點,d(w,w1)=k2+k3-1。令U1=U-uw+w1u,G=U-u,Ti中第ki層的頂點構成集合Vi,T′i=Ti-Vi。

利用引理1.4易知,W(U)-W(U1)將等于圖G中所有頂點到w,w1兩點距離差的總和。

G中頂點到w,w1兩點的所有可能的距離差:

1)T1中頂點到w,w1兩點的距離差為k2-1-d(v3,w1)。

2)T2-u中頂點到w,w1兩點的距離差:

-d(w,w1), 2-d(w,w1), 4-d(w,w1),…,2i-d(w,w1),i=1,2,…k2-1.

3)T3中頂點到w,w1兩點的距離差:

d(w,w1),d(w,w1)-2,d(w,w1)-4,…,d(w,w1)-2i,i=1,2,…d(v3,w1).

各個距離差所對應的點數:

1)T1中距離差為k2-1-d(v3,w1)的點數為n1。

2)T2-u中各個距離差所對應的點數。距離差為2(k2-1)-d(w,w1)的點數為1,即v2點;若m2≠1,則距離差為-d(w,w1)的點數為1,即u1點;距離差2i-d(w,w1)(i=1,2,…,k2-2)所對應的點數可通過圖U(如圖1)的特點而獲得。如下:

圖1 圖U

距離差2i-d(w,w1)(i=1,2,…,k2-2)在T′2中所對應的點數為2i。

若m2=1或2,則距離差2i-d(w,w1)(i=1,2,…,k2-2)在T2-u中所對應的點數為2i。

若m2≥3,且2l+1≤m2≤2l+1(1≤l≤k2-2),則第k2層中,距離差2i-d(w,w1)(i=1,2,…,l-1)的點數為2i,距離差2l-d(w,w1)的點數為m2-2l;2i-d(w,w1)(i=l+1,…k2-2)的點數為0。

若m2≥3,且2l+1≤m2≤2l+1(1≤l≤k2-2),則T2-u中距離差2i-d(w,w1)(i=1,2,…l-1)的點數為2i+1,距離差2l-d(w,w1)的點數為m2,距離差2i-d(w,w1)(i=l+1,…k2-2)的點數為2i。

3)T3中各個距離差所對應的點數。距離差為d(w,w1)-2d(v3,w1)的點數為1,即v3點;若m3=2k3-1-1,則距離差為d(w,w1)的點數為1,即第k3層與w1相鄰的頂點;距離差d(w,w1)-2i(i=1,2,…,d(v3,w1)-1)所對應的點數可通過圖U的特點而獲得。如下:

若m3=2k3-1,則距離差d(w,w1)-2i(i=1,2,…,d(v3,w1)-1)在T3中所對應的點數為2i。

若1≤m3≤2k3-1-1,則距離差d(w,w1)-2i(i=1,2,…d(v3,w1)-1)在T3′中所對應的點數為2i。

若1≤m3≤2k3-2,則第k3層中,距離差d(w,w1)-2(d(v3,w1)-1)的點數為m3,距離差d(w,w1)-2i(i=1,2,…,d(v3,w1)-2)的點數為0。

若2k3-1-2k3-r-1

2.2 Wiener指數值的變化在k2-k3≥2的條件下,可分為兩種情形:

情形1:m3=2k3-1。

情形1.1:m2=1。

情形1.2:m2=2。

W(U)-W(U1)=D(w|G)-D(w1|G)

(k2-k3)+(k2-k3-2)-(k2+k3)

=2k2-1(k2-k3-6)+2k3(k2-k3+4)+2(k2-k3)-2+n1(k2-k3-1)-(k2+k3).

情形1.3:2l+1≤m2≤2l+1(1≤l≤k2-2).

若1≤l≤k3-1,利用引理1.5,則

W(U)-W(U1)=D(w|G)-D(w1|G)

n1(k2-k3-1)+2(k2-k3)-2-(k2+k3)

=2k2-1(k2-k3-6)+2k3(k2-k3+4)+n1(k2-k3-1)+2(k2-k3)-2-

(m2-1)(k2+k3)+2(2+m2l-2l+1).

若k3≤l≤k2-2,利用引理1.5,則

W(U)-W(U1)=D(w|G)-D(w1|G)

=2k2-1(k2-k3-6)+2k3(k2-k3+4)+n1(k2-k3-1)+2(k2-k3)-2-

(m2-1)(k2+k3)+2(2+m2l-2l+1).

綜上所述,若1≤l≤k2-2,則

W(U)-W(U1)=2k2-1(k2-k3-6)+2k3(k2-k3+4)+n1(k2-k3-1)

+2(k2-k3)-2-(m2-1)(k2+k3)+2(2+m2l-2l+1)

(1)

特別地,m2=1,2(l=0)時也滿足(1)式。

情形2:1≤m3≤2k3-1-1。

若1≤m3≤2k3-2,則第k3層上點的距離差之和為m3(k2-k3+3);若2k3-1-2k3-r-1

2k3-2(k2-k3+3)+…+2k3-r-1(k2-k3+2r+1)+(m3-(2k3-1-2k3-r-1))(k2-k3+2r+3)

=2k3(1-r)-2k3-r+m3(k2-k3+2r+3)≥2k3(1-r)-2k3-r+(2k3-1-2k3-r-1)(k2-k3+2r+3)

=2k3-1(k2-k3+5)-2k3-r-1(k2-k3+2r+5)

≥2k3-2(k2-k3+3)

>0.

綜上,若2l+1≤m2≤2l+1(1≤l≤k2-2)或m2=1,2(l=0),則

(2)

3 主要結論

定理1設U*是U(3,3)中具有極小Wiener指數的圖,階數n≥13,其各個分支的層數滿足k2≥k1≥k3>0,則

1)若m3=2k3-1,m2=1,則k2-k3≤5。

2)若m3=2k3-1,2k2-2

3)若m3=2k3-1,2≤m2≤2k2-2,則k2-k3≤6。

定理1的證明記圖變換后的圖為U1。易知n1≥2k3。令m2=1,若k2-k3≥6,則代入(1)式得

W(U*)-W(U1)=2k2-1(k2-k3-6)+2k3(k2-k3+4)+n1(k2-k3-1)+2(k2-k3)-2

>0,

結果(1)得證。

令m2=2k2-q+a(2≤q≤k2,1≤a≤2k2-q),l=k2-q,代入(1)式,

W(U*)-W(U1)=2k2-1(k2-k3-6)+2k3(k2-k3+4)+n1(k2-k3-1)+2(k2-k3)-2-

(2k2-q+a-1)(k2+k3)+4+2k2-q+1(k2-q-2)+2a(k2-q)

=2k2-q(2q-1(k2-k3-6)+(k2-k3)-2q-4)+2k3(k2-k3+4)+

n1(k2-k3-1)+a(k2-k3-2q)+3k2-k3+2

(3)

若k2-k3≥2q,則由(3)式得

W(U*)-W(U1)≥2k2-q(2q-1(k2-k3-6)+(k2-k3)-2q-4)+

2k3(k2-k3+4)+n1(k2-k3-1)+3k2-k3+2

(4)

若k2-k3≥2q+2,則f(q)=2k2-q(k2-k3-2q-4)單調遞減;若2q≤k2-k3≤2q+1,則f(q)單調遞增。

若k2-k3≤2q-1,則由(3)式得

W(U*)-W(U1)≥2k2-q(2q-1(k2-k3-6)+(k2-k3)-2q-4+(k2-k3)-2q)+

2k3(k2-k3+4)+n1(k2-k3-1)+3k2-k3+2

=2k2-q(2q-1(k2-k3-6)+2(k2-k3)-4q-4)+2k3(k2-k3+4)+

n1(k2-k3-1)+3k2-k3+2

(5)

若k2-k3≤2q-1,則f(q)=2k2-q(2k2-2k3-4q-4)單調遞增。

情形1:q=2。

若k2-k3≥6=2q+2>4=2q,則由(4)式得

W(U*)-W(U1)≥2k2-1(k2-k3-6)-(k2+k3)-4+2k3(k2-k3+4)+

n1(k2-k3-1)+3k2-k3+2

≥2k3(2k2-k3-1(k2-k3-6)+2(k2-k3)+3)+2(k2-k3-1)

>0

(6)

結果(2)得證。

情形2:3≤q≤k2。

情形2.1:q=3。

若k2-k3≥8=2q+2>6=2q,則由(6)式可知,W(U*)-W(U1)>0。

若k2-k3=7=2q+1>6=2q,則由(4)式得

W(U*)-W(U1)≥2k2-1(k2-k3-6)+2k2-3(k2-k3-10)+2k3(k2-k3+4)+

n1(k2-k3-1)+3k2-k3+2

>2k3(2k2-k3-3(5k2-5k3-34)+2(k2-k3)+3)>0

(7)

情形2.2:4≤q≤k2。

若k2-k3≥2q+2≥10,則由(6)式可知,W(U*)-W(U1)>0。

若k2-k3=2q+1≥9,則由(7)式可知,W(U*)-W(U1)>0。

若k2-k3=2q≥8,則由(4)式得

W(U*)-W(U1)≥2k2-1(k2-k3-6)+2k2-4(k2-k3-12)+2k3(k2-k3+4)+

n1(k2-k3-1)+3k2-k3+2

>2k3(2k2-k3-4(9k2-9k3-60)+2(k2-k3)+3)>0。

若7≤k2-k3≤2q-1,則由(5)式得

W(U*)-W(U1)≥2k2-1(k2-k3-6)+2k2-3(k2-k3-10)+2k3(k2-k3+4)+

n1(k2-k3-1)+3k2-k3+2

>2k3(2k2-k3-3(5k2-5k3-34)+2(k2-k3)+3)>0.

結果(3)得證。

證畢。

定理2設U*是U(3,3)中具有極小Wiener指數的圖,階數n≥13,其各個分支的層數滿足k2≥k1≥k3>0,則

1)若1≤m3≤2k3-1-1,m2=1,則k2-k3≤4。

2)若1≤m3≤2k3-1-1,2k2-2

3)若1≤m3≤2k3-1-1,2≤m2≤2k2-2,則k2-k3≤5。

定理2的證明記圖變換后的圖為U1。易知n1≥2k3。令m2=1,若k2-k3≥5,則代入(2)式得

W(U*)-W(U1)≥2k2-1(k2-k3-5)+2k3-1(k2-k3+5)+2(k2-k3)+m3(k2-k3+3)+n1(k2-k3)>0。

結果(1)得證。

令m2=2k2-q+a(2≤q≤k2,1≤a≤2k2-q),l=k2-q,代入(2)式,

W(U*)-W(U1)

≥2k2-1(k2-k3-5)+2k3-1(k2-k3+5)-(2k2-q+a-1)(k2+k3-1)+

4+2k2-q+1(k2-q-2)+2a(k2-q)+2(k2-k3)+m3(k2-k3+3)+n1(k2-k3)

=2k2-q(2q-1(k2-k3-5)+(k2-k3)-2q-3)+2k3-1(k2-k3+5)+n1(k2-k3)+

a(k2-k3+1-2q)+(m3+1)(k2-k3)+2k2+3(m3+1)

(8)

若k2-k3≥2q-1,則由(8)式得

W(U*)-W(U1)≥2k2-q(2q-1(k2-k3-5)+(k2-k3)-2q-3)+2k3-1(k2-k3+5)+

n1(k2-k3)+(m3+1)(k2-k3)+2k2+3(m3+1)

(9)

若k2-k3≥2q+1,則f(q)=2k2-q(k2-k3-2q-3)單調遞減;若2q-1≤k2-k3≤2q,則f(q)單調遞增。

若k2-k3≤2q-2。則由(8)式得

W(U*)-W(U1)≥2k2-q(2q-1(k2-k3-5)+(k2-k3)-2q-3+k2-k3+1-2q)+

2k3-1(k2-k3+5)+n1(k2-k3)+(m3+1)(k2-k3)+2k2+3(m3+1)

=2k2-q(2q-1(k2-k3-5)+2(k2-k3)-4q-2)+2k3-1(k2-k3+5)+

n1(k2-k3)+(m3+1)(k2-k3)+2k2+3(m3+1)

(10)

若k2-k3≤2q-2,則f(q)=2k2-q(2k2-2k3-4q-2)單調遞增。

情形1:q=2。

若k2-k3≥5=2q+1>3=2q-1,則由(9)式得

W(U*)-W(U1)≥2k2-1(k2-k3-5)-(k2+k3)-3+2k3-1(k2-k3+5)+n1(k2-k3)+

(m3+1)(k2-k3)+2k2+3(m3+1)

>2k3-1(2k2-k3(k2-k3-5)+3(k2-k3)+5)+3(k2-k3+1)>0

(11)

結果(2)得證。

情形2:3≤q≤k2。

情形2.1:q=3。

若k2-k3≥7=2q+1>5=2q-1,則由(11)式可知,W(U*)-W(U1)>0。

若k2-k3=6=2q>5=2q-1,則由(9)式,得

W(U*)-W(U1)≥2k2-1(k2-k3-5)+2k2-3(k2-k3-9)+2k3-1(k2-k3+5)+n1(k2-k3)+

(m3+1)(k2-k3)+2k2+3(m3+1)

>2k3-1(2k2-k3-2(5k2-5k3-29)+3(k2-k3)+5)>0

(12)

情形2.2:4≤q≤k2。

若k2-k3≥2q+1≥9,則由(11)式可知,W(U*)-W(U1)>0。

若k2-k3=2q≥8,則由(12)式可知,W(U*)-W(U1)>0。

若k2-k3=2q-1≥7,則由(9)式得

W(U*)-W(U1)≥2k2-1(k2-k3-5)+2k2-4(k2-k3-11)+2k3-1(k2-k3+5)+

n1(k2-k3)+(m3+1)(k2-k3)+2k2+3(m3+1)

>2k3-1(2k2-k3-3(9k2-9k3-51)+3(k2-k3)+5)>0.

若6≤k2-k3≤2q-2,則由(10)式得

W(U*)-W(U1)≥2k2-1(k2-k3-5)+2k2-3(k2-k3-9)+2k3-1(k2-k3+5)+

n1(k2-k3)+(m3+1)(k2-k3)+2k2+3(m3+1)

>2k3-1(2k2-k3-2(5k2-5k3-29)+3(k2-k3)+5)>0.

結果(3)得證。

證畢。