王艷秋，葉永升

（淮北師范大學(xué) 數(shù)學(xué)科學(xué)學(xué)院，安徽 淮北 235000）

1 基本概念

連通圖的一個(gè)pebbling是一些pebble在這個(gè)圖的頂點(diǎn)上的一種放置方式，一個(gè)pebbling移動(dòng)是從一個(gè)頂點(diǎn)上移走兩個(gè)pebble，扔掉其中的一個(gè)而把另一個(gè)移到與其相鄰的一個(gè)頂點(diǎn)上.圖G的一個(gè)頂點(diǎn)v的pebbling數(shù)是最小的數(shù)f(G,v)，滿足從G的頂點(diǎn)上f(G,v)個(gè)pebble的任意一種放置開始，總可以通過一系列的pebbling移動(dòng)把一個(gè)pebble移到頂點(diǎn)v上.圖G的pebbling數(shù)記為f(G)，是對(duì)G的所有頂點(diǎn)v來說f(G,v)的最大值.

對(duì)于pebbling 數(shù)f(G)已經(jīng)得到了一些結(jié)果（見文獻(xiàn)［1-4］），如果除頂點(diǎn)v之外每一個(gè)頂點(diǎn)上都只放置一個(gè)pebble，則沒有一個(gè)pebble 能夠移到v上，另外，如果頂點(diǎn)w與v的距離為d，且2d-1 個(gè)pebble放置在w上，則也不能把一個(gè)pebble移到v上，所以有f(G)≥max{|V(G)|, 2d} .這里|V(G)|表示圖G的頂點(diǎn)個(gè)數(shù)，而d為圖G的直徑.

給定G的一種pebbling，G的一個(gè)傳送子圖是一條路x0,x1,…,xk，使得在頂點(diǎn)x0上至少有2 個(gè)pebbles，且除了可能xk外的其他頂點(diǎn)上至少有1個(gè)pebble.這時(shí)可以把1個(gè)pebble從x0傳送到xk.

扇圖Fn是一條路Pn-1加上另一個(gè)頂點(diǎn)，此頂點(diǎn)與路Pn-1的每個(gè)頂點(diǎn)都相鄰.輪圖Wn是一個(gè)圈Cn-1再加上與此圈中每個(gè)頂點(diǎn)都相鄰的一個(gè)頂點(diǎn).

下面我們給出幾個(gè)圖的定義：

定義1設(shè)Fn是由頂點(diǎn)v1,v2,…,vn-1的路再加上與此路中的每個(gè)頂點(diǎn)都相鄰的一個(gè)頂點(diǎn)v0，另有路Pk=u1u2…uk，連接v0與uk，便得到Fn?Pk.

定義2設(shè)Wn是由頂點(diǎn)v1,v2,…,vn-1的圈Cn-1再加上與此圈中每個(gè)頂點(diǎn)都相鄰的一個(gè)頂點(diǎn)v0，另有路Pk=u1u2…uk，連接v0與uk便得到Wn?Pk.

定義3設(shè)Wm是由頂點(diǎn)a1,a2,…,am-1的圈Cm-1再加上與此圈中每個(gè)頂點(diǎn)都相鄰的一個(gè)頂點(diǎn)a0，Wn是由頂點(diǎn)b1,b2,…,bn-1的圈Cn-1再加上與此圈中每個(gè)頂點(diǎn)都相鄰的一個(gè)頂點(diǎn)b0，路Pk-1=w1w2…wk-1，分別連接a0與w1，b0與wk-1，便得到Wm?Pk-1?Wn，此圖被稱為雙輪圖.

文獻(xiàn)［2］給出了扇圖和輪圖的pebbling數(shù)，f(Fn)=n和f(Wn)=n.文獻(xiàn)［3］給出了偶圈圖的pebbling數(shù)，f(C2n)=2n.文獻(xiàn)［4］證明了完全二部圖的pebbling 數(shù)，f(Km,n)=m+n.文獻(xià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數(shù).

本文考慮的圖都是簡單無向連通圖，設(shè)圖G的頂點(diǎn)集為V(G)，邊集為E(G).給定G的pebble 的一個(gè)分配，對(duì)G的任意頂點(diǎn)v.p(v)代表v上的pebble的個(gè)數(shù).為放置在G的頂點(diǎn)上的pebble 個(gè)數(shù).

2 主要結(jié)論

在這一部分，首先給出Fn?Pk的pebbling 數(shù)，在此基礎(chǔ)上得出Wn?Pk的pebbling 數(shù)，最后研究了Wm?Pk-1?Wn的pebbling數(shù).為定理的證明，先給出下面的引理：

引理［1］f(Pn)=2n-1，其中Pn為n個(gè)頂點(diǎ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 個(gè)pebble，可是頂點(diǎn)u1無法得到一個(gè)pebble.所以f(Fn?Pk)≥n+2k+1-2.下面證明f(Fn?Pk)≤n+2k+1-2.

（1）設(shè)p(v0)=0，如果任意vi，p(vi)≥2(i≠0)，則可移動(dòng)一個(gè)pebble 給v0.若p(vi)≤1(i≠0)，則至少有n+2k+1-2-(n-1)=2k+1-1(＞2k)個(gè)pebble 放在路u1,u2,…,uk,v0上，由引理知，可以移動(dòng)一個(gè)pebble給v0.

（2）設(shè)p(vi)=0(1≤i≤n-1)，不妨設(shè)p(v1)=0，如果p(v0)≥2 或p(v2)≥2 或p(vi)≥4(3≤i≤n-1)，則v1均可得到一個(gè)pebble.否則，p(v0)≤1且p(v2)≤1且p(vi)≤3(3≤i≤n-1)，此時(shí)有以下情形：

（2.1）當(dāng)p(v0)=1 時(shí)，如果 2≤p(vi)≤3，那么{vi,v0,v1} 成傳送子圖；如果p(vi)≤1，那么至少有n+2k+1-2-(n-2)+1(=2k+1+1)個(gè)pebble 放在路u1,u2,…,uk,v0,v1上，由引理可知，可以移動(dòng)一個(gè)pebble給v1.

（2.2）當(dāng)p(v0)=0 時(shí)，如果2≤p(vi)≤3,那么任意兩個(gè)頂點(diǎn)vi,vj(3≤i,j≤n-1)可分別給v0一個(gè)peb?ble，v0再給v1一個(gè)；如果p(vi)≤1,則至少有n+2k+1-2-(n-2)=2k+1個(gè) pebble 放在路u1,u2,…,uk,v0,v1上，那么可移動(dòng)一個(gè)pebble給v1.

（3）設(shè)p(ui0)=0(1≤i0≤k), 記A={u1,u2,…,uk,v0} ,B={v1,v2,…,vn-1} .設(shè)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同時(shí)為奇數(shù)或偶數(shù)，故有

B至少可以移給v0的pebble個(gè)數(shù)為，則A中的pebble個(gè)數(shù)至少為

所以可以移給ui0一個(gè)pebble.

如果p(B)＞p(A)且p(B)-p(A)=q(0＜q≤n+2k+1-2)，則n和p同奇同偶，并且若n和q均為偶數(shù)，則n+2k+1-2 也為偶數(shù)，有以下情形：

當(dāng)q=n+2k+1-2 時(shí)，即把n+2k+1-2 全放在B中，此時(shí)p(B)=n+2k+1-2，則B至少可以給頂點(diǎn)v0的pebble個(gè)數(shù)為，所以A中至少有2k個(gè)pebble，可以移給ui0一個(gè)pebble.

當(dāng) 0＜q≤n+2k+1-4，B至少可以給頂點(diǎn)v0的pebble 個(gè)數(shù)為則移動(dòng)之后A中的pebble個(gè)數(shù)至少為

所以可以移給ui0一個(gè)pebble.

當(dāng)n和q均為奇數(shù)時(shí)，情況與上面類似，ui0也可以得到一個(gè)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 個(gè)pebble，可是頂點(diǎn)u1無法得到一個(gè)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 個(gè) pebble，頂點(diǎn)a1無法得到pebble，因此f(Wm?Pk-1?Wn)≥m+n+2k+2-4.下面我們證明f(Wm?Pk-1?Wn)≤m+n+2k+2-4.

首先，設(shè)目標(biāo)頂點(diǎn)為a0，即p(a0)=0.

令A(yù)={a1,a2,…,am-1}，B={a0,w1,w2,…,wk-1,b0,b1,…,bn-1} .若對(duì)于某個(gè)ai(i≠ 0)，有p(ai)≥2，則a0可得一個(gè)pebble.若對(duì)于所有的ai(i≠ 0)，p(ai)≤1，則至少有

個(gè)pebble放在B中，由推論可知，a0可得一個(gè)pebble.

其次，設(shè)目標(biāo)頂點(diǎn)為ai(i≠0)，不失一般性，設(shè)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可得一個(gè)pebble.否則，p(a0)≤1且p(ai)≤3(i≠ 0,1,2,m-1)且p(a2)≤1且p(am-1)≤1，我們有以下情形：

（1）當(dāng)p(a0)=1 時(shí)，如果p(ai)≥2，則{ai,a0,a1} 成傳送子圖，可移給a1一個(gè)pebble；如果p(ai)≤1，則至少有

個(gè)pebble放在B中，則a0可以得到一個(gè)pebble，之后a0可以給a1一個(gè).

（2）當(dāng)p(a0)=0 時(shí)，如果p(ai)≥2，則任意兩個(gè)頂點(diǎn)ai,aj(i,j≠0,1,2,m-1)可分別給a0一個(gè)pebble，a0得到兩個(gè)pebble后可給a1一個(gè)；如果p(ai)≤1，則至少有m+n+2k+2-4-(m-2)=n+2k+2-2 個(gè)pebble放在B中，此時(shí)令C={a0,w1,w2,…,wk-1,b0}，D={b1,b2,…,bn-1} .

設(shè)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同時(shí)為奇數(shù)或偶數(shù).所以有D至少可以移給b的pebble0個(gè)數(shù)為則移動(dòng)之后C中的pebble個(gè)數(shù)至少為

所以可以移給a0兩個(gè)pebble，那么a1可以從a0處得到一個(gè)pebble.

設(shè)p(C)＜p(D)且p(C)-p(D)=t(0≤t≤n+2k+2-2)，同樣，n和t亦同奇同偶,并且

若n和t同為偶數(shù)，則n+2k+2-2 為偶數(shù).

當(dāng)t=n+2k+2-2 時(shí)，即n+2k+2-2 個(gè)pebble全部放在D中，此時(shí)D至少可移給b0的pebble個(gè)數(shù)為

則可移給a0兩個(gè)pebble，那么a1可以從a0處得到一個(gè)pebble.

當(dāng) 0≤t≤n+2k+2-4 時(shí)，D至少可以移給b0的 pebble 個(gè)數(shù)為則移動(dòng)之后C中的pebble個(gè)數(shù)至少為

所以可移給a0兩個(gè)pebble，那么a1可以從a0處得到一個(gè)pebble.

若n和t同為偶數(shù)，情況與此類似.

最后，設(shè)目標(biāo)頂點(diǎn)為wi(1≤i≤k-1)，不失一般性，設(shè)為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總會(huì)得到一個(gè)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］馮榮權(quán)，金珠英.完全二部圖乘積上的Graham pebbling猜想［J］.中國數(shù)學(xué)（A輯），2001，31（3）：199-203.

［5］高澤圖，尹建華.幾類二部圖的pebbling數(shù)［J］.高校應(yīng)用數(shù)學(xué)學(xué)報(bào)，2010，25（3）：365-371.