路和圈的最优一般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数……