Abstract: 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. Graham conjectured that for any connected graphs G and H,f(G×H)f(G)f(H) . Multi-fan graph F_n1,n2,…,nm is a joint-graph P₁∨(P_n1∪P_n2∪…∪P_nm) with n₁+n₂+…+n_m+1 vertices. This paper shows that f(F_n1,n2,…,nm)= n₁+n₂+…+n_m+2 and F_n1,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.

Key words: operational research, pebbling number, Graham’s conjecture, pebbling move, multi-fan graphs

摘要： 图G的pebbling数f(G)是最小的整数n,使得不论n个pebble如何放置在G的顶点上,总可以通过一系列的pebbling移动把1个pebble移到任意一个顶点上,其中一个pebbling移动是从一个顶点处移走两个pebble而把其中的一个移到与其相邻的一个顶点上。Graham猜想对于任意的连通图G和H有f(G×H)f(G)f(H)。多扇图F_n1,n2,…,nm是指阶为n₁+n₂+…+n_m+1的联图P₁∨(P_n1∪P_n2∪…∪P_nm)。本文首先给出了多扇图的pebbling数,然后证明了多扇图F_n1,n2,…,nm具有2-pebbling性质,最后论述了对于一个多扇图和一个具有2-pebbling性质的图的乘积来说,Graham猜想是成立的。作为一个推论,当G和H都是多扇图时,Graham猜想成立。

关键词: 运筹学, pebbling数, Graham猜想, pebbling移动, 多扇图