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

史彩霞， 葉永升

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

0 引 言

圖的pebbling 數(shù)問題首先是由Chung［1］所討論的，而圖的一般pebbling 數(shù)問題最早是由A.Lourdusamy 和C.Muthulakshmi［2］所討論的. 考慮一個連通圖G 并有一定數(shù)目的pebble 放置在這個圖G 的頂點上，一個一般pebbling 移動是從一個頂點上移走p 個pebble，把其中的一個移到與其相鄰的一個頂點上. 圖G 的一個頂點v 的一般pebbling 數(shù)f(G，v)是最小的正整數(shù)f(G，v)，滿足從G 的頂點上fgl(G，v)個pebble 的任何一種放置開始，總可以通過一系列一般pebbling 移動把一個pebble 移到v 上. 圖G 的一般pebbling 數(shù)fgl(G)是對圖G 的所有頂點v 來說f(G，v)的最大值. 圖G的一個分布是可解的，當通過一系列一般pebbling移動，能把一個pebble 移到其任意一個頂點上.如對于可解分布D，用| D| 表示可解分布D 上所擁有的pebble 個數(shù). 對于圖G 的頂點v 來說，D(v)=t，表示可解分布D 下放置t 個pebble 在v 上. 圖G的頂點v 被占據(jù)，當D(v)＞0;頂點v 未被占據(jù)，當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，通過去掉一個頂點，這個頂點的度為1 或2. 如果去掉一個度為1 的頂點v，這時的圖被理解為與頂點v 相關聯(lián)的邊也去掉. 如果v的度為2，這時與v相關聯(lián)的兩條邊被原來與v 相鄰的兩點相連的一條邊所取代. 此時，n 個頂點的路(或圈)通過刪除一個頂點就變成了n -1 個頂點的路(或圈)了.

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 時，由引理1 知，結論正確.

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

當3t + r = 1，2，3 時. 很容易驗證上式成立，即定理成立.

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

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

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

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

(2.3)若在P3t+r中被占據(jù)的點擁有的pebble個數(shù)至少為3 = p (否則為情況2.1 或2.2). 令i 是最小的正整數(shù)，使得vi被占據(jù)，vi+1未被占據(jù). 不然從相反的方向重新標記P3t+r的頂點. 如果找不到上述情形，說明P3t+r的頂點均被占據(jù)或未被占據(jù).此時| D|≥(3t + r)= 9t +3r ＞pt + r 或| D| =0，矛盾，故一定會出現(xiàn)前者情形. 不失一般性，設vi參與一般pebbling 移動，那么vi不是末端點，即1 ≤i ＜3t +r. 構造D*，刪除vi+1，并將vi上的一個pebble 去掉. 當D(vi)= p，i = 1 或3t + r -1 時，刪除v2(或v3t+r)及v1(或v3t+r-1)上一個pebble 前后沒有影響. 若1 ＜i ＜3t +r -1，設從vi-1可移a個pebble 給vi，那么在D 下，從vi-1最多可移』』個pebble 給vi+2. 在D*下，可從vi-1移』個pebble 給?a ≥0.當D(vi)= b ≥4 ＞p 時，若i = 3t + r -1，刪除v3t+r及v3t+r-1上一個pebble，前后沒有影響.若i = 1，在D 下，從v1最多可移個pebble 給v3，而在D*下，從v1直接可移個pebble 給v3.［，?b ≥4.若1 ＜i ＜3t + r -1 時，設從vi-1可移a 個pebble 給vi，那么在D 下，從vi-1最多可移個pebble 給vi+2. 而在D*下，可從vi-1直接可移』個 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 時，在P3t+r每個頂點上放一個pebble，此時分布是可解的，且其上的pebble 個數(shù)為3t + r.下證任意一種可解分布的pebble 個數(shù)都不小于3t+r.設D 為P3t+r的一種可解分布，則D 為以下兩種情況中的一種.

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

②有些點參與一般pebbling 移動. 若從一個點到其鄰點有一般pebbling 移動，至少要扔掉3 個pebble，而此時所用的pebble 要比在這個點及與這個點相鄰的兩點上分別有一個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 時，由引理2 知，結論正確.

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

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

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

(2.3)C3t+r中被占據(jù)的點擁有的pebble 個數(shù)至少為3 = p(否則為情況2.1 或2.2). 設D(v1)= 3，否則重新標記C3t+r的頂點. 若v2或v3t+r未被占據(jù)，不妨設D(v2)= 0，刪除v2及v1上的一個pebble，并把v1上的另一個pebble 給v3t+r，得D*.設從v3t+r可移a 個pebble 給v1，在D 下，從v3t+r最多可移個pebble 給v3.而在D*下，可移個pebble.?a ≥0.設從v3可移b 個pebble 給v2，在D 下，從v3最多可移個pebble 給v3t+r.而在D*下，直接可移個pebble 給v3t+r.，?b ≥0.若v2及v3t+r均被占據(jù)，類似于(2.2)中證明. 若v1是被占據(jù)的點上擁有的pebble 個數(shù)最小的點，且D(v1)=b ＞p，從v1到v2到v3t+r方向找到離v1最近的未被占據(jù)的點，不妨記為vj. 刪除vj及v1上的3 個pebble，并把其中的2 個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 時，類似于定理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).