Pebbling numbers of some graphs  

作　　者：冯荣权 Ju Young Kim 

机构地区：[1]School of Mathematical Sciences, Peking University, Beijing 100871, China [2]Department of Mathematics, Catholic University of Daegu, Kyongsan 713-702, Korea

出　　处：《Science China Mathematics》2002年第4期470-478,共9页中国科学：数学（英文版）

基　　金：This work was supported by the National Natural Science Foundation of China(Grant No. 10001005) and by RFDP of China.

摘　　要：Chung defined a pebbling move on a graphG as the removal of two pebbles from one vertex and the addition of one pebble to an adjacent vertex. The pebbling number of a connected graphG, f(G), is the leastn such that any distribution ofn pebbles onG allows one pebble to be moved to any specified but arbitrary vertex by a sequence of pebbling moves. Graham conjectured that for any connected graphsG andH, f(G xH) ≤ f(G)f(H). In the present paper the pebbling numbers of the product of two fan graphs and the product of two wheel graphs are computed. As a corollary, Graham’s conjecture holds whenG andH are fan graphs or wheel graphs.Chung defined a pebbling move on a graph G as the removal of two pebbles from one vertex and the addition of one pebble to an adjacent vertex. The pebbling number of a connected graph G, f(G), is the least n such that any distribution of n pebbles on G allows one pebble to be moved to any specified but arbitrary vertex by a sequence of pebbling moves. Graham conjectured that for any connected graphs G and H, f(G×H)≤f(G)f(H). In the present paper the pebbling numbers of the product of two fan graphs and the product of two wheel graphs are computed. As a corollary, Graham's conjecture holds when G and H are fan graphs or wheel graphs.

关 键 词：pebbling  Graham's conjecture  CARTESIAN product  fan graph  wheel graph. 

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