On pebbling graphs

Abstract

The pebbling number of a graph G, f(G), is the least m such that, however m 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. We give another proof that f(Q^n) = 2^n (Chung) and show that for most graphs f(G) = |V(G)| or |V(G)| + 1. We also find explicitly for certain classes of graphs (i.e. for odd cycles and squares of paths). characterize efficient graphs, show that most graphs have the 2-pebbling property, and obtain some results on optimal pebbling.

Additional details