多扇图的Pebbling数和Graham猜想  

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

作　　者：王艳秋[1] 叶永升[1] 

机构地区：[1]淮北师范大学数学科学学院,安徽淮北235000

出　　处：《运筹与管理》2015年第4期137-140,共4页Operations Research and Management Science

基　　金：安徽省自然科学基金资助项目(1408085MA08;KJ2013Z279)

摘　　要：图G的pebbling数f(G)是最小的整数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的联图P1∨(Pn1∪Pn2∪…∪Pnm)。本文首先给出了多扇图的pebbling数,然后证明了多扇图Fn1,n2,…,nm具有2-pebbling性质,最后论述了对于一个多扇图和一个具有2-pebbling性质的图的乘积来说,Graham猜想是成立的。作为一个推论,当G和H都是多扇图时,Graham猜想成立。The pebbling number of a graph G,f（G） , is the least n, no matter how n pebbles are placed on the vertices of G, 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. Gra- ham conjectured that for any connected graphs G and H,f（G×H）≤f（G）f（H）. Multi-fan graph Fn1,n2,…,nm is a joint-graph P1∨（Pn1∪Pn2∪…∪Pnm） with n1 ＋n2 ＋ … ＋ nm ＋ 1 vertices. This paper shows that f（ Fn1.,n2,....nm） = n1 ＋ n2 ＋ ... ＋ nm ＋ 2 and Fn1,n2,...nm with 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.

关 键 词：运筹学 PEBBLING数 GRAHAM猜想 pebbling移动 多扇图 

分 类 号：O157.5[理学—数学]