史彩霞， 葉永升

(淮北師范大學(xué)數(shù)學(xué)科學(xué)學(xué)院，安徽 準(zhǔn)北235000)

0 引 言

圖的pebbling 數(shù)問題首先是由Chung［1］所討論的，而圖的一般pebbling 數(shù)問題最早是由A.Lourdusamy 和C.Muthulakshmi［2］所討論的. 考慮一個(gè)連通圖G 并有一定數(shù)目的pebble 放置在這個(gè)圖G 的頂點(diǎn)上，一個(gè)一般pebbling 移動(dòng)是從一個(gè)頂點(diǎn)上移走p 個(gè)pebble，把其中的一個(gè)移到與其相鄰的一個(gè)頂點(diǎn)上. 圖G 的一個(gè)頂點(diǎn)v 的一般pebbling 數(shù)f(G，v)是最小的正整數(shù)f(G，v)，滿足從G 的頂點(diǎn)上fgl(G，v)個(gè)pebble 的任何一種放置開始，總可以通過一系列一般pebbling 移動(dòng)把一個(gè)pebble 移到v 上. 圖G 的一般pebbling 數(shù)fgl(G)是對(duì)圖G 的所有頂點(diǎn)v 來說f(G，v)的最大值. 圖G的一個(gè)分布是可解的，當(dāng)通過一系列一般pebbling移動(dòng)，能把一個(gè)pebble 移到其任意一個(gè)頂點(diǎn)上.如對(duì)于可解分布D，用| D| 表示可解分布D 上所擁有的pebble 個(gè)數(shù). 對(duì)于圖G 的頂點(diǎn)v 來說，D(v)=t，表示可解分布D 下放置t 個(gè)pebble 在v 上. 圖G的頂點(diǎn)v 被占據(jù)，當(dāng)D(v)＞0;頂點(diǎn)v 未被占據(jù)，當(dāng)D(v)= 0.

Chung［1］給出了n-立方體Qn、完全圖Kn和路Pn的 pebbling 數(shù);A. Lourdusamy 和 C.Muthulakshmi［2］研究了完全圖、路、圈和K1，n的一般pebbling 數(shù);Pachter［3］研究了路P3t+r的最優(yōu)pebbling 數(shù);C.Wyelsand 和T. Friedman［4］研究了路和圈的最優(yōu)pebbling 數(shù)，本文討論了路和圈的最優(yōu)一般pebbling 數(shù).

引理1［4］令路Pn= P3t+r，t ∈N+，r ∈{0，1，2}，則fgl'(P3t+r)= 2t + r，p = 2.

引理2［4］令圈Cn= C3t+r，t ∈N+，r ∈{0，1，2}，則fgl'(C3t+r)= 2t + r，p = 2.

在后面的證明中要改變圖G，通過去掉一個(gè)頂點(diǎn)，這個(gè)頂點(diǎn)的度為1 或2. 如果去掉一個(gè)度為1 的頂點(diǎn)v，這時(shí)的圖被理解為與頂點(diǎn)v 相關(guān)聯(lián)的邊也去掉. 如果v的度為2，這時(shí)與v相關(guān)聯(lián)的兩條邊被原來與v 相鄰的兩點(diǎn)相連的一條邊所取代. 此時(shí)，n 個(gè)頂點(diǎn)的路(或圈)通過刪除一個(gè)頂點(diǎn)就變成了n -1 個(gè)頂點(diǎn)的路(或圈)了.

1 路和圈的最優(yōu)一般pebbling 數(shù)

在這一部分，首先證明了路Pn的最優(yōu)一般pebbling 數(shù)，接著證明了圈Cn的最優(yōu)一般pebbling數(shù).

定理3 路Pn的最優(yōu)一般pebbling 數(shù):令Pn= P3t+r，t ∈N+，r ∈{0，1，2}，

證明 (1)p = 2 時(shí)，由引理1 知，結(jié)論正確.

(2)p = 3 時(shí)，設(shè)P3t+r的頂點(diǎn)依次為v1，v2，…，v3t+r.令1 ≤i ≤3t，D(vi)= p，若i ≡2mod3，而對(duì)于其它點(diǎn)未被占據(jù). 如果r = 1，令D(v3t+1)= 1;如果r = 2，令D(v3t+1)= D(v3t+2)= 1，這時(shí)的分布是可解的，所以fgl'(P3t+r)≤pt +r.下證fgl'(P3t+r)≥pt + r.

當(dāng)3t + r = 1，2，3 時(shí). 很容易驗(yàn)證上式成立，即定理成立.

為了證明fgl'(P3t+r)≥pt +r，假設(shè)對(duì)于小于3t+r 的正整數(shù)，定理均成立. 而3t+r 是最小的正整數(shù)使得fgl'(P3t+r)≥pt +r 不成立，即fgl'(P3t+r)＜pt + r.

以下的證明思路為:由于假設(shè)fgl'(P3t+r)≤pt+ r -1，可以選擇P3t+r的一個(gè)可解分布D，使得| D| = pt + r -1，通過去掉D 上一個(gè)點(diǎn)及一個(gè)pebble得到P3t+r-1的一個(gè)可解分布D*.此時(shí)| D*| = pt +r - 2，而fgl'(P3t+r-1) = pt + r - 1，| D*| ＜fgl(P3t+r-1)，得到矛盾，從而定理得證.

(2.1)若P3t+r中有一個(gè)頂點(diǎn)vi，D(vi)= 1.不失一般性，假設(shè)j ＞i，一般pebbling 移動(dòng)為由vi到vj方向進(jìn)行.去掉vi及其上的一個(gè)pebble，這時(shí)構(gòu)造了一個(gè)P3t+r-1的一個(gè)可解分布D*.若i = 1 或3t+ r，則vi或v3t+r不參與一般pebbling 移動(dòng)，去掉vi或v3t+r前后沒有影響.若1 ＜i ＜3t +r，設(shè)從vi-1可移a 個(gè)pebble 給vi，那么在D 下，vi-1最多可移』個(gè)pebble 給vi+1.而在D*下，a 個(gè)pebble 可以從vi-1直接移給vi+1.

(2.2)若在P3t+r中被占據(jù)的點(diǎn)擁有的pebble個(gè)數(shù)至少為2(否則為情況2.1). 令i(i ＜3t + r)是最小的正整數(shù)，使得D(vi)= 2，不然從相反的方向重新標(biāo)記P3t+r的頂點(diǎn). 構(gòu)造D*，去掉頂點(diǎn)vi及其上的一個(gè)pebble，并把另一個(gè)pebble 給vi+1.若i = 1，在D 下，v1不參與一般pebbling 移動(dòng)，而在D*下，v2可獲得一個(gè)pebble. 若i ＞1，設(shè)從vi-1可移a 個(gè)pebble 給vi，那么在D 下，從vi-1最多可移』個(gè)pebble 給vi+1.而在D*下，vi+1可直接得到a +1 個(gè)pebble.

(2.3)若在P3t+r中被占據(jù)的點(diǎn)擁有的pebble個(gè)數(shù)至少為3 = p (否則為情況2.1 或2.2). 令i 是最小的正整數(shù)，使得vi被占據(jù)，vi+1未被占據(jù). 不然從相反的方向重新標(biāo)記P3t+r的頂點(diǎn). 如果找不到上述情形，說明P3t+r的頂點(diǎn)均被占據(jù)或未被占據(jù).此時(shí)| D|≥(3t + r)= 9t +3r ＞pt + r 或| D| =0，矛盾，故一定會(huì)出現(xiàn)前者情形. 不失一般性，設(shè)vi參與一般pebbling 移動(dòng)，那么vi不是末端點(diǎn)，即1 ≤i ＜3t +r. 構(gòu)造D*，刪除vi+1，并將vi上的一個(gè)pebble 去掉. 當(dāng)D(vi)= p，i = 1 或3t + r -1 時(shí)，刪除v2(或v3t+r)及v1(或v3t+r-1)上一個(gè)pebble 前后沒有影響. 若1 ＜i ＜3t +r -1，設(shè)從vi-1可移a個(gè)pebble 給vi，那么在D 下，從vi-1最多可移』』個(gè)pebble 給vi+2. 在D*下，可從vi-1移』個(gè)pebble 給?a ≥0.當(dāng)D(vi)= b ≥4 ＞p 時(shí)，若i = 3t + r -1，刪除v3t+r及v3t+r-1上一個(gè)pebble，前后沒有影響.若i = 1，在D 下，從v1最多可移個(gè)pebble 給v3，而在D*下，從v1直接可移個(gè)pebble 給v3.［，?b ≥4.若1 ＜i ＜3t + r -1 時(shí)，設(shè)從vi-1可移a 個(gè)pebble 給vi，那么在D 下，從vi-1最多可移個(gè)pebble 給vi+2. 而在D*下，可從vi-1直接可移』個(gè) pebble 給，?a ≥0.綜上，| D*| = pt + r - 2 ＜fgl'(P3t+r-1)= pt +r -1，矛盾. 故fgl'(P3t+r-1)≥pt+ r，p = 3.可知，fgl'(P3t+r-1)= pt + r，p = 3.

(3)p ≥4 時(shí)，在P3t+r每個(gè)頂點(diǎn)上放一個(gè)pebble，此時(shí)分布是可解的，且其上的pebble 個(gè)數(shù)為3t + r.下證任意一種可解分布的pebble 個(gè)數(shù)都不小于3t+r.設(shè)D 為P3t+r的一種可解分布，則D 為以下兩種情況中的一種.

①P3t+r的所有頂點(diǎn)均被占據(jù)，且不參與一般pebbling 移動(dòng). 對(duì)于1 ≤i ≤3t +r，D(vi)∈{1，2，3}.

②有些點(diǎn)參與一般pebbling 移動(dòng). 若從一個(gè)點(diǎn)到其鄰點(diǎn)有一般pebbling 移動(dòng)，至少要扔掉3 個(gè)pebble，而此時(shí)所用的pebble 要比在這個(gè)點(diǎn)及與這個(gè)點(diǎn)相鄰的兩點(diǎn)上分別有一個(gè)pebble 占據(jù)所用的pebble 多.

可知| D|≥3t +r，故fgl'(P3t+r)= 3t +r，p ≥4.

定理4 圈Cn的最優(yōu)一般pebbling 數(shù):令Cn= C3t+r，t ∈N+，r ∈{0，1，2}

證明 (1)p = 2 時(shí)，由引理2 知，結(jié)論正確.

(2)p = 3 時(shí)，設(shè)C3t+r的頂點(diǎn)依次為v1，v2，…，v3t+r.因?yàn)镻3t+r是C3t+r的生成子圖，故fgl'(C3t+r)≤fgl'(P3t+r)= pt+r.下證fgl(C3t+r)≥pt+r.證明思路類似于定理1 中的(2).

(2.1)若C3t+r中有一個(gè)頂點(diǎn)vi，D(vi)= 1.記D(v1)= 1，不然對(duì)C3t+r的頂點(diǎn)重新標(biāo)記. 這時(shí)刪除v1及其上的pebble，得D*. 設(shè)從v3t+r可移a 個(gè)pebble 給v1，在D 下，從v3t+r最多可移個(gè)pebble 給v2，而在D*下，從v3t+r可移a 個(gè)pebble 給v2.a ≥，?a ≥0.設(shè)v2可移b 個(gè)pebble 給v1，在D 下，v2可移個(gè)pebble 給v3t+r，而在D*下，v2直接可移b 個(gè)pebble 給v3t+r.b ≥0.

(2.2)C3t+r中被占據(jù)的點(diǎn)擁有的pebble 個(gè)數(shù)至少為2(否則為情況2.1)，記D(v1)= 2，不然對(duì)C3t+r的頂點(diǎn)重新標(biāo)記. 若v2或v3t+r未被占據(jù)，不妨設(shè)D(v2)=0，這時(shí)刪除v2及v1上的一個(gè)pebble，得D*.設(shè)從v3t+r可移a 個(gè)pebble 給v1，在D 下，從v3t+r最多可移個(gè)pebble 給v3. 而在D*下，從v3t+r可移個(gè)pebble 給v3.，?a ≥0.若v3可移b 個(gè)pebble 給v2，在D 下，v3最多可移個(gè)pebble給v3t+r. 而在D*下，v3可移個(gè)pebble 給v3t+r.，?b ≥0. 若v2及v3t+r均被占據(jù)，這時(shí)去掉v1及其上的一個(gè)pebble 并把另一個(gè)pebble 給v3t+r，得到D*. 設(shè)從v3t+r可移a 個(gè)pebble 給v1，在D 下，v3t+r最多可移個(gè)pebble 給v2.在D*下，從v3t+r至少可移a個(gè)pebble 給v2.a ≥，?a ≥0.設(shè)從v2可移b 個(gè)pebble 給v1，在D 下，從v2最多可移個(gè)pebble 給v3t+r. 而在D*下，v3t+r可直接得到b+1 個(gè)pebble. b +1 ≥，?b ≥0.

(2.3)C3t+r中被占據(jù)的點(diǎn)擁有的pebble 個(gè)數(shù)至少為3 = p(否則為情況2.1 或2.2). 設(shè)D(v1)= 3，否則重新標(biāo)記C3t+r的頂點(diǎn). 若v2或v3t+r未被占據(jù)，不妨設(shè)D(v2)= 0，刪除v2及v1上的一個(gè)pebble，并把v1上的另一個(gè)pebble 給v3t+r，得D*.設(shè)從v3t+r可移a 個(gè)pebble 給v1，在D 下，從v3t+r最多可移個(gè)pebble 給v3.而在D*下，可移個(gè)pebble.?a ≥0.設(shè)從v3可移b 個(gè)pebble 給v2，在D 下，從v3最多可移個(gè)pebble 給v3t+r.而在D*下，直接可移個(gè)pebble 給v3t+r.，?b ≥0.若v2及v3t+r均被占據(jù)，類似于(2.2)中證明. 若v1是被占據(jù)的點(diǎn)上擁有的pebble 個(gè)數(shù)最小的點(diǎn)，且D(v1)=b ＞p，從v1到v2到v3t+r方向找到離v1最近的未被占據(jù)的點(diǎn)，不妨記為vj. 刪除vj及v1上的3 個(gè)pebble，并把其中的2 個(gè)pebble 放在v3t+r上，得D*.容易發(fā)現(xiàn)D*比D 更優(yōu)，綜上可知，| D*| = pt +r- 2 ＜ fgl'(C3t+r-1) = pt + r - 1，矛盾. 故fgl'(C3t+r-1)≥pt +r，p = 3. 可知，fgl'(C3t+r-1)= pt+ r，p = 3.

(3)p ≥4 時(shí)，類似于定理1 中(3)的證明.

［1］ F. Chung F R K.Pebbling in Hypercubes［J］. SIAMJ. Discrete Math，1989，2(4):467 -472.

［2］ A.Lourdusamy，C.Muthulakshmi. Generalized Pebbling Number［J］. Internation Mathematical Forum，2010，5(7):1331 -1337.

［3］ Pachter L，Snevily H S，Voxman B. On Pebbling Graphs［J］.Congressus Numerantium，1995，107:65 - 80.

［4］ C. Wyels，T. Friedman. Optimal Pebbling of Paths and Cycles［J］. Discrete Mathematics，submitted(Mathematics Arxiv Article math. Co/0506076).