路和偶圈中間圖的一般Pebbling數(shù)

史彩霞，葉永升

(淮北師范大學 數(shù)學科學學院，安徽 淮北 235000)

0 引言

圖的pebbling數(shù)問題首先是由Chung所討論的，而圖的一般pebbling數(shù)問題最早是由A.Lourdusamy等所討論的.對于圖的pebbling數(shù)和一般pebbling數(shù)已經(jīng)得到了一些結果(見文獻[1-5]).考慮一個連通圖 G并有一定數(shù)目的pebble放置在這個圖 G的頂點上，一個一般pebbling移動是從一個頂點上移走 p個pebble，而把其中的一個pebble移到與其相鄰的一個頂點上.圖 G的一個頂點 v的一般pebbling數(shù) fgl(G，v)是最小的正整數(shù) fgl(G，v)，滿足從 G的頂點上 fgl(G，v)個pebble的任何一種放置開始，總可以通過一系列一般pebbling移動把一個pebble移到 v上.圖 G的一般pebbling數(shù) fgl(G)是對圖 G的所有頂點 v來說 fgl(G，v)的最大值.

在文獻[1]中，Akiyama等人給出了圖 G的中間圖(middle graph)的定義，即:圖 G的中間圖 M(G)就是在 G的每一條邊上插入一個新點，再把 G上相鄰邊上的新點用一條邊連接起來.Chung[2]給出了 n-立方體Qn、完全圖 Kn和路 Pn的pebbling數(shù);文[3]研究了完全圖、路、圈和 K1，n的一般pebbling數(shù);文獻[4]已經(jīng)證明了路、完全圖和星圖的中間圖的pebbling數(shù).本文將討論路和偶圈中間圖的一般pebbling數(shù).

在本文中，G=(V(G)，E(G))表示頂點集為 V(G)和邊集為 E(G)的簡單連通圖，對于 G的一種pebbling分布，p(H)表示分布在 G的子圖 H上的pebbling數(shù)，p(v)表示放置在頂點 v上的pebbling數(shù).而用p～(H)和p～(v)分別表示 G的子圖 H和頂點 v通過一系列一般pebbling移動所具有的pebbling數(shù).

引理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時，結論正確.假設對于正整數(shù) n'，1≤n'＜n結論正確.

引理4[4]設 M(Pn)為路 pn的中間圖，那么 fgl(M(Pn))=pn+n-2，p=2.

1 路和偶圈中間圖的一般pebbling數(shù)

在這一部分，我們首先證明路中間圖 M(Pn)的一般pebbling數(shù)，然后證明偶圈中間圖 M(C2n)的一般pebbling數(shù).

定理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).現(xiàn)證有 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).

現(xiàn)在放置 pn+(n-2)(p-1)個pebble在 M(Pn)上.

當 p=2時，由引理4知，結論正確.

當 p≥3時，我們用數(shù)學歸納法證明.當 n=2時，由引理2知，結論正確.假設對于正整數(shù) 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 個數(shù)不小于 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 個數(shù)不小于 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).現(xiàn)在在 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.現(xiàn)在設 p(un)=pn-a(1≤a≤pn)，根據(jù)對稱性，不妨設 p(A')≥p(B').

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

如果 p(v1)≥p，那么我們能從 v1移一個pebble給 u0.現(xiàn)在假設 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，故

而 unun-1…u0是一條長度為 n的路，由引理3知，能移一個pebble給 u0.

[1]AKIYAMA J，HAMADA T，YOSHIMURA I.Miscellaneous properties of middle graphs[J].TRU Math，1974，10:41-53.

[2]CHUNG F R K.Pebbling in hypercubes[J].SIAMJ Discrete Math，1989，2(4):467-472.

[3]LOURDUSAMY A，MUTHULAKSHMI C.Generalized pebbling number[J].Internation Mathematical Forum，2010，5(7):1 331-1 337.

[4]劉海英，秦瓊，王志平，等.中間圖的pebbling數(shù)[J].大連海事大學學報，2006，32(4):125-128.

[5]SNEVILY H S，F(xiàn)OSTER J A.The 2-pebbling propertyanda conjectureof graham's[J].Graphsand Combinatorics，2000，16:231-244.