轮图中间图的pebbling数

史彩霞，叶永升，高 洁，程 芳

（淮北师范大学 数学科学学院，安徽 淮北 235000）

图的pebbling 数问题首先是由Chung讨论的，考虑一个连通图G并有一定数目的pebble放置在这个图G的顶点上，一个pebbling移动是从一个顶点上移走2个pebble，把其中的一个移到与其相邻的一个顶点上.图G的一个顶点v的pebbling数f（G，v）是最小的正整数f（G，v），满足从G的顶点上f（G，v）个pebble的任何一种放置开始，总可以通过一系列的pebbling移动把一个pebble移到v上.图G的pebbling数f（G）是对图G的所有顶点v来说f（G，v）的最大值.

在图G中，如果除了v以外其他点最多放一个pebble，那么没有一个pebble 移到v.另外，如果顶点u和v的距离为d且至多将2d-1 个pebble 放在u上，那么也不能把一个pebble 移到v上，因此f（G）≥max｛|V（G）|，2D｝，这里|V（G）|表示图G的顶点个数，而D为图G的直径.G的一个传送子图是一条路x0，x1，…，xk，使得在顶点x0上至少有2个pebble，且通过一系列的pebbling移动可以把一个pebble从x0传送到xk.在一个传送子图中，顶点xi上的一个pebble 等效于x0上放置2i个pebble.为了下文证明需要，我们引用下述4个引理：

引理 1［1］在一条路x0，x1，…，xk上，设p（x0）+2p（x1）+…+2ip（xi）+…+2k-1p（xk-1）≥2k，则路x0，x1，…，xk是一个传送子图.

引理2［1］设C2n+1=v0v1…v2nv0，边viv（i+1）mod（2n+1）的插入点为ui（i=0，1，2，…，2n），把C2n+1的相邻边上的插入点相连，便构成了f（M（C2n+1））.

引理3具有3个顶点的扇图，记为F3，是一条路P2加上另一个顶点v0，此顶点v0与路P2的两个顶点都相邻，这里P2=v1v2，在P2上插入点u12，在边v0v1，v0v2上分别插入点u01，u02，再将u01，u02，u12两两相连，便得扇图F3的中间图（M（F3））.对于（M（F3））容易验证f（M（F3））=7.

引理4［2］f（Kn）=n，其中Kn为n个顶点的完全图.

定义5轮图的中间图M（Wn）：具有n个顶点的轮图，记为Wn，是一个圈Cn-1加上中间一个顶点v0，此顶点v0与圈Cn-1的每个顶点都相邻，这里Cn-1=v1v2…vn-1.在Cn-1边上依次插入点u12，u23，…，u（n-2）（n-1），分别在边v0v1，v0v2，…，v0vn-1上插入点u01，u02，…，u0（n-1），再将Wn的相邻边上的插入点相连.

在文献［3］中，Akiyama 等人给出图G的中间图（middle graph）的定义，即：图G的中间图M（G）就是在G的每一条边上插入一个新点，再把G上相邻边上的新点用一条边连接起来.Chung［2］给出n-立方体Qn、完全图Kn和路Pn的 pebbling 数；Pachter［4］研究了圈Cn的 pebbling 数；扇图Fn和轮图Wn的 pebbling 数是冯荣权等在文献［5］中给出的；在文献［6］中，刘海英等已经证明路、完全图和星图的中间图的pebbling数.在文献［1］中，叶永升等已经证明圈的中间图的pebbling 数.本文我们讨论轮图的中间图M（Wn）的pebbling数.

在本文中，设图G为一个简单连通图，对于G的一种pebbling 分布，p（v）表示放置在顶点v上的peb⁃bling数.而用p(v)表示G的顶点v通过一系列pebbling移动所具有的pebbling数.

1 轮图中间图的pebbling数

在这一部分，首先证明W4的中间图M（W4）的pebbling数，然后证明了Wn，n≥4的中间图M（Wn）的peb⁃bling数.

定理6f（M（W4））=10.

证明显然f（M（W4））≥10.现在任意放置10个pebble在M（W4）上.

（1）设目标顶点为点集｛v1，v2，v3，u12，u13，u23｝中任意一点，先设目标顶点为v1，即p（v1）=0.如果p（v0）+p（u01）+p（u02）+p（u03）≤3，去掉v0，u01，u02，u03得M（C3）且至少含有7个pebble，由引理2知，能移一个pebble给v1.如果p（v0）+p（u01）+p（u02）+p（u03）=4，当点集｛v0，u01，u02，u03｝中有一点含有4 个pebble，由引理 1 知，能移一个pebble给v1.当p（v0）=p（u01）=p（u02）=p（u03）=1时，那么点集｛u12，v2，u23，v3，u13｝中至少有一点含有的peb⁃ble个数不小于2，由引理1知，能移一个pebble 给v1.否则，点集｛v0，u01，u02，u03｝中至少有一点含有的peb⁃ble个数不小于2，那么至少能移一个pebble给｛v1，v2，v3，u12，u13，u23｝，然后去掉v0，u01，u02，u03得M（C3）且至少含有7个pebble，由引理2知，能移一个pebble给v1.如果p（v0）+p（u01）+p（u02）+p（u03）≥6，能移2个pebble给u01，使得p(u01)=2.如果p（v0）+p（u01）+p（u02）+p（u03）=5，当点集｛u12，v2，u23，v3，u13｝中至少有一点含有的peb⁃ble个数不小于2，那么至少能移一个pebble给｛v0，u01，u02，u03｝，使得p（v0）+p（u01）+p（u02）+p（u03）≥6.当p（u12）=p（v2）=p（u23）=p（v3）=p（u13）=1 时，点集｛v0，u01，u02，u03｝中至少有一点含有的 pebble 个数不小于 2，由引理1知，能移一个pebble给v1.当目标顶点为｛v2，v3，u12，u13，u23｝中任意一点时，类似可证.

（2）设目标顶点为点集｛u01，u02，u03｝中任意一点，由对称性，不妨设目标顶点为u01，即p（u01）=0.如果点集｛v0，u02，u03，v1，u12，u13｝中至少有一点含有的pebble 个数不小于2，那么能移一个pebble 给u01.下面设点集｛v0，u02，u03，v1，u12，u13｝中任意一点含有的pebble 个数都不超过1.因为在M（W4）中，v0，u01，u02，u03构成完全图K4，由引理4知，f（K4）=4，所以当p（v0）+p（u01）+p（u02）+p（u03）≥4时，能移一个pebble给u01.当p（v0）+p（u01）+p（u02）+p（u03）=3 时，点集｛v1，v2，v3，u12，u13，u23｝中至少有一点含有的 pebble 个数不小于 2，那么至少能移一个 pebble 给｛v0，u01，u02，u03｝，使得p（v0）+p（u01）+p（u02）+p（u03）≥4.当p（v0）+p（u01）+p（u02）+p（u03）=2时，如果p（v1）=1，去掉v0，u01，u02，u03得M（C3）且除v1含有一个pebble外，还含有7个pebble，由引理2知，能移一个 pebble 给v1，使得p（v1）=2.如果p（v1）=0，p（u12）=1或p（u13）=1 时，同上.如果p（v1）=p（u12）=p（u13）=1，点集｛v2，u23，v3｝中至少有一点含有的pebble 个数不小于2，由引理1 知，能移一个pebble 给u01.如果p（v1）=p（u12）=p（u13）=0，｛v2，u23，v3｝至少能移 2 个 pebble 给｛v0，u01，u02，u03｝，使得p（v0）+p（u01）+p（u02）+p（u03）≥4.当p（v0）+p（u01）+p（u02）+p（u03）=1时，如果点集｛v1，u12，u13｝中至少有一点含有一个pebble，同上.如果p（v1）=p（u12）=p（u13）=0，｛v2，u23，v3｝至少能移 3 个 pebble给｛v0，u01，u02，u03｝，使得p（v0）+p（u01）+p（u02）+p（u03）≥4.当p（v0）+p（u01）+p（u02）+p（u03）=0时，如果点集｛v1，u12，u13｝中至少有一点含有一个pebble，类似可证.如果p（v1）=p（u12）=p（u13）=0，此时点集｛v2，u23，v3｝中至少有一点含有的pebble 个数不小于4，由引理1知，能移一个pebble给u01.

（3）设目标顶点为v0，即p（v0）=0.如果点集｛u01，u02，u03｝中至少有一点含有的pebble个数不小于2，那么能移一个pebble给v0.因此下面设点集｛u01，u02，u03｝中任意一点含有的pebble个数都不超过1.当p（v0）+p（u01）+p（u02）+p（u03）≥3 时，同（2）.当p（v0）+p（u01）+p（u02）+p（u03）=2 时，此时要么｛v1，v2，v3，u12，u13，u23｝至少能移 2 个 pebble给｛v0，u01，u02，u03｝，使得p（v0）+p（u01）+p（u02）+p（u03）≥4.要么点集｛v1，v2，v3，u12，u13，u23｝中至少有一点含有的 pebble 个数不小于2，由引理 1 知，能移一个pebble 给v0.当p（v0）+p（u01）+p（u02）+p（u03）=1 时，点集｛u01，u02，u03｝中某点含有一个pebble，类似于（2）中证明.当p（v0）+p（u01）+p（u02）+p（u03）=0时，如果p（v1）+p（u12）+p（u13）≥6，能移 2个 pebble给u01，使得p（u01）=2.如果p（v1）+p（u12）+p（u13）=5，｛v2，u23，v3｝至少能移一个 pebble 给｛v1，u12，u13｝，使得p（v1）+p（u12）+p（u13）≥6.当p（v1）+p（u12）+p（u13）=4 时，｛v1，u12，u13｝能移一个pebble给｛v2，u23，v3｝，然后去掉u01，v1，u12，u13得M（F3）且含有7个pebble，由引理3知，能移一个pebble给v0.当p（v1）+p（u12）+p（u13）≤3时，去掉u01，v1，u12，u13得M（F3）且至少含有7个pebble，由引理3知，能移一个pebble给v0.

为了便于定理7的证明，在M（Wn）中，例如去掉点v1，u01，u12，使u1（n-1）分别与v2，u23相连接，得M（Wn-1）.在下面的证明过程中，去点得M（Wn-1）与此类似，不再说明.

定理7f（M（Wn））=3n-2 （n≥4）.

证明显然f（M（Wn））≥3n-2.由定理5 知，当n=4 时命题成立.假设对于k＜n，有f（M（Wk））=3k-2 成立.下证f（M（Wn））=3n-2.现在任意放置3n-2个pebble 在M（Wn）上.下面讨论n的奇偶性，当n为偶数，即n=2r（r≥3）时：

（1）设目标顶点为点集｛v1，v2，…，vn-1｝中任意一点，由对称性，不妨设目标顶点为v1，即p（v1）=0.如果点集｛u01，u12，u1（n-1）｝中至少有一点含有的pebble个数不小于2，那么能移一个pebble给v1.因此下面设点集｛u01，u12，u1（n-1）｝中任意一点含有的pebble个数都不超过1.

（1.1）p（u01）=1.如果点集｛v0，u02，u03，…，u0（n-1）｝中至少有一点含有的pebble 个数不小于2，那么能移一个pebble给u01，使得p（u01）=2.下面设点集｛v0，u02，u03，…，u0（n-1）｝中任意一点含有的pebble个数都不超过1.当p（v0）=1时，去掉v1，u01，u12得M（Wn-1）且除v0含有一个pebble 外，还至少有3n-5=3（n-1）-2个peb⁃ble，由假设知，能移一个pebble给v0，使得p（v0）=2.当p（v0）=0时，如果p（u02）=p（u03）=…=p（u0（n-））=1，则点集｛v2，u23，v3，…，vn-2，u（n-2）（n-1），vn-1｝中至少有一点含有的pebble个数不小于2.由引理1知，能移一个pebble给u01，使得p（u01）=2.如果点集｛u02，u03，…，u0（n-1）｝中至少有一点含有的pebble个数为0，令p（u0r）=0，r∈｛2，3，…，n-1｝.如果p（ur（r+1））+p（vr）≥5，那么能移 2个pebble给u0r，使得p（u0r）=2.如果p（ur（r+1））+p（vr）=4，能从｛ur（r+1），vr｝移一个pebble给vr+1，然后去掉u0r，vr，ur（r+1）得M（Wn-1）且含有3n-5=3（n-1）-2个pebble，由假设知，能移一个 pebble 给v1.如果p（ur（r+1））+p（vr）≤3，去掉u0r，vr，ur（r+1）得M（Wn-1）且至少含有 3n-5=3（n-1）-2 个pebble，由假设知，能移一个pebble给v1.

（1.2）p（u01）=0.如果点集｛v0，u02，u03，…，u0（n-1）｝中至少有一点含有的pebble个数不小于4，那么能移2个pebble给u01，使得p（u01）=2.下面设点集｛v0，u02，u03，…，u0（n-1）｝中任意一点含有的pebble个数都不超过3.如果点集｛v0，u02，u03，…，u0（n-1）｝中有两点含有的pebble个数之和为5或6，那么能移2个pebble给u01，使得p（u01）=2.如果点集｛v0，u02，u03，…，u0（n-1）｝中有两点含有的pebble个数都为2，那么能分别移一个pebble给u01，使得p（u01）=2.如果点集｛v0，u02，u03，…，u0（n-1）｝中只有一点含有的 pebble 个数不小于2，不失一般性，不妨设p（u0i）≥2，其中i∈｛1，2，…，r-1，r+1，…，n-1｝（否则重新标记），从u0i能移一个pebble给u01，如果p（u0r）=1，当｛ur（r+1），vr｝中至少有一点含有的pebble个数不小于2时，能移一个pebble给u0r，使得p（u0r）=2，那么能再移一个pebble给u01，使得p（u01）=2.否则，当｛ur（r+1），vr｝中含有的pebble个数都不超过1时，去掉u0r，vr，ur（r+1）得M（Wn-1）且至少含有 3n-5=3（n-1）-2个pebble，由假设知，能移一个pebble给v1.如果p（u0r）=0，类似于（1.1）中讨论.下面讨论点集｛v0，u02，u03，…，u0（n-1）｝中任意一点含有的pebble个数都不超过1.如果p（v0）=p（u02）=p（u03）=…=p（u0（n-1））=1，则点集｛v2，u23，v3，…，u（n-2）（n-1），vn-1｝中至少有一点含有的 pebble个数不小于2，由引理1知，能移一个pebble给v1.如果点集｛v0，u02，u03，…，u0（n-1）｝中至少有一点含有的pebble个数为0，类似于（1.1）中讨论.

（2）设目标顶点为点集｛u12，u23，u34，…，u（n-2）（n-1）｝中任意一点，由对称性，不妨设目标顶点为u12，即p（u12）=0.如果点集｛v1，v2，u23，u1（n-1），u01，u02｝中至少有一点含有的pebble个数不小于2，那么能移一个pebble给u12.下面设点集｛v1，v2，u23，u1（n-1），u01，u02｝中任意一点含有的pebble个数都不超过1.

（2.1）p（u01）=1.如果点集｛v0，u03，u04，…，u0（n-1）｝中至少有一点含有的pebble 个数不小于2，那么能移一个pebble给u01，使得p（u01）=2.下面讨论点集｛v0，u03，u04，…，u0（n-1）｝中任意一点含有的pebble个数都不超过 1.如果p（v0）=p（u03）=p（u04）=…=p（u0（n-1）｝）=1，则点集｛v3，u34，v4，…，vn-2，u（n-2）（n-1），vn-1｝中至少有一点含有的pebble个数不小于2，由引理1知，那么能移一个pebble给u12.如果点集｛v0，u03，u04，…，u0（n-1）｝中至少有一点含有的pebble个数为0，类似于（1.1）中讨论.

（2.2）p（u01）=0.如果p（u02）=1类似于（2.1）中讨论.下面设p（u02）=0.如果点集｛v0，u03，u04，…，u0（n-1）｝中至少有一点含有的pebble 个数不小于4，由引理1 知，能移一个pebble 给u12.如果点集｛v0，u03，u04，…，u0（n-1）｝中任意一点含有的pebble个数都不超过3，类似于（1.2）中讨论.

（3）设目标顶点为点集｛u01，u02，…，u0（n-1）｝中任意一点，由对称性，不妨设目标顶点为u01，即p（u01）=0.如果点集｛v0，u02，u03，…，u0（n-1），v1，u12，u1（n-1）｝中至少有一点含有的pebble个数不小于2，那么能移一个peb⁃ble给u01.下面设点集｛v0，u02，u03，…，u0（n-1），v1，u12，u1（n-1）｝中任意一点含有的pebble个数都不超过1.

（3.1）p（u0r）=1.如果点集｛u（r-1）r，vr，ur（r+1）｝中至少有一点含有的 pebble 个数不小于 2，那么能移一个pebble给u0r，使得p（u0r）=2.如果点集｛u（r-1）r，vr，ur（r+1）｝中任意一点含有的pebble个数都不超过1，去掉u0r，vr，ur（r+1）得M（Wn-1）且至少含有3n-5=3（n-1）-2个pebble，由假设知，能移一个pebble给u01.

（3.2）p（u0r）=0.如果点集｛u（r-1）r，vr，ur（r+1）｝中至少有一点含有的 pebble 个数不小于 4，那么能移 2 个pebble 给u0r，使得p（u0r）=2.下面设点集｛u（r-1）r，vr，ur（r+1）｝中任意一点含有的 pebble 个数都不超过 3.当p（vr）+p（ur（r+1）｝）=5 或 6 时，能移 2 个 pebble 给u0r，使得p（u0r）=2.当p（vr）+p（ur（r+1））≤4 时，类似于（1.1）中讨论.

（4）设目标顶点为v0，即p（v0）=0.如果点集｛u01，u02，…，u0（n-1）｝中至少有一点含有的pebble 个数不小于2，那么能移一个pebble给v0.因此下面设点集｛u01，u02，…，u0（n-1）｝中任意一点含有的pebble个数都不超过1.

（4.1）p（u0r）=1.类似于（3.1）中讨论.

（4.2）p（u0r）=0.类似于（3.2）中讨论.

当n为奇数，即n=2r+1（r≥2）时：把u0r，vr，ur-1（r），vr+1，ur（r+1）中的r相应的换成r+1.

［1］叶永升，刘芳，翟明清.圈的中间图的pebbling数和Graham猜想［J］.运筹学学报，2013，17（3）：35-44.

［2］CHUNG F R K.Pebblingin hypercubes［J］.SIAMJ Discrete Math，1989，2（4）：467-472.

［3］AKIYAMA J，HAMADA T，YOSHIMURA I.Miscellaneous properties of middle graphs［J］.TRU Math，1974，10：41-53.

［4］PACHTER L，SNEVILY H S，VOXMAN B.On pebbling graphs［J］.Congressus Numerantium，1995，107：65-80.

［5］FENG R Q，KIM J Y.Pebbling numbers of some graphs［J］.Science in China（Series A），2002，45（4）：470-478.

［6］刘海英，秦琼，王志平，等.中间图的pebbling数［J］.大连海事大学学报，2006，32（4）：125-128.