路和偶圈中间图的一般Pebbling数

2013-08-16 07:41:14史彩霞叶永升

淮北师范大学学报(自然科学版) 2013年3期

史彩霞，叶永升

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

0 引言

图的pebbling数问题首先是由Chung所讨论的，而图的一般pebbling数问题最早是由A.Lourdusamy等所讨论的.对于图的pebbling数和一般pebbling数已经得到了一些结果(见文献[1-5]).考虑一个连通图 G并有一定数目的pebble放置在这个图 G的顶点上，一个一般pebbling移动是从一个顶点上移走 p个pebble，而把其中的一个pebble移到与其相邻的一个顶点上.图 G的一个顶点 v的一般pebbling数 fgl(G，v)是最小的正整数 fgl(G，v)，满足从 G的顶点上 fgl(G，v)个pebble的任何一种放置开始，总可以通过一系列一般pebbling移动把一个pebble移到 v上.图 G的一般pebbling数 fgl(G)是对图 G的所有顶点 v来说 fgl(G，v)的最大值.

在文献[1]中，Akiyama等人给出了图 G的中间图(middle graph)的定义，即:图 G的中间图 M(G)就是在 G的每一条边上插入一个新点，再把 G上相邻边上的新点用一条边连接起来.Chung[2]给出了 n-立方体Qn、完全图 Kn和路 Pn的pebbling数;文[3]研究了完全图、路、圈和 K1，n的一般pebbling数;文献[4]已经证明了路、完全图和星图的中间图的pebbling数.本文将讨论路和偶圈中间图的一般pebbling数.

在本文中，G=(V(G)，E(G))表示顶点集为 V(G)和边集为 E(G)的简单连通图，对于 G的一种pebbling分布，p(H)表示分布在 G的子图 H上的pebbling数，p(v)表示放置在顶点 v上的pebbling数.而用p～(H)和p～(v)分别表示 G的子图 H和顶点 v通过一系列一般pebbling移动所具有的pebbling数.

引理2[2]令 P=v0v1…vn是一条长度为 n的路，则 fgl(P)=pn.

在路 P=v0v1…vn上，顶点 vi上放置一个pebble，等效于 v0上放置了 pi个pebble.

引理3 令 P=v0v1…vn是一条长度为 n的路，如果 WP(vn)≥kpn，那么通过一系列一般pebbling移动至少能移 k个pebble给 vn.

证明对 n进行归纳证明.显然，当 n=0时，结论正确.假设对于正整数 n'，1≤n'＜n结论正确.

引理4[4]设 M(Pn)为路 pn的中间图，那么 fgl(M(Pn))=pn+n-2，p=2.