Pebbling and optimal pebbling in graphs

Abstract

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