Graham's pebbling conjecture on product of complete bipartite graphs  

作　　者：冯荣权 金珠英 

出　　处：《Science China Mathematics》2001年第7期817-822,共6页中国科学：数学（英文版）

基　　金：This work was supported by the National Natural Science Foundation of China (Grant Nos. 49873002, 10001005).

摘　　要：The pebbling number of a graph G,f(G),is the least n such that,no matter how n pebbles are placed on the vertices of G,we can move a pebble to any vertex by a sequence of moves,each move taking two pebbles off one vertex and placing one on an adjacent vertex.Graham conjectured that for any connected graphs G and H,f(G×H)≤f(G)f(H).We show that Graham's conjecture holds true of a complete bipartite graph by a graph with the two-pebbling property.As a corollary,Graham's conjecture holds when G and H are complete bipartite graphs.The pebbling number of a graph G, f( G), is the least n such that, no matter how n pebbles are placed on the vertices of G, we can move a pebble to any vertex by a sequence of moves, each move taking two pebbles off one vertex and placing one on an adjacent vertex. Graham conjectured that for any connected graphs G and H, f( G ×H) ≤f( G) f( H). We show that Graham's conjecture holds true of a complete bipartite graph by a graph with the two-pebbling property. As a corollary, Graham's conjecture holds when G and H are complete bipartite graphs.

关 键 词：PEBBLING Graham’s conjecture Cartesian product complete bipartite graph. 

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