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 ver...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.展开更多
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...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.展开更多
基金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.
基金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 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.
