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

2013-08-16史彩霞叶永升

淮北师范大学学报(自然科学版) 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.

1 路和偶圈中间图的一般pebbling数

在这一部分，我们首先证明路中间图 M(Pn)的一般pebbling数，然后证明偶圈中间图 M(C2n)的一般pebbling数.

定理5 设 M(Pn)为路 pn的中间图，那么 fgl(M(Pn))=pn+(n-2)(p-1)(p≥2，n≥2).

证明设 Pn=v1v2…vn，在边 vivi+1上插入点 ui(i=1，2，…，n-1)，再把 Pn相邻边上的插入点相连，便构成了 M(Pn).现证有 pn+(n-2)(p-1)-1个pebble的一个分布不能使一个pebble到达一目标顶点，考虑 pn+(n-2)(p-1)-1 个 pebble的分布情况:p(v1)=pn-1，p(vi)=p-1(i=2，3，…，n-1)，p(ui)=0(i=1，2，…，n-1)，这时无 pebble 到达点 vn，因此 fgl(M(Pn))≥pn+(n-2)(p-1).

现在放置 pn+(n-2)(p-1)个pebble在 M(Pn)上.

当 p=2时，由引理4知，结论正确.

当 p≥3时，我们用数学归纳法证明.当 n=2时，由引理2知，结论正确.假设对于正整数 n'，3≤n'＜n时结论正确.下面证明 fgl(M(Pn))=pn+(n-2)(p-1).

(1)设目标顶点为 v1或 vn(v1与 vn是对称的)，不妨设目标顶点为 vn，即 p(vn)=0.若 p(un-1)≥p，那么 un-1通过一般pebbling移动可以移一个pebble给 vn.下面假设 p(un-1)≤p-1.

(1.1)若集合｛v1， u1， u2，…， un-2， un-1｝上放置的 pebble 个数不小于 pn，而 v1u1u2… un-2un-1是一条长度为 n-1的路，由引理3知，un-1至少可以得到 p个pebble，即p～(un-1)≥p，那么可以移一个pebble给 vn.

而 v1u1u2…un-2un-1vn是一条长度为 n的路，由引理3知，能移一个pebble给 vn.

(2)设目标顶点为 u1或 un-1(u1与 un-1是对称的)，不妨设目标顶点为 un-1，即 p(un-1)=0.若 p(vn)≥p，那么 vn可以通过一般pebbling移动移一个pebble给 un-1.下面假设 p(vn)≤p-1.

(2.1)若集合｛v1， u1， u2，…，un-2｝上放置的 pebble 个数不小于 pn-1，而 v1u1u2… un-2un-1是一条长度为n-1的路，由引理2知，能移一个pebble给 un-1.

而 v1u1u2…un-2un-1是一条长度为 n-1的路，由引理3知，能移一个pebble给 un-1.

(4)设目标顶点为 uj，2≤j≤n-2，即 p(uj)=0.这时以 vj+1为分点把 M(Pn)分解为其两个子图 M(Pj+1)和 M(Pn-j).

类似于(3)证明.

定理6 设 M(C2n)为偶圈 C2n的中间图，那么 fgl(M(C2n))=pn+1+(2n-2)(p-1)(p≥2，n≥2).

证明设 C2n=v0v1…v2n-1v0，边 viv(i+1)mod(2n)的插入点为 ui(i=0，1，…，2n-1)，把 C2n相邻边上的插入点相连，便构成 M(C2n).如果在 vn上放置 pn+1-1 个 pebble，并在 v1，v2，…， vn-1，vn+1， vn+2，…， v2n-1上各放置 p-1个 pebble，而其余顶点没有放置pebble，那么不能移一个 pebble到 v0.因此 fgl(M(C2n))≥pn+1+(2n-2)(p-1).现在在 M(C2n)上任意放置 pn+1+(2n-2)(p-1)个pebble.下面分两种情况讨论:

此时，vnun-1un-2…u0v0是一条长度为 n+1的路，由引理3知，能移一个pebble给 v0.

(2)设目标顶点为 ui， i=0，1，…，2n-1，不妨设目标顶点为 u0，即 p(u0)=0.设 A'= ｛v1， u1，…， vn-1，un-1，vn｝，B'= ｛v0，u2n-1，…，un+1，vn+1｝.显然，当 p(un)≥pn时，unun-1…u0是一条长度为 n 的路，由引理 3知，能移一个pebble给 u0.现在设 p(un)=pn-a(1≤a≤pn)，根据对称性，不妨设 p(A')≥p(B').

(2.1)若 a=pn或 pn-1，则

如果 p(v1)≥p，那么我们能从 v1移一个pebble给 u0.现在假设 p(v1)≤p-1.删除 v1及其上的pebble，则在 A'-v1+u0上至少放置了 pn+(n-2)(p-1)个pebble，这时 u0u1v2u2…un-1vn可以看作一条长度为 n的路的中间图.由定理5知，我们能移一个pebble给 u0.

(2.2)若 1≤ a≤ pn-2，故