Download
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 ΠOPT(G)<=ceil(2n/3) (sharp for paths and cycles). Let an,k be the maximum of ΠOPT(G) when G is a connected n-vertex graph with minimum degree at least k. Always 2 ceil(n/(k+1)) <= an,k <= 4 ceil(n/(k+1)), 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 ΠOPT(G) <= 16n/(k2+17) when G has girth at least 5 and k >= 4. Finally, we compute ΠOPT(G) in special families such as prisms and Mobius ladders.