王艷秋, 葉永升

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

?

多扇圖的Pebbling數(shù)和Graham猜想

王艷秋, 葉永升

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

圖G的pebbling數(shù)f(G)是最小的整數(shù)n，使得不論n個pebble如何放置在G的頂點上，總可以通過一系列的pebbling移動把1個pebble移到任意一個頂點上，其中一個pebbling移動是從一個頂點處移走兩個pebble而把其中的一個移到與其相鄰的一個頂點上。Graham猜想對于任意的連通圖G和H有f(G×H)≤f(G)f(H)。多扇圖Fn1,n2,…,nm是指階為n1+n2+…+nm+1的聯(lián)圖P1∨(Pn1∪Pn2∪…∪Pnm)。本文首先給出了多扇圖的pebbling數(shù)，然后證明了多扇圖Fn1,n2,…,nm具有2-pebbling性質(zhì)，最后論述了對于一個多扇圖和一個具有2-pebbling性質(zhì)的圖的乘積來說，Graham猜想是成立的。作為一個推論，當G和H都是多扇圖時，Graham猜想成立。

運籌學；pebbling數(shù)；Graham猜想；pebbling移動；多扇圖

0 引言

連通圖的一個pebbling是一些pebble在這個圖的頂點上的一種放置方式， 一個pebbling移動是從一個頂點上移走兩個pebble。扔掉其中的一個而把另一個移到與其相鄰的一個頂點上。圖G的一個頂點v的pebbling數(shù)是最小的數(shù)f(G,v)滿足從G的頂點上f(G,v)個pebble的任意一種放置開始， 總可以通過一系列的pebbling移動把一個pebble移到頂點v上。 圖G的pebbling數(shù)記為f(G)，是對G的所有頂點v來說f(G,v)的最大值。

對于pebbling數(shù)f(G)已經(jīng)得到了一些結(jié)果(見文獻[1～5])，如果除頂點v之外每一個頂點上都只放置一個pebble，則沒有一個pebble能夠移到v上，另外，如果頂點w與v的距離為d，且2d-1個pebble放置在w上，則也不能把一個pebble移到v上，所以有f(G)≥max{|V(G)|,2d}。這里|V(G)|表示圖G的頂點個數(shù)，而d為圖G的直徑。進一步地，從文獻[1]知道f(Kn)=n·f(Pn)=2n-1，其中Kn為n個頂點的完全圖，而Pn為n個頂點的路。

給定G的一種pebbling，設q為具有至少1個pebble的頂點個數(shù)，r為具有奇數(shù)個pebble的頂點個數(shù)，稱G滿足2-pebbling性質(zhì)(或弱2-pebbling性質(zhì))， 如果當開始時總的pebble個數(shù)為2f(G)-q+1(或2f(G)-r+1)時，總可以把兩個pebble移到某個特定的目標頂點上，滿足2-pebbling性質(zhì)的圖也滿足弱2-pebbling性質(zhì)。給定G的一種pebbling，G的一個傳送子圖是一條路x0,x1…xk，使得在頂點x0上至少有兩個pebble， 且除了可能xk外的其他頂點上至少有1個pebble。這時可以把1個pebble從x0傳送到xk。

下面我們給出多扇圖的定義。

聯(lián)圖G1∨G2[2]是指從并圖G1∪G2中連接圖G1的每個頂點和的G2每個頂點所得到的圖。設Pn為n個頂點的路，稱聯(lián)圖P1∨Pn為n+1階的扇形圖，記為Fn。 稱聯(lián)圖P1∨(Pn1∪Pn2∪…∪Pnm)為n1+n2+…+nm+1階多扇圖，記為Fn1,n2,…,nm。 如圖1所示。

圖1 多扇圖Fn1,n2,…,nm

Graham猜想指出對任意的連通圖G和H有f(G×H)≤f(G)f(H)?，F(xiàn)已在很少的幾種情形下驗證了Graham猜想，其中有1棵樹乘以1棵樹[3]，一個圈乘以一個圈[1]，一個完全圖乘以一個滿足2-pebbling性質(zhì)的圖[1]，一個完全二部圖乘以1個滿足2-pebbling性質(zhì)的圖[4]，一個扇圖乘以一個扇圖[5]，而且我們已經(jīng)知道了扇圖的pebbling數(shù)，以及扇圖滿足2-pebbling性質(zhì)，由此，本文給出了多扇圖的pebbling數(shù)，并證明了多扇圖滿足2-pebbling性質(zhì)，最后推導了一個多扇圖乘以一個具有2-pebbling性質(zhì)的圖滿足Graham猜想，由此可知兩個多扇圖的乘積也滿足Graham猜想。

在本文中，G表示一個簡單圖，其頂點集為V(G)，邊集為E(G)，對G的任意頂點v。P(v)代表v上的pebble的個數(shù)。

1 Fn1,n2,…,nm的pebbling數(shù)及其2-pebbling性質(zhì)

在這一部分，我們首先給出Fn1,n2,…,nm的pebbling數(shù)，再證明Fn1,n2,…,nm具有2-pebbling性質(zhì)。

定理1f(Fn1,n2,…,nm)=n1+n2+…+nm+2。

證明 我們把n1+n2+…+nm+1個pebble放在多扇圖Fn1,n2,…,nm上，如果p(v0)=0，p(vn1+n2+…+nm)=3，p(v2)=p(v3)=…=p(vn1)=…=p(vn1+n2+…+nm-1)=1，那么目標頂點v1無法得到1個pebble，故F(Fn1,n2,…,nm)≥n1+n2+…+nm+2。下面證明f(Fn1,n2,…,nm)≤n1+n2+…+nm+2。

首先，設目標頂點為v0，即p(v0)=0，則一定存在某個i≥1，使得p(vi)≥2。所以可以從vi處移1個pebble給v0。

其次，設目標頂點為vk，即p(vk)=0，k∈{1,2,…,n1+n2+…+nm}。若p(v0)≥2或p(vi)≥4(i≥1且i≠k)，則{v0,vk}或{vi,v0,vk}構(gòu)成一傳送子圖。所以vk可得到1個pebble。否則，p(v0)≤1且p(vi)≤3(i≥1且i≠k)。

(1)當p(v0)=1時，一定存在一個頂點v1，使得P(v1)≥2(i≥1且i≠k)，此時{vi,vo,vk}構(gòu)成一傳送子圖。vk可得到1個pebble。

(2)當p(v0)=0時，n1+n2+…+nm-1個頂點上被放置n1+n2+…+nm+2個pebble，故在除去頂點v0,vk之外的頂點中，至少有2個頂點滿足2≤p(vi),p(vj)≤3。則vi,vj分別可給v01個pebble，v0獲得2個pebble后可移1個pebble給vk。

綜上可知，f(Fn1,n2,…,nm)=n1+n2+…+nm+2。證畢

定理2 多扇圖Fn1,n2,…,nm滿足2-pebbling性質(zhì)。

證明 記p為多扇圖Fn1,n2,…,nm上的pebble個數(shù)，q為具有至少1個pebble的頂點個數(shù)，r為具有奇數(shù)個pebble的頂點個數(shù)，且p+q=2(n1+n2+…+nm+2)+1。設目標頂點為vi。若p(vi)=1，則除vi外，其余頂點的pebble個數(shù)為

2(n1+n2+…+nm+2)+1-q-1

≥2(n1+n2+…+nm+2)-(n1+n2+…+nm+1)

=n1+n2+…+nm+3>n1+n2+…+nm+2,

因為f(Fn1,n2,…,nm)=n1+n2+…+nm+2，利用這2(n1+n2+…+nm+2)+1-q-1個pebble，可以再往vi上放1個pebble。如果p(vi)=0，則考慮以下情形：

(1)i=0，即目標頂點為v0，而q+r≤2(n1+n2+…+nm)，則

p-r=2(n1+n2+…+nm+2)+1-q-r

≥2(n1+n2+…+nm+2)+1-2(n1+n2+…+nm)=5

從而至少可以從頂點v1,v2,…,vn1+n2+…+nm上移2個pebble到v0上。

(2)i≠0，不失一般性，設目標頂點為v1，即p(v1)=0，

1)如果p(v0)≥4， 那么可以利用v0上4個pebble移2個到v1上。

2)如果2≤p(v0)≤3， 那么可以從v0移1個pebble到v1上， 另外除v0和v1外， 其余頂點的pebble個數(shù)為

2(n1+n2+…+nm+2)+1-q-p(v0)≥2(n1+n2+…+nm+2)+1-(n1+n2+…+nm)-3

=n1+n2+…+nm+2=f(Fn1,n2,…,nm)

于是可以利用這2(n1+n2+…+nm+2)+1-q-p(v0)個pebble再往v1上放1個pebble。

3)如果p(v0)=1，那么q+r≤2(n1+n2+…+nm)，除v0和v1外，其余頂點的pebble個數(shù)為p-1，具有奇數(shù)個pebble的頂點個數(shù)為r-1，于是(p-1)-(r-1)=p-r=2(n1+n2+…+nm+2)+1-q-r≥5，由于p-r不可能為奇數(shù)，所以p-r≥6。從而至少可移3個pebble到v0，這時利用v0上的4個pebble移2個給v1。

4)如果p(v0)=0，那么q+r≤2(n1+n2+…+nm-1)，于是p-r=2(n1+n2+…+nm+2)+1-q-r≥7，所以p-r≥8，從而至少可移4個pebble到v0，再從v0移2個到v1上。證畢

2 Fn1,n2,…,nm的Graham猜想

設G和H為兩個圖，G和H的Descartes積G×H是一個圖，其頂點集為Descartes積V(G×H)=V(G)×V(H)={(x,y)|x∈V(G),y∈V(H)}，且兩個頂點(x,y)與(x′,y′)相鄰當且僅當x=x′，且{y,y′}∈E(H)，或者{x,x′}∈E(G)且y=y′?？梢杂脠D形來表示出G×H，即在G的每一個頂點處畫出一個H的圖形，并且把任一H中的每一個頂點和與此H相鄰的H中的對應頂點連接起來。用{x}×H(或G×{y})來表示頂點投射到V(G)上為頂點x(或投射到V(H)上為頂點y)的G×H的子圖。

首先給出三個引理，然后證明對于一個多扇圖和一個具有2-pebbling性質(zhì)的圖的乘積來說，Graham猜想成立。

引理1[1]如果G′是G的一個生成子圖，則f(G′)≥f(G)。

引理2[6]設K1,n為一個星形圖，則當n>1時，有f(K1,n)=n+2。

引理3[6]設G滿足2-pebbling性質(zhì)，則f(K1,n×G)≤f(K1,n)f(G)。

定理3 設G滿足2-pebbling性質(zhì)，則f(Fn1,n2,…,nm×G)≤f(Fn1,n2,…,nm)f(G)。

證明 由引理1，可知f(Fn1,n2,…,nm×G)≤f(K1,n1+n2+…+nm×G)。 由引理2和引理3，可得到f(K1,n1+n2+…+nm×G)≤(n1+n2+…+nm+2)f(G)。因此，我們有f(Fn1,n2,…,nm×G)≤f(Fn1,n2,…,nm)f(G)。證畢

由多扇圖滿足2-pebbling性質(zhì)，可得下面的推論：

推論f(Fn1,n2,…,nm×Fs1,s2,…,st)≤(n1+n2+…+nm+2)(s1+s2+…+st+2)。

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

[2] 王力工等,多扇圖中保Wiener指數(shù)的樹[J].湖南師范大學自然科學學報,2012,35(1):17-18.

[3] Moews D. Pebbling graphs[J]. Combin Theory(Series B), 1992, 55: 244-252.

[4] 馮榮權(quán),金珠英.完全二部圖乘積上的Graham pebbling猜想[J].中國數(shù)學(A輯),2001,31(3):199-203.

[5] FENG R Q, KIM J Y. Pebbling numbers of some graphs[J]. Science in China(Series A), 2002; 45(4): 470- 478.

[6] 胡蔚勇.星形圖乘積上的Graham pebbling猜想[J].無錫商業(yè)職業(yè)技術(shù)學院學報,2003,3(2):68-70.

The Pebbling Number of Multi-fan Graphs and Graham’s Conjecture

WANG Yan-qiu YE Yong-sheng

(CollegeofMathematicalScience,HuaibeiNormalUniversity,Huaibei235000,China)

The pebbling number of a graphG,f(G) , is the leastn, no matter hownpebbles are placed on the vertices ofG, a pebble can be moved to any vertex by a sequence of pebbling moves. A pebbling move consists of the removal of two pebbles vertex and the placement of one of those two pebbles on an adjacent vertex. Graham conjectured that for any connected graphsGandH,f(G×H)≤f(G)f(H) . Multi-fan graphFn1,n2,…,nmis a joint-graphP1∨(Pn1∪Pn2∪…∪Pnm) withn1+n2+…+nm+1 vertices. This paper shows thatf(Fn1,n2,…,nm)=n1+n2+…+nm+2 andFn1,n2,…,nmwith the 2-pebbling property. Graham’s conjecture holds of a multi-fan graphs by a graph with the 2-pebbling property. As a corollary, Graham’s conjecture holds when G and H are multi-fan graphs.

operational research; pebbling number; Graham’s conjecture; pebbling move; multi-fan graphs

2013-12-28

安徽省自然科學基金資助項目(1408085MA08; KJ2013Z279)

王艷秋(1989-)，女，安徽淮北人，碩士生，研究方向：圖論及其應用；葉永升(1964-)，男，安徽嘉山人，教授，碩士生導師，研究方向：圖論及其應用。

O157.5

A

1007-3221(2015)04- 0137- 04