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

王艷秋, 葉永升

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

?

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

王艷秋, 葉永升

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

圖G的pebbling數(shù)f(G)是最小的整數(shù)n，使得不論n個(gè)pebble如何放置在G的頂點(diǎn)上，總可以通過一系列的pebbling移動把1個(gè)pebble移到任意一個(gè)頂點(diǎn)上，其中一個(gè)pebbling移動是從一個(gè)頂點(diǎn)處移走兩個(gè)pebble而把其中的一個(gè)移到與其相鄰的一個(gè)頂點(diǎn)上。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ì)，最后論述了對于一個(gè)多扇圖和一個(gè)具有2-pebbling性質(zhì)的圖的乘積來說，Graham猜想是成立的。作為一個(gè)推論，當(dāng)G和H都是多扇圖時(shí)，Graham猜想成立。

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

0 引言

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

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

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

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

聯(lián)圖G1∨G2[2]是指從并圖G1∪G2中連接圖G1的每個(gè)頂點(diǎn)和的G2每個(gè)頂點(diǎn)所得到的圖。設(shè)Pn為n個(gè)頂點(diǎ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)已在很少的幾種情形下驗(yàn)證了Graham猜想，其中有1棵樹乘以1棵樹[3]，一個(gè)圈乘以一個(gè)圈[1]，一個(gè)完全圖乘以一個(gè)滿足2-pebbling性質(zhì)的圖[1]，一個(gè)完全二部圖乘以1個(gè)滿足2-pebbling性質(zhì)的圖[4]，一個(gè)扇圖乘以一個(gè)扇圖[5]，而且我們已經(jīng)知道了扇圖的pebbling數(shù)，以及扇圖滿足2-pebbling性質(zhì)，由此，本文給出了多扇圖的pebbling數(shù)，并證明了多扇圖滿足2-pebbling性質(zhì)，最后推導(dǎo)了一個(gè)多扇圖乘以一個(gè)具有2-pebbling性質(zhì)的圖滿足Graham猜想，由此可知兩個(gè)多扇圖的乘積也滿足Graham猜想。

在本文中，G表示一個(gè)簡單圖，其頂點(diǎn)集為V(G)，邊集為E(G)，對G的任意頂點(diǎn)v。P(v)代表v上的pebble的個(gè)數(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個(gè)pebble放在多扇圖Fn1,n2,…,nm上，如果p(v0)=0，p(vn1+n2+…+nm)=3，p(v2)=p(v3)=…=p(vn1)=…=p(vn1+n2+…+nm-1)=1，那么目標(biāo)頂點(diǎn)v1無法得到1個(gè)pebble，故F(Fn1,n2,…,nm)≥n1+n2+…+nm+2。下面證明f(Fn1,n2,…,nm)≤n1+n2+…+nm+2。

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

其次，設(shè)目標(biāo)頂點(diǎn)為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個(gè)pebble。否則，p(v0)≤1且p(vi)≤3(i≥1且i≠k)。

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

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

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

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

證明 記p為多扇圖Fn1,n2,…,nm上的pebble個(gè)數(shù)，q為具有至少1個(gè)pebble的頂點(diǎn)個(gè)數(shù)，r為具有奇數(shù)個(gè)pebble的頂點(diǎn)個(gè)數(shù)，且p+q=2(n1+n2+…+nm+2)+1。設(shè)目標(biāo)頂點(diǎn)為vi。若p(vi)=1，則除vi外，其余頂點(diǎn)的pebble個(gè)數(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,

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

(1)i=0，即目標(biāo)頂點(diǎn)為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

從而至少可以從頂點(diǎn)v1,v2,…,vn1+n2+…+nm上移2個(gè)pebble到v0上。

(2)i≠0，不失一般性，設(shè)目標(biāo)頂點(diǎn)為v1，即p(v1)=0，

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

2)如果2≤p(v0)≤3， 那么可以從v0移1個(gè)pebble到v1上， 另外除v0和v1外， 其余頂點(diǎn)的pebble個(gè)數(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)個(gè)pebble再往v1上放1個(gè)pebble。

3)如果p(v0)=1，那么q+r≤2(n1+n2+…+nm)，除v0和v1外，其余頂點(diǎn)的pebble個(gè)數(shù)為p-1，具有奇數(shù)個(gè)pebble的頂點(diǎn)個(gè)數(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個(gè)pebble到v0，這時(shí)利用v0上的4個(gè)pebble移2個(gè)給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個(gè)pebble到v0，再從v0移2個(gè)到v1上。證畢

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

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

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

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

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

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

定理3 設(shè)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].湖南師范大學(xué)自然科學(xué)學(xué)報(bào),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ù)學(xué)(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ù)學(xué)院學(xué)報(bào),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

安徽省自然科學(xué)基金資助項(xiàng)目(1408085MA08; KJ2013Z279)

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

O157.5

A

1007-3221(2015)04- 0137- 04