Abstract
Given a distribution of pebbles on the vertices of a graph G, a pebbling move takes two pebbles from one vertex and puts one on a neighboring vertex. The pebbling number Ξ (G) is the least k such that for every distribution of k pebbles and every vertex r, a pebble can be moved to r. The optimal pebbling number Ξ ~OPT~(G) is the least k such that some distribution of k pebbles permits reaching each vertex.
Using new tools (such as the βSquishingβ and βSmoothingβ Lemmas), we give short proofs of prior results on these parameters for paths, cycles, trees, and hypercubes, a new linearβtime algorithm for computing Ξ (G) on trees, and new results on Ξ ~OPT~(G). If G is connected and has n vertices, then $\Pi_{\rm OPT}(G)\le \lceil{2n/3}\rceil$ (sharp for paths and cycles). Let a~n,k~ be the maximum of Ξ ~OPT~(G) when G is a connected nβvertex graph with Ξ΄(G)ββ₯βk. Always $2 \lceil{n \over {k+1}}\rceil \le a_{{n},k}\le 4 \lceil{n \over {k+1}}\rceil$, with a better lower bound when k is a nontrivial multiple of 3. Better upper bounds hold for nβvertex graphs with minimum degree k having large girth; a special case is $\Pi_{{\rm OPT}}({G})\le {16}{n}/{({k}^{2}+{17})}$ when G has girth at least 5 and kββ₯β4. Finally, we compute Ξ ~OPT~(G) in special families such as prisms and MΓΆbius ladders. Β© 2007 Wiley Periodicals, Inc. J Graph Theory 57: 215β238, 2008