路和圈的最优一般Pebbling 数①

史彩霞， 叶永升

(淮北师范大学数学科学学院，安徽 准北235000)

0 引 言

图的pebbling 数问题首先是由Chung［1］所讨论的，而图的一般pebbling 数问题最早是由A.Lourdusamy 和C.Muthulakshmi［2］所讨论的. 考虑一个连通图G 并有一定数目的pebble 放置在这个图G 的顶点上，一个一般pebbling 移动是从一个顶点上移走p 个pebble，把其中的一个移到与其相邻的一个顶点上. 图G 的一个顶点v 的一般pebbling 数f(G，v)是最小的正整数f(G，v)，满足从G 的顶点上fgl(G，v)个pebble 的任何一种放置开始，总可以通过一系列一般pebbling 移动把一个pebble 移到v 上. 图G 的一般pebbling 数fgl(G)是对图G 的所有顶点v 来说f(G，v)的最大值. 图G的一个分布是可解的，当通过一系列一般pebbling移动，能把一个pebble 移到其任意一个顶点上.如对于可解分布D，用| D| 表示可解分布D 上所拥有的pebble 个数. 对于图G 的顶点v 来说，D(v)=t，表示可解分布D 下放置t 个pebble 在v 上. 图G的顶点v 被占据，当D(v)＞0;顶点v 未被占据，当D(v)= 0.

Chung［1］给出了n-立方体Qn、完全图Kn和路Pn的 pebbling 数;A. Lourdusamy 和 C.Muthulakshmi［2］研究了完全图、路、圈和K1，n的一般pebbling 数;Pachter［3］研究了路P3t+r的最优pebbling 数;C.Wyelsand 和T. Friedman［4］研究了路和圈的最优pebbling 数，本文讨论了路和圈的最优一般pebbling 数.

引理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 相关联的边也去掉. 如果v的度为2，这时与v相关联的两条边被原来与v 相邻的两点相连的一条边所取代. 此时，n 个顶点的路(或圈)通过删除一个顶点就变成了n -1 个顶点的路(或圈)了.

1 路和圈的最优一般pebbling 数

在这一部分，首先证明了路Pn的最优一般pebbling 数，接着证明了圈Cn的最优一般pebbling数.

定理3 路Pn的最优一般pebbling 数:令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，而对于其它点未被占据. 如果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 的正整数，定理均成立. 而3t+r 是最小的正整数使得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中被占据的点拥有的pebble个数至少为2(否则为情况2.1). 令i(i ＜3t + r)是最小的正整数，使得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中被占据的点拥有的pebble个数至少为3 = p (否则为情况2.1 或2.2). 令i 是最小的正整数，使得vi被占据，vi+1未被占据. 不然从相反的方向重新标记P3t+r的顶点. 如果找不到上述情形，说明P3t+r的顶点均被占据或未被占据.此时| D|≥(3t + r)= 9t +3r ＞pt + r 或| D| =0，矛盾，故一定会出现前者情形. 不失一般性，设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 个数为3t + r.下证任意一种可解分布的pebble 个数都不小于3t+r.设D 为P3t+r的一种可解分布，则D 为以下两种情况中的一种.

①P3t+r的所有顶点均被占据，且不参与一般pebbling 移动. 对于1 ≤i ≤3t +r，D(vi)∈{1，2，3}.

②有些点参与一般pebbling 移动. 若从一个点到其邻点有一般pebbling 移动，至少要扔掉3 个pebble，而此时所用的pebble 要比在这个点及与这个点相邻的两点上分别有一个pebble 占据所用的pebble 多.

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

定理4 圈Cn的最优一般pebbling 数:令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中被占据的点拥有的pebble 个数至少为2(否则为情况2.1)，记D(v1)= 2，不然对C3t+r的顶点重新标记. 若v2或v3t+r未被占据，不妨设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均被占据，这时去掉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中被占据的点拥有的pebble 个数至少为3 = p(否则为情况2.1 或2.2). 设D(v1)= 3，否则重新标记C3t+r的顶点. 若v2或v3t+r未被占据，不妨设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均被占据，类似于(2.2)中证明. 若v1是被占据的点上拥有的pebble 个数最小的点，且D(v1)=b ＞p，从v1到v2到v3t+r方向找到离v1最近的未被占据的点，不妨记为vj. 删除vj及v1上的3 个pebble，并把其中的2 个pebble 放在v3t+r上，得D*.容易发现D*比D 更优，综上可知，| 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).