孫曉慧，安新慧

(新疆大學(xué)數(shù)學(xué)與系統(tǒng)科學(xué)學(xué)院，新疆 烏魯木齊 830017)

0 引言

1947 年,Wiener[1]首次引入連通圖G 的Wiener 指標(biāo)用于研究化學(xué)中石蠟的沸點(diǎn).它是圖G 的所有無序頂點(diǎn)對(duì)之間距離的總和.如果圖G 是連通圖且u,v ∈v(G),則u 和v 之間的距離d(u,v) 是連接u 和v 的最短路徑上的邊數(shù).連通圖G 的Wiener 指標(biāo)W(G) 定義如下:

Entringer 等[2]證明了n 個(gè)頂點(diǎn)的樹的Wiener 指標(biāo)在其為星圖時(shí)達(dá)到最小值(n-1)2,在其為路時(shí)達(dá)到最大值(n3-n)/6.Marraki 和Modabish 證明了n 個(gè)頂點(diǎn)的平面圖的Wiener 指標(biāo)的最小值為(n-2)2+2[3].Che和Collins 證明了當(dāng)圖G 是一個(gè)頂點(diǎn)數(shù)為n ≥3 的Apollonian 網(wǎng)絡(luò)時(shí),Wiener 指標(biāo)的最大值為?(n3+3n2)/18」,并且進(jìn)一步討論了當(dāng)圖G 是頂點(diǎn)數(shù)為3 ≤n ≤10 的極大平面圖的Wiener 指標(biāo)的上界,并猜測(cè)它對(duì)所有n ≥3都成立[4].Ghosh 等證明了上述猜想,并確定了n ≥10 的極大平面圖的Wiener 指標(biāo)為Apollonian 網(wǎng)絡(luò)時(shí)達(dá)到最大值[5].本文中我們主要研究了極大外平面圖的Wiener 指標(biāo)的上下界.

1 預(yù)備知識(shí)

本文僅考慮有限簡(jiǎn)單連通圖,未指定的符號(hào)定義參閱文獻(xiàn)[6].用N(v) 表示頂點(diǎn)v 的鄰點(diǎn)集,基數(shù)|N(v)|是點(diǎn)v 的度數(shù),記為d(v).集合S 的基數(shù)用|S| 表示.圖G 的頂點(diǎn)集用V(G) 表示,其基數(shù)稱為圖G 的階數(shù).如果圖G 中的任意兩個(gè)頂點(diǎn)可通過路徑連接，則稱其為連通圖.對(duì)于點(diǎn)x,y ∈V(G),d(x,y) 表示圖G 中連接x和y 的最短路的長(zhǎng)度.N(x,i) 表示圖G 中與頂點(diǎn)x 的距離為i 的所有點(diǎn)的集合.特別的,當(dāng)i=1 時(shí),N(x,1)是x 的鄰點(diǎn)集并且其基數(shù)等于x 的度數(shù).圖G 中頂點(diǎn)x 的離心率表示x 與圖G 中其它頂點(diǎn)之間的最大距離,記為e(x).圖G 的直徑是所有頂點(diǎn)離心率的最大值,用diam(G) 表示.

定義1用W(x,G) 表示頂點(diǎn)x 和圖G 中其它頂點(diǎn)之間所有距離的總和,即

圖G 的Wiener 指標(biāo)W(G) 表示G 中的無序頂點(diǎn)對(duì)之間的所有距離之和.圖G 的Wiener 指標(biāo)還可以表示為:

定義2外平面圖是具有平面嵌入的平面圖,其中每個(gè)頂點(diǎn)位于外部區(qū)域的邊界上.若通過添加邊獲得的圖不是外平面圖,則此時(shí)的外平面圖是極大外平面圖.

對(duì)于給定的圖G,我們使用G-x 表示通過刪除頂點(diǎn)x 得到的圖形.兩個(gè)圖G1和G2的連接,用G1∨G2表示,即將圖G1中的每個(gè)頂點(diǎn)與圖G2中每個(gè)頂點(diǎn)連接.我們首先給出極大外平面圖的一些簡(jiǎn)單性質(zhì).

引理1設(shè)圖G 是n 個(gè)頂點(diǎn)的極大外平面圖(n ≥3),則

(i) 圖G 中至少有兩個(gè)2 度頂點(diǎn).

(ii) 如果d(v)=2,那么圖G-v 也是極大外平面圖.

(iii) 圖G 恰好有2n-3 條邊.

定義3設(shè)P2n是通過將路Pn中所有距離為2 的頂點(diǎn)對(duì)之間連邊后得到的圖.

引理2[7]設(shè)圖G 是n 個(gè)頂點(diǎn)的極大外平面圖,其中n ≥5.若v 為圖G 中1 個(gè)度為2 的點(diǎn),并且其鄰點(diǎn)為u 和w,則d(u)+d(w)≥7,等號(hào)成立當(dāng)且僅當(dāng)G[N(u)∪N(w)]～=P25.

當(dāng)n ≥3 時(shí),令Hn表示n 個(gè)頂點(diǎn)的所有非同構(gòu)的極大外平面圖的集合.當(dāng)n ∈{3,4,5},Hn包含唯一確定的圖C3,H1,H2,如圖1 所示.

圖1 C3,H1=P24,H2=P25

當(dāng)n=6 時(shí),H6={H′1,H′2,H′3} (如圖2 所示).通過直接計(jì)算,可以得到

圖2 H′1=K1 ∨P5,H′2,H′3=P26

W(H′1)=21,W(H′2)=21,W(H′3)=22.

在本文中,我們給出了極大外平面圖的Wiener 指標(biāo)的上下界,并刻畫了相應(yīng)的極圖.

2 極大外平面圖的Wiener 指標(biāo)的下界

在本節(jié)中,我們將確定極大外平面圖的Wiener 指標(biāo)的下界,并刻畫相應(yīng)的極圖.

引理3階數(shù)n ≥7 的極大外平面圖G 的直徑為2 當(dāng)且僅當(dāng)G ～=K1∨Pn-1.

證明顯然,K1∨Pn-1是一個(gè)極大外平面圖,并且直徑為2.下面假設(shè)圖G 是直徑為2 且n ≥7 的極大外平面圖.由引理1 可知,在圖G 中存在v0∈V(G),它的度數(shù)d(v0)=2.設(shè)N(v0)={u0,w0}.由于圖G 的直徑是2,對(duì)于任何y ∈V(G){v0,u0,w0},有d(v0,y)=2.如果d(u0)=n-1 或d(w0)=n-1,則G ～=K1∨Pn-1.下面考慮如果d(u0)

定理1設(shè)圖G 為頂點(diǎn)數(shù)n ≥7 的極大外平面圖,則W(G)≥n2-3n+3,等式成立當(dāng)且僅當(dāng)G ～=K1∨Pn-1.

證明當(dāng)圖G 為極大外平面圖且v ∈V(G),有

因此,可得

等式(1) 和等式(2) 成立當(dāng)且僅當(dāng)對(duì)任意u,v ∈V(G),有d(u,v)≤2.由于n ≥7,根據(jù)引理3,等式成立當(dāng)且僅當(dāng)G ～=K1∨Pn-1.

3 極大外平面圖的Wiener 指標(biāo)的上界

在本節(jié)中,我們將確定極大外平面圖的Wiener 指標(biāo)的上界,并刻畫相應(yīng)的極圖.

圖3 為n 分別是偶數(shù)和奇數(shù)時(shí)的P2n的結(jié)構(gòu).

圖3 P22k 和P22k-1

引理4[8]設(shè)Pn為頂點(diǎn)數(shù)n ≥3 的路,則

引理5[9]每個(gè)階數(shù)至少為3 的極大外平面圖都是2 連通的.

引理6設(shè)圖G 為n 個(gè)頂點(diǎn)的2 連通圖,則diam(G)≤?n/2」.

證明設(shè)x 是圖G 中的頂點(diǎn),e(x)=t,其中t>1.

注意,N(x,i) 對(duì)于0 ≤i ≤t 是兩兩不相交的,并且形成了圖G 的頂點(diǎn)集的一個(gè)劃分,從而

顯然|N(x,0)|=1.當(dāng)1 ≤i ≤t-1 時(shí),N(x,i)是圖G 的一個(gè)頂點(diǎn)割.由于圖G 是2 連通的,對(duì)于1 ≤i ≤t-1有|N(x,i)|≥2.因此,n ≥2(t-1)+2=2t.那么e(x)=t ≤?n/2」,所以

引理7設(shè)圖G 是n 個(gè)頂點(diǎn)的2 連通圖.如果v ∈V(G) 且d(v)=2,那么

證明對(duì)n 個(gè)頂點(diǎn)的2 連通圖G,有

因?yàn)閨N(v,i)|≥2 (1 ≤i ≤t-1),

由于-t2+tn 在t 接近n/2 的整數(shù)處最大化,則

引理7 得證.

定理2設(shè)圖G 為頂點(diǎn)數(shù)n ≥2 的極大外平面圖,則

等式成立當(dāng)且僅當(dāng)G ～=P2n.

證明設(shè)圖G 是n 個(gè)頂點(diǎn)的極大外平面圖.當(dāng)n ≤5 時(shí),顯然圖G 存在唯一的極大外平面圖同構(gòu)于P2n.

當(dāng)n=6 時(shí),由圖2 可知,只有三個(gè)不同構(gòu)的極大外平面圖H′1,H′2,H′3.通過簡(jiǎn)單計(jì)算可得,W(H′1)=21,W(H′2)=21,W(H′3)=22.由于H′3～=P26,所以n=6 時(shí),結(jié)果成立.

當(dāng)n ≥7 時(shí),我們對(duì)頂點(diǎn)數(shù)n 使用數(shù)學(xué)歸納法證明,若G ?P2n,則W(G)

情況1 圖G 至少有三個(gè)2 度頂點(diǎn).

圖G 存在兩個(gè)2 度頂點(diǎn),記為u 和v,使得d(u,v)

情況2 圖G 恰好有兩個(gè)2 度頂點(diǎn).

圖G 的兩個(gè)2 度頂點(diǎn)記為u 和v,由于G ?P2n,因此至少存在一個(gè)頂點(diǎn)w,其度數(shù)至少為5.因此,圖G-u和G-v 中的至少有一個(gè)與Pn2-1不同構(gòu).不失一般性,假設(shè)G-u ?,因此設(shè)G′～=G-u.

由于圖G′是一個(gè)頂點(diǎn)數(shù)為n-1 的極大外平面圖,且G′?,根據(jù)歸納假設(shè),W(G′)

由于

將式(3) 代入式(4) ,利用引理7,我們得到

定理得證.