寧鵬祥，葉永升

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

圈的強(qiáng)刺圖的最優(yōu)Pebbling數(shù)

寧鵬祥，葉永升

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

圖 G上的一個pebbling移動是從一個頂點(diǎn)處移走兩個pebble，而把其中的一個移到與其相鄰的一個頂點(diǎn)上.圖 G的最優(yōu)pebbling數(shù) f'(G)是指最小的整數(shù) p，滿足從 G的 p個pebble的某種放置方式開始，總可以通過一系列的pebbling移動把一個pebble移到 G的任一個頂點(diǎn) v上.文章主要研究圈的強(qiáng)刺圖C的最優(yōu)pebbling數(shù).

最優(yōu)pebbling數(shù);α－pebbling;強(qiáng)刺圖

0 引言

圖的pebbling問題首先是由Chung[1]所討論的.圖 G的pebbling數(shù) f(G)第一次是由Saks和Lagarias[1]提出并研究的，在此基礎(chǔ)上，Lemke和Kleitman[2]解決了一個數(shù)論問題，而最優(yōu)pebbling數(shù)是由Pachter等[3]介紹的.

定義1 設(shè) p1，p2，…，pn為非負(fù)整數(shù)，G是頂點(diǎn)數(shù)為 n的圖，在圖 G的每個頂點(diǎn) ui處連接 pi個度為1的點(diǎn)，這里的 i=1，2，…，n，這樣構(gòu)成的圖稱為圖 G的刺圖，記作 G＊.若 pi≥1(i=1，2，…，n)，那么這樣構(gòu)成的圖稱為圖 G的強(qiáng)刺圖，記作 G＊＊.稱度為1的所有點(diǎn)為 G＊＊的懸空點(diǎn)，以懸空點(diǎn)為端點(diǎn)的所有邊稱為G＊＊的刺.

設(shè) Cn=(v1，v2，…，vn)，在 vi上加 pi(pi≥1)個懸空點(diǎn)得到的新圖為 Cn的強(qiáng)刺圖C.在本文中，對于v∈V(Cn)，在 Cn上去掉點(diǎn) v所得的圖表示為 Cn－1.

1 定理及證明

為證明本文的定理，先介紹下面的引理和推論.

由引理2可得到下面一個結(jié)論.

當(dāng) n=3時，設(shè) D為 C3的一個分布，且滿足 D(v1)=4，D(v2)=D(v3)=0，那么 C3通過一系列的pebbling移動，任意一點(diǎn)都能獲得至少2個pebble，從而f2'(C3)≤4.若 D(C3)=3，那么無論怎么分布，C3通過一系列的pebbling移動，至少有一點(diǎn)至多只能得到1個pebble.故f2'(C3)=4.

當(dāng) n=4時，設(shè) D為 C4的一個分布，且滿足 D(v1)=D(v3)=2，D(v2)=D(v4)=0，那么 C4通過一系列的pebbling移動，任意一點(diǎn)都能獲得至少2個pebble，從而f2'(C4)≤4.因為f2'(C4)≥f2'(C3)，從而f2'(C4) =4.

當(dāng) n≥5時，在 Cn上構(gòu)造一個最優(yōu)可解的分布 D，且|D|=n.令 n=3 t+r，當(dāng)1≤i≤3 t時，設(shè) D(vi)= 2這里 i≡2 mod 3，D(vi+1)=1，D(vi－1)=0.如果 r=1時，令 D(v3t+1)=1，如果 r=2時，令 D(v3t+2)=2且 D(v3t+1)=0，所以f2'(Cn)≤n.下證f2'(Cn)=n.

假設(shè) n為最小的整數(shù)使f2'(Cn)＜n.在 Cn上構(gòu)造一個最優(yōu)可解的分布 D，且|D|=n－1.修改 D得到D＊，使得 D＊是 Cm(m＜n)上的一個最優(yōu)可解的分布，且|D＊|＜m，從而得到矛盾.

(1)Cn中存在一個點(diǎn) vi，使 D(vi)=1(1＜i＜n)(否則重新編號).

(2)Cn上每個放pebble的頂點(diǎn)上都放2個pebble.

在 Cn上一定存在相鄰的3個頂點(diǎn) vi，vi+1，vi+2，D[vi，vi+1，vi+2]=[2，0，2]或 D[vi，vi+1，vi+2]=[2，2，0].否則就有兩個連續(xù)的沒有分配到pebble的頂點(diǎn)，那么通過一系列的pebbling移動這兩個頂點(diǎn)最多只能得到1個pebble，因此這樣相鄰的3個頂點(diǎn)一定存在.去掉 vi+1，vi+2和它們上面的pebble，從而得到 Cn－2上的一個新的分布 D＊，在分布 D＊下，vi+3是放有2個pebble或能從 vi上得到1個pebble，因此 vi+3在分布D＊下通過一系列的pebbling移動得到的pebble的個數(shù)不小于在分布 D下通過一系列的pebbling移動得到的pebble的個數(shù)，在分布 D和分布 D＊下，vi－1和 vi+4通過一系列的pebbling移動得到的pebble數(shù)一樣，從而 D＊是最優(yōu)可解的.由于|D＊|＜n－2，故f2'(Cn－2)＜n－2，矛盾.

(3)Cn包含一頂點(diǎn) vi，滿足 D(vi)≥3.

綜上所述，這樣的 n是找不到的，從而當(dāng) n≥5時，f2'(n)=n.

[1]CHUNG F R K.Pebbling in hypercubes[J].SIAM JDiscrete Math，1989，2(4):461－472.

[2]LEMKE P，KLEITMAN D.An addition theorem on the integersmodulon[J].JNumber Theory，1989，31(3):335－345.

[3]PACHTER L，SNEVILY H，VOXMAN B.On pebbling graphs，Proceedings of the Twenty－sixth Southeastern International Conference on Combinatorics，Graph Theory and Computing[J].Congeessus Numerantium，1995，107(3):65－80.

[4]HUNG L F，CHIN L S.The optimal pebbling number of the complete m－ary tree[J].Discrete Math，2000，22(2):89－100.

[5]MOEWSD.Optimally pebbling hypercubes and powers[J].Discrete Math，1998，190(4):271－276.

[6]ALPAY Kirlangic.The scattering number of thorn graphs[J].International Journal of Computer Mathematics，2004，81(3):299－311.

Abstract:The pebbling move of G is taking two pebbles off one vertex and then placing one on an adjacent vertex.The optimal pebbling number of G，f'(G)，is the least positive integer p such that p pebbles are placed suitably on vertices of G and for any target vertex v of G.In this paper，we find the optimal pebbling number of the circle of strong thorn graphs.

Key words:optimal pebbling number;α－pebbling;strong thorn graphs

The Optimal Pebbling Number of the Circle of Strong Thorn Graphs

NING Peng－xiang，YE Yong－sheng
(School of Mathematical Sciences，Huaibei Normal University，235000，Huaibei，Anhui，China)

O 157.5

A

2095－0691(2012)03－0015－03

2012－01－14

安徽省自然科學(xué)研究項目(2010SQRL136ZD，1208085QF119)

寧鵬祥(1985－ )，男，安徽太和人，碩士生，研究方向為圖論及其應(yīng)用.通訊作者:葉永升(1964－ )，男，安徽嘉山人，副教授，研究方向為圖論及其應(yīng)用.