王艷秋,葉永升
(淮北師范大學 數學科學學院,安徽 淮北 235000)
連通圖的一個pebbling是一些pebble在這個圖的頂點上的一種放置方式,一個pebbling移動是從一個頂點上移走兩個pebble,扔掉其中的一個而把另一個移到與其相鄰的一個頂點上.圖G的一個頂點v的pebbling數是最小的數f(G,v),滿足從G的頂點上f(G,v)個pebble的任意一種放置開始,總可以通過一系列的pebbling移動把一個pebble移到頂點v上.圖G的pebbling數記為f(G),是對G的所有頂點v來說f(G,v)的最大值.
對于pebbling 數f(G)已經得到了一些結果(見文獻[1-4]),如果除頂點v之外每一個頂點上都只放置一個pebble,則沒有一個pebble 能夠移到v上,另外,如果頂點w與v的距離為d,且2d-1 個pebble放置在w上,則也不能把一個pebble移到v上,所以有f(G)≥max{|V(G)|, 2d} .這里|V(G)|表示圖G的頂點個數,而d為圖G的直徑.
給定G的一種pebbling,G的一個傳送子圖是一條路x0,x1,…,xk,使得在頂點x0上至少有2 個pebbles,且除了可能xk外的其他頂點上至少有1個pebble.這時可以把1個pebble從x0傳送到xk.
扇圖Fn是一條路Pn-1加上另一個頂點,此頂點與路Pn-1的每個頂點都相鄰.輪圖Wn是一個圈Cn-1再加上與此圈中每個頂點都相鄰的一個頂點.
下面我們給出幾個圖的定義:
定義1設Fn是由頂點v1,v2,…,vn-1的路再加上與此路中的每個頂點都相鄰的一個頂點v0,另有路Pk=u1u2…uk,連接v0與uk,便得到Fn?Pk.
定義2設Wn是由頂點v1,v2,…,vn-1的圈Cn-1再加上與此圈中每個頂點都相鄰的一個頂點v0,另有路Pk=u1u2…uk,連接v0與uk便得到Wn?Pk.
定義3設Wm是由頂點a1,a2,…,am-1的圈Cm-1再加上與此圈中每個頂點都相鄰的一個頂點a0,Wn是由頂點b1,b2,…,bn-1的圈Cn-1再加上與此圈中每個頂點都相鄰的一個頂點b0,路Pk-1=w1w2…wk-1,分別連接a0與w1,b0與wk-1,便得到Wm?Pk-1?Wn,此圖被稱為雙輪圖.
文獻[2]給出了扇圖和輪圖的pebbling數,f(Fn)=n和f(Wn)=n.文獻[3]給出了偶圈圖的pebbling數,f(C2n)=2n.文獻[4]證明了完全二部圖的pebbling 數,f(Km,n)=m+n.文獻[5]給出了f(C2n?Pm)=2m+n,f(C2n?Pk-1?C2m)=2m+n+k,f(Pk?C2n?Pm)=2m+n+k.本文研究了圖Fn?Pk,Wn?Pk和雙輪圖Wm?Pk-1?Wn的pebbling數.
本文考慮的圖都是簡單無向連通圖,設圖G的頂點集為V(G),邊集為E(G).給定G的pebble 的一個分配,對G的任意頂點v.p(v)代表v上的pebble的個數.為放置在G的頂點上的pebble 個數.
在這一部分,首先給出Fn?Pk的pebbling 數,在此基礎上得出Wn?Pk的pebbling 數,最后研究了Wm?Pk-1?Wn的pebbling數.為定理的證明,先給出下面的引理:
引理[1]f(Pn)=2n-1,其中Pn為n個頂點的路.
定理1f(Fn?Pk)=n+2k+1-2(n≥5,k≥2).
證明如果p(v2)=p(v3)=…=p(vn-1)=1,p(v1)=2k+1-1,那么Fn?Pk被放置n+2k+1-3 個pebble,可是頂點u1無法得到一個pebble.所以f(Fn?Pk)≥n+2k+1-2.下面證明f(Fn?Pk)≤n+2k+1-2.
(1)設p(v0)=0,如果任意vi,p(vi)≥2(i≠0),則可移動一個pebble 給v0.若p(vi)≤1(i≠0),則至少有n+2k+1-2-(n-1)=2k+1-1(>2k)個pebble 放在路u1,u2,…,uk,v0上,由引理知,可以移動一個pebble給v0.
(2)設p(vi)=0(1≤i≤n-1),不妨設p(v1)=0,如果p(v0)≥2 或p(v2)≥2 或p(vi)≥4(3≤i≤n-1),則v1均可得到一個pebble.否則,p(v0)≤1且p(v2)≤1且p(vi)≤3(3≤i≤n-1),此時有以下情形:
(2.1)當p(v0)=1 時,如果 2≤p(vi)≤3,那么{vi,v0,v1} 成傳送子圖;如果p(vi)≤1,那么至少有n+2k+1-2-(n-2)+1(=2k+1+1)個pebble 放在路u1,u2,…,uk,v0,v1上,由引理可知,可以移動一個pebble給v1.
(2.2)當p(v0)=0 時,如果2≤p(vi)≤3,那么任意兩個頂點vi,vj(3≤i,j≤n-1)可分別給v0一個peb?ble,v0再給v1一個;如果p(vi)≤1,則至少有n+2k+1-2-(n-2)=2k+1個 pebble 放在路u1,u2,…,uk,v0,v1上,那么可移動一個pebble給v1.
(3)設p(ui0)=0(1≤i0≤k), 記A={u1,u2,…,uk,v0} ,B={v1,v2,…,vn-1} .設p(A)≥p(B)且p(A)-p(B)=p,其中 0≤p≤n+2k+1-2,又由于p(A)+p(B)=n+2k+1-2,可知,n和p同時為奇數或偶數,故有
B至少可以移給v0的pebble個數為,則A中的pebble個數至少為
所以可以移給ui0一個pebble.
如果p(B)>p(A)且p(B)-p(A)=q(0<q≤n+2k+1-2),則n和p同奇同偶,并且若n和q均為偶數,則n+2k+1-2 也為偶數,有以下情形:
當q=n+2k+1-2 時,即把n+2k+1-2 全放在B中,此時p(B)=n+2k+1-2,則B至少可以給頂點v0的pebble個數為,所以A中至少有2k個pebble,可以移給ui0一個pebble.
當 0<q≤n+2k+1-4,B至少可以給頂點v0的pebble 個數為則移動之后A中的pebble個數至少為
所以可以移給ui0一個pebble.
當n和q均為奇數時,情況與上面類似,ui0也可以得到一個pebble.綜上所述,
推論f(Wn?Pk)=n+2k+1-2(n≥5,k≥2).
證明由于圖Fn?Pk是圖Wn?Pk的生成子圖,故f(Wn?Pk)≤n+2k+1-2.如果p(v2)=p(v3)=…=p(vn-1)=1,p(v1)=2k+1-1,那么Wn?Pk被放置n+2k+1-3 個pebble,可是頂點u1無法得到一個pebble.所以f(Wn?Pk)≥n+2k+1-2.因此f(Wn?Pk)=n+2k+1-2(n≥5,k≥2).
定理2f(Wm?Pk-1?Wn)=m+n+2k+2-4(m≥5,n≥5).
證 明如果p(a2)=p(a3)=…=p(am-1)=1,p(b1)=2k+2-1,p(b2)=p(b3)=…=p(bn-1)=1.那么Wm?Pk-1?Wn被放置m+n+2k+2-5 個 pebble,頂點a1無法得到pebble,因此f(Wm?Pk-1?Wn)≥m+n+2k+2-4.下面我們證明f(Wm?Pk-1?Wn)≤m+n+2k+2-4.
首先,設目標頂點為a0,即p(a0)=0.
令A={a1,a2,…,am-1},B={a0,w1,w2,…,wk-1,b0,b1,…,bn-1} .若對于某個ai(i≠ 0),有p(ai)≥2,則a0可得一個pebble.若對于所有的ai(i≠ 0),p(ai)≤1,則至少有
個pebble放在B中,由推論可知,a0可得一個pebble.
其次,設目標頂點為ai(i≠0),不失一般性,設p(a1)=0.若p(a0)≥2 或p(ai)≥4(i≠ 0,1,2,m-1)或p(a2)≥2 或p(am-1)≥2.則{a0,a1} 或{ai,a0,a1} 或{a2,a1} 或{am-1,a1} 成傳送子圖,a1可得一個pebble.否則,p(a0)≤1且p(ai)≤3(i≠ 0,1,2,m-1)且p(a2)≤1且p(am-1)≤1,我們有以下情形:
(1)當p(a0)=1 時,如果p(ai)≥2,則{ai,a0,a1} 成傳送子圖,可移給a1一個pebble;如果p(ai)≤1,則至少有
個pebble放在B中,則a0可以得到一個pebble,之后a0可以給a1一個.
(2)當p(a0)=0 時,如果p(ai)≥2,則任意兩個頂點ai,aj(i,j≠0,1,2,m-1)可分別給a0一個pebble,a0得到兩個pebble后可給a1一個;如果p(ai)≤1,則至少有m+n+2k+2-4-(m-2)=n+2k+2-2 個pebble放在B中,此時令C={a0,w1,w2,…,wk-1,b0},D={b1,b2,…,bn-1} .
設p(C)≥p(D)且p(C)-p(D)=s(0≤s≤n+2k+2-2),由于p(C)+p(D)=n+2k+2-2,可以知道,n和s同時為奇數或偶數.所以有D至少可以移給b的pebble0個數為則移動之后C中的pebble個數至少為
所以可以移給a0兩個pebble,那么a1可以從a0處得到一個pebble.
設p(C)<p(D)且p(C)-p(D)=t(0≤t≤n+2k+2-2),同樣,n和t亦同奇同偶,并且
若n和t同為偶數,則n+2k+2-2 為偶數.
當t=n+2k+2-2 時,即n+2k+2-2 個pebble全部放在D中,此時D至少可移給b0的pebble個數為
則可移給a0兩個pebble,那么a1可以從a0處得到一個pebble.
當 0≤t≤n+2k+2-4 時,D至少可以移給b0的 pebble 個數為則移動之后C中的pebble個數至少為
所以可移給a0兩個pebble,那么a1可以從a0處得到一個pebble.
若n和t同為偶數,情況與此類似.
最后,設目標頂點為wi(1≤i≤k-1),不失一般性,設為wi0,即p(wi0)=0.令
由推論知,f(A′)=m+2i0+1-2,f(B′)=n+2k-i0+1-2.由于f(A′)+f(B′)≤m+n+2k+2-4,所以必有p(A′)≥f(A′)或p(B′)≥f(B′),因此,wi0總會得到一個pebble.
綜上,f(Wm?Pk-1?Wn)=m+n+2k+2-4(m≥5,n≥5).
[1]CHUNG F R K.Pebbling in hypercubes[J].SIAMJ Discrete Math,1989,2(4):467-472.
[2]FENG R Q,KIM J Y.Pebbling numbers of some graphs[J].Science in China(Series A),2002,45(4):470-478.
[3]PACHTER L,SNEVILY S,VOXMAN B.On pebbling graphs[J].Congr Numer,1995,107:65-80.
[4]馮榮權,金珠英.完全二部圖乘積上的Graham pebbling猜想[J].中國數學(A輯),2001,31(3):199-203.
[5]高澤圖,尹建華.幾類二部圖的pebbling數[J].高校應用數學學報,2010,25(3):365-371.