宁鹏祥，叶永升

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

圈的强刺图的最优Pebbling数

宁鹏祥，叶永升

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

图 G上的一个pebbling移动是从一个顶点处移走两个pebble，而把其中的一个移到与其相邻的一个顶点上.图 G的最优pebbling数 f'(G)是指最小的整数 p，满足从 G的 p个pebble的某种放置方式开始，总可以通过一系列的pebbling移动把一个pebble移到 G的任一个顶点 v上.文章主要研究圈的强刺图C的最优pebbling数.

最优pebbling数;α－pebbling;强刺图

0 引言

图的pebbling问题首先是由Chung[1]所讨论的.图 G的pebbling数 f(G)第一次是由Saks和Lagarias[1]提出并研究的，在此基础上，Lemke和Kleitman[2]解决了一个数论问题，而最优pebbling数是由Pachter等[3]介绍的.

定义1 设 p1，p2，…，pn为非负整数，G是顶点数为 n的图，在图 G的每个顶点 ui处连接 pi个度为1的点，这里的 i=1，2，…，n，这样构成的图称为图 G的刺图，记作 G＊.若 pi≥1(i=1，2，…，n)，那么这样构成的图称为图 G的强刺图，记作 G＊＊.称度为1的所有点为 G＊＊的悬空点，以悬空点为端点的所有边称为G＊＊的刺.

设 Cn=(v1，v2，…，vn)，在 vi上加 pi(pi≥1)个悬空点得到的新图为 Cn的强刺图C.在本文中，对于v∈V(Cn)，在 Cn上去掉点 v所得的图表示为 Cn－1.

1 定理及证明

为证明本文的定理，先介绍下面的引理和推论.

由引理2可得到下面一个结论.

当 n=3时，设 D为 C3的一个分布，且满足 D(v1)=4，D(v2)=D(v3)=0，那么 C3通过一系列的pebbling移动，任意一点都能获得至少2个pebble，从而f2'(C3)≤4.若 D(C3)=3，那么无论怎么分布，C3通过一系列的pebbling移动，至少有一点至多只能得到1个pebble.故f2'(C3)=4.

当 n=4时，设 D为 C4的一个分布，且满足 D(v1)=D(v3)=2，D(v2)=D(v4)=0，那么 C4通过一系列的pebbling移动，任意一点都能获得至少2个pebble，从而f2'(C4)≤4.因为f2'(C4)≥f2'(C3)，从而f2'(C4) =4.

当 n≥5时，在 Cn上构造一个最优可解的分布 D，且|D|=n.令 n=3 t+r，当……