輪圖中間圖的pebbling數(shù)

史彩霞，葉永升，高 潔，程 芳

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

圖的pebbling 數(shù)問題首先是由Chung討論的，考慮一個連通圖G并有一定數(shù)目的pebble放置在這個圖G的頂點上，一個pebbling移動是從一個頂點上移走2個pebble，把其中的一個移到與其相鄰的一個頂點上.圖G的一個頂點v的pebbling數(shù)f（G，v）是最小的正整數(shù)f（G，v），滿足從G的頂點上f（G，v）個pebble的任何一種放置開始，總可以通過一系列的pebbling移動把一個pebble移到v上.圖G的pebbling數(shù)f（G）是對圖G的所有頂點v來說f（G，v）的最大值.

在圖G中，如果除了v以外其他點最多放一個pebble，那么沒有一個pebble 移到v.另外，如果頂點u和v的距離為d且至多將2d-1 個pebble 放在u上，那么也不能把一個pebble 移到v上，因此f（G）≥max｛|V（G）|，2D｝，這里|V（G）|表示圖G的頂點個數(shù)，而D為圖G的直徑.G的一個傳送子圖是一條路x0，x1，…，xk，使得在頂點x0上至少有2個pebble，且通過一系列的pebbling移動可以把一個pebble從x0傳送到xk.在一個傳送子圖中，頂點xi上的一個pebble 等效于x0上放置2i個pebble.為了下文證明需要，我們引用下述4個引理：

引理 1［1］在一條路x0，x1，…，xk上，設p（x0）+2p（x1）+…+2ip（xi）+…+2k-1p（xk-1）≥2k，則路x0，x1，…，xk是一個傳送子圖.

引理2［1］設C2n+1=v0v1…v2nv0，邊viv（i+1）mod（2n+1）的插入點為ui（i=0，1，2，…，2n），把C2n+1的相鄰邊上的插入點相連，便構(gòu)成了f（M（C2n+1））.

引理3具有3個頂點的扇圖，記為F3，是一條路P2加上另一個頂點v0，此頂點v0與路P2的兩個頂點都相鄰，這里P2=v1v2，在P2上插入點u12，在邊v0v1，v0v2上分別插入點u01，u02，再將u01，u02，u12兩兩相連，便得扇圖F3的中間圖（M（F3））.對于（M（F3））容易驗證f（M（F3））=7.

引理4［2］f（Kn）=n，其中Kn為n個頂點的完全圖.

定義5輪圖的中間圖M（Wn）：具有n個頂點的輪圖，記為Wn，是一個圈Cn-1加上中間一個頂點v0，此頂點v0與圈Cn-1的每個頂點都相鄰，這里Cn-1=v1v2…vn-1.在Cn-1邊上依次插入點u12，u23，…，u（n-2）（n-1），分別在邊v0v1，v0v2，…，v0vn-1上插入點u01，u02，…，u0（n-1），再將Wn的相鄰邊上的插入點相連.

在文獻［3］中，Akiyama 等人給出圖G的中間圖（middle graph）的定義，即：圖G的中間圖M（G）就是在G的每一條邊上插入一個新點，再把G上相鄰邊上的新點用一條邊連接起來.Chung［2］給出n-立方體Qn、完全圖Kn和路Pn的 pebbling 數(shù)；Pachter［4］研究了圈Cn的 pebbling 數(shù)；扇圖Fn和輪圖Wn的 pebbling 數(shù)是馮榮權(quán)等在文獻［5］中給出的；在文獻［6］中，劉海英等已經(jīng)證明路、完全圖和星圖的中間圖的pebbling數(shù).在文獻［1］中，葉永升等已經(jīng)證明圈的中間圖的pebbling 數(shù).本文我們討論輪圖的中間圖M（Wn）的pebbling數(shù).

在本文中，設圖G為一個簡單連通圖，對于G的一種pebbling 分布，p（v）表示放置在頂點v上的peb?bling數(shù).而用p(v)表示G的頂點v通過一系列pebbling移動所具有的pebbling數(shù).

1 輪圖中間圖的pebbling數(shù)

在這一部分，首先證明W4的中間圖M（W4）的pebbling數(shù)，然后證明了Wn，n≥4的中間圖M（Wn）的peb?bling數(shù).

定理6f（M（W4））=10.

證明顯然f（M（W4））≥10.現(xiàn)在任意放置10個pebble在M（W4）上.

（1）設目標頂點為點集｛v1，v2，v3，u12，u13，u23｝中任意一點，先設目標頂點為v1，即p（v1）=0.如果p（v0）+p（u01）+p（u02）+p（u03）≤3，去掉v0，u01，u02，u03得M（C3）且至少含有7個pebble，由引理2知，能移一個pebble給v1.如果p（v0）+p（u01）+p（u02）+p（u03）=4，當點集｛v0，u01，u02，u03｝中有一點含有4 個pebble，由引理 1 知，能移一個pebble給v1.當p（v0）=p（u01）=p（u02）=p（u03）=1時，那么點集｛u12，v2，u23，v3，u13｝中至少有一點含有的peb?ble個數(shù)不小于2，由引理1知，能移一個pebble 給v1.否則，點集｛v0，u01，u02，u03｝中至少有一點含有的peb?ble個數(shù)不小于2，那么至少能移一個pebble給｛v1，v2，v3，u12，u13，u23｝，然后去掉v0，u01，u02，u03得M（C3）且至少含有7個pebble，由引理2知，能移一個pebble給v1.如果p（v0）+p（u01）+p（u02）+p（u03）≥6，能移2個pebble給u01，使得p(u01)=2.如果p（v0）+p（u01）+p（u02）+p（u03）=5，當點集｛u12，v2，u23，v3，u13｝中至少有一點含有的peb?ble個數(shù)不小于2，那么至少能移一個pebble給｛v0，u01，u02，u03｝，使得p（v0）+p（u01）+p（u02）+p（u03）≥6.當p（u12）=p（v2）=p（u23）=p（v3）=p（u13）=1 時，點集｛v0，u01，u02，u03｝中至少有一點含有的 pebble 個數(shù)不小于 2，由引理1知，能移一個pebble給v1.當目標頂點為｛v2，v3，u12，u13，u23｝中任意一點時，類似可證.

（2）設目標頂點為點集｛u01，u02，u03｝中任意一點，由對稱性，不妨設目標頂點為u01，即p（u01）=0.如果點集｛v0，u02，u03，v1，u12，u13｝中至少有一點含有的pebble 個數(shù)不小于2，那么能移一個pebble 給u01.下面設點集｛v0，u02，u03，v1，u12，u13｝中任意一點含有的pebble 個數(shù)都不超過1.因為在M（W4）中，v0，u01，u02，u03構(gòu)成完全圖K4，由引理4知，f（K4）=4，所以當p（v0）+p（u01）+p（u02）+p（u03）≥4時，能移一個pebble給u01.當p（v0）+p（u01）+p（u02）+p（u03）=3 時，點集｛v1，v2，v3，u12，u13，u23｝中至少有一點含有的 pebble 個數(shù)不小于 2，那么至少能移一個 pebble 給｛v0，u01，u02，u03｝，使得p（v0）+p（u01）+p（u02）+p（u03）≥4.當p（v0）+p（u01）+p（u02）+p（u03）=2時，如果p（v1）=1，去掉v0，u01，u02，u03得M（C3）且除v1含有一個pebble外，還含有7個pebble，由引理2知，能移一個 pebble 給v1，使得p（v1）=2.如果p（v1）=0，p（u12）=1或p（u13）=1 時，同上.如果p（v1）=p（u12）=p（u13）=1，點集｛v2，u23，v3｝中至少有一點含有的pebble 個數(shù)不小于2，由引理1 知，能移一個pebble 給u01.如果p（v1）=p（u12）=p（u13）=0，｛v2，u23，v3｝至少能移 2 個 pebble 給｛v0，u01，u02，u03｝，使得p（v0）+p（u01）+p（u02）+p（u03）≥4.當p（v0）+p（u01）+p（u02）+p（u03）=1時，如果點集｛v1，u12，u13｝中至少有一點含有一個pebble，同上.如果p（v1）=p（u12）=p（u13）=0，｛v2，u23，v3｝至少能移 3 個 pebble給｛v0，u01，u02，u03｝，使得p（v0）+p（u01）+p（u02）+p（u03）≥4.當p（v0）+p（u01）+p（u02）+p（u03）=0時，如果點集｛v1，u12，u13｝中至少有一點含有一個pebble，類似可證.如果p（v1）=p（u12）=p（u13）=0，此時點集｛v2，u23，v3｝中至少有一點含有的pebble 個數(shù)不小于4，由引理1知，能移一個pebble給u01.

（3）設目標頂點為v0，即p（v0）=0.如果點集｛u01，u02，u03｝中至少有一點含有的pebble個數(shù)不小于2，那么能移一個pebble給v0.因此下面設點集｛u01，u02，u03｝中任意一點含有的pebble個數(shù)都不超過1.當p（v0）+p（u01）+p（u02）+p（u03）≥3 時，同（2）.當p（v0）+p（u01）+p（u02）+p（u03）=2 時，此時要么｛v1，v2，v3，u12，u13，u23｝至少能移 2 個 pebble給｛v0，u01，u02，u03｝，使得p（v0）+p（u01）+p（u02）+p（u03）≥4.要么點集｛v1，v2，v3，u12，u13，u23｝中至少有一點含有的 pebble 個數(shù)不小于2，由引理 1 知，能移一個pebble 給v0.當p（v0）+p（u01）+p（u02）+p（u03）=1 時，點集｛u01，u02，u03｝中某點含有一個pebble，類似于（2）中證明.當p（v0）+p（u01）+p（u02）+p（u03）=0時，如果p（v1）+p（u12）+p（u13）≥6，能移 2個 pebble給u01，使得p（u01）=2.如果p（v1）+p（u12）+p（u13）=5，｛v2，u23，v3｝至少能移一個 pebble 給｛v1，u12，u13｝，使得p（v1）+p（u12）+p（u13）≥6.當p（v1）+p（u12）+p（u13）=4 時，｛v1，u12，u13｝能移一個pebble給｛v2，u23，v3｝，然后去掉u01，v1，u12，u13得M（F3）且含有7個pebble，由引理3知，能移一個pebble給v0.當p（v1）+p（u12）+p（u13）≤3時，去掉u01，v1，u12，u13得M（F3）且至少含有7個pebble，由引理3知，能移一個pebble給v0.

為了便于定理7的證明，在M（Wn）中，例如去掉點v1，u01，u12，使u1（n-1）分別與v2，u23相連接，得M（Wn-1）.在下面的證明過程中，去點得M（Wn-1）與此類似，不再說明.

定理7f（M（Wn））=3n-2 （n≥4）.

證明顯然f（M（Wn））≥3n-2.由定理5 知，當n=4 時命題成立.假設對于k＜n，有f（M（Wk））=3k-2 成立.下證f（M（Wn））=3n-2.現(xiàn)在任意放置3n-2個pebble 在M（Wn）上.下面討論n的奇偶性，當n為偶數(shù)，即n=2r（r≥3）時：

（1）設目標頂點為點集｛v1，v2，…，vn-1｝中任意一點，由對稱性，不妨設目標頂點為v1，即p（v1）=0.如果點集｛u01，u12，u1（n-1）｝中至少有一點含有的pebble個數(shù)不小于2，那么能移一個pebble給v1.因此下面設點集｛u01，u12，u1（n-1）｝中任意一點含有的pebble個數(shù)都不超過1.

（1.1）p（u01）=1.如果點集｛v0，u02，u03，…，u0（n-1）｝中至少有一點含有的pebble 個數(shù)不小于2，那么能移一個pebble給u01，使得p（u01）=2.下面設點集｛v0，u02，u03，…，u0（n-1）｝中任意一點含有的pebble個數(shù)都不超過1.當p（v0）=1時，去掉v1，u01，u12得M（Wn-1）且除v0含有一個pebble 外，還至少有3n-5=3（n-1）-2個peb?ble，由假設知，能移一個pebble給v0，使得p（v0）=2.當p（v0）=0時，如果p（u02）=p（u03）=…=p（u0（n-））=1，則點集｛v2，u23，v3，…，vn-2，u（n-2）（n-1），vn-1｝中至少有一點含有的pebble個數(shù)不小于2.由引理1知，能移一個pebble給u01，使得p（u01）=2.如果點集｛u02，u03，…，u0（n-1）｝中至少有一點含有的pebble個數(shù)為0，令p（u0r）=0，r∈｛2，3，…，n-1｝.如果p（ur（r+1））+p（vr）≥5，那么能移 2個pebble給u0r，使得p（u0r）=2.如果p（ur（r+1））+p（vr）=4，能從｛ur（r+1），vr｝移一個pebble給vr+1，然后去掉u0r，vr，ur（r+1）得M（Wn-1）且含有3n-5=3（n-1）-2個pebble，由假設知，能移一個 pebble 給v1.如果p（ur（r+1））+p（vr）≤3，去掉u0r，vr，ur（r+1）得M（Wn-1）且至少含有 3n-5=3（n-1）-2 個pebble，由假設知，能移一個pebble給v1.

（1.2）p（u01）=0.如果點集｛v0，u02，u03，…，u0（n-1）｝中至少有一點含有的pebble個數(shù)不小于4，那么能移2個pebble給u01，使得p（u01）=2.下面設點集｛v0，u02，u03，…，u0（n-1）｝中任意一點含有的pebble個數(shù)都不超過3.如果點集｛v0，u02，u03，…，u0（n-1）｝中有兩點含有的pebble個數(shù)之和為5或6，那么能移2個pebble給u01，使得p（u01）=2.如果點集｛v0，u02，u03，…，u0（n-1）｝中有兩點含有的pebble個數(shù)都為2，那么能分別移一個pebble給u01，使得p（u01）=2.如果點集｛v0，u02，u03，…，u0（n-1）｝中只有一點含有的 pebble 個數(shù)不小于2，不失一般性，不妨設p（u0i）≥2，其中i∈｛1，2，…，r-1，r+1，…，n-1｝（否則重新標記），從u0i能移一個pebble給u01，如果p（u0r）=1，當｛ur（r+1），vr｝中至少有一點含有的pebble個數(shù)不小于2時，能移一個pebble給u0r，使得p（u0r）=2，那么能再移一個pebble給u01，使得p（u01）=2.否則，當｛ur（r+1），vr｝中含有的pebble個數(shù)都不超過1時，去掉u0r，vr，ur（r+1）得M（Wn-1）且至少含有 3n-5=3（n-1）-2個pebble，由假設知，能移一個pebble給v1.如果p（u0r）=0，類似于（1.1）中討論.下面討論點集｛v0，u02，u03，…，u0（n-1）｝中任意一點含有的pebble個數(shù)都不超過1.如果p（v0）=p（u02）=p（u03）=…=p（u0（n-1））=1，則點集｛v2，u23，v3，…，u（n-2）（n-1），vn-1｝中至少有一點含有的 pebble個數(shù)不小于2，由引理1知，能移一個pebble給v1.如果點集｛v0，u02，u03，…，u0（n-1）｝中至少有一點含有的pebble個數(shù)為0，類似于（1.1）中討論.

（2）設目標頂點為點集｛u12，u23，u34，…，u（n-2）（n-1）｝中任意一點，由對稱性，不妨設目標頂點為u12，即p（u12）=0.如果點集｛v1，v2，u23，u1（n-1），u01，u02｝中至少有一點含有的pebble個數(shù)不小于2，那么能移一個pebble給u12.下面設點集｛v1，v2，u23，u1（n-1），u01，u02｝中任意一點含有的pebble個數(shù)都不超過1.

（2.1）p（u01）=1.如果點集｛v0，u03，u04，…，u0（n-1）｝中至少有一點含有的pebble 個數(shù)不小于2，那么能移一個pebble給u01，使得p（u01）=2.下面討論點集｛v0，u03，u04，…，u0（n-1）｝中任意一點含有的pebble個數(shù)都不超過 1.如果p（v0）=p（u03）=p（u04）=…=p（u0（n-1）｝）=1，則點集｛v3，u34，v4，…，vn-2，u（n-2）（n-1），vn-1｝中至少有一點含有的pebble個數(shù)不小于2，由引理1知，那么能移一個pebble給u12.如果點集｛v0，u03，u04，…，u0（n-1）｝中至少有一點含有的pebble個數(shù)為0，類似于（1.1）中討論.

（2.2）p（u01）=0.如果p（u02）=1類似于（2.1）中討論.下面設p（u02）=0.如果點集｛v0，u03，u04，…，u0（n-1）｝中至少有一點含有的pebble 個數(shù)不小于4，由引理1 知，能移一個pebble 給u12.如果點集｛v0，u03，u04，…，u0（n-1）｝中任意一點含有的pebble個數(shù)都不超過3，類似于（1.2）中討論.

（3）設目標頂點為點集｛u01，u02，…，u0（n-1）｝中任意一點，由對稱性，不妨設目標頂點為u01，即p（u01）=0.如果點集｛v0，u02，u03，…，u0（n-1），v1，u12，u1（n-1）｝中至少有一點含有的pebble個數(shù)不小于2，那么能移一個peb?ble給u01.下面設點集｛v0，u02，u03，…，u0（n-1），v1，u12，u1（n-1）｝中任意一點含有的pebble個數(shù)都不超過1.

（3.1）p（u0r）=1.如果點集｛u（r-1）r，vr，ur（r+1）｝中至少有一點含有的 pebble 個數(shù)不小于 2，那么能移一個pebble給u0r，使得p（u0r）=2.如果點集｛u（r-1）r，vr，ur（r+1）｝中任意一點含有的pebble個數(shù)都不超過1，去掉u0r，vr，ur（r+1）得M（Wn-1）且至少含有3n-5=3（n-1）-2個pebble，由假設知，能移一個pebble給u01.

（3.2）p（u0r）=0.如果點集｛u（r-1）r，vr，ur（r+1）｝中至少有一點含有的 pebble 個數(shù)不小于 4，那么能移 2 個pebble 給u0r，使得p（u0r）=2.下面設點集｛u（r-1）r，vr，ur（r+1）｝中任意一點含有的 pebble 個數(shù)都不超過 3.當p（vr）+p（ur（r+1）｝）=5 或 6 時，能移 2 個 pebble 給u0r，使得p（u0r）=2.當p（vr）+p（ur（r+1））≤4 時，類似于（1.1）中討論.

（4）設目標頂點為v0，即p（v0）=0.如果點集｛u01，u02，…，u0（n-1）｝中至少有一點含有的pebble 個數(shù)不小于2，那么能移一個pebble給v0.因此下面設點集｛u01，u02，…，u0（n-1）｝中任意一點含有的pebble個數(shù)都不超過1.

（4.1）p（u0r）=1.類似于（3.1）中討論.

（4.2）p（u0r）=0.類似于（3.2）中討論.

當n為奇數(shù)，即n=2r+1（r≥2）時：把u0r，vr，ur-1（r），vr+1，ur（r+1）中的r相應的換成r+1.

［1］葉永升，劉芳，翟明清.圈的中間圖的pebbling數(shù)和Graham猜想［J］.運籌學學報，2013，17（3）：35-44.

［2］CHUNG F R K.Pebblingin hypercubes［J］.SIAMJ Discrete Math，1989，2（4）：467-472.

［3］AKIYAMA J，HAMADA T，YOSHIMURA I.Miscellaneous properties of middle graphs［J］.TRU Math，1974，10：41-53.

［4］PACHTER L，SNEVILY H S，VOXMAN B.On pebbling graphs［J］.Congressus Numerantium，1995，107：65-80.

［5］FENG R Q，KIM J Y.Pebbling numbers of some graphs［J］.Science in China（Series A），2002，45（4）：470-478.

［6］劉海英，秦瓊，王志平，等.中間圖的pebbling數(shù)［J］.大連海事大學學報，2006，32（4）：125-128.