Pebbling Graphs of Diameter Three and Four

Given a configuration of pebbles on the vertices of a connected graph G, a pebbling move is defined as the removal of two pebbles from some vertex, and the placement of one of these on an adjacent vertex. The pebbling number of a graph G is the smallest integer k such that for each vertex v and each configuration of k pebbles on G there is a sequence of pebbling moves that places at least one pebble on v. We improve on the bound of Bukh by showing that the pebbling number of a graph of diameter three on n vertices is at most ⌊3n/2⌋+2, and this bound is best possible. We obtain an asymptotically best possible bound of 3n/2+Θ(1) for the pebbling number of graphs of diameter four. Finally, we prove an asymptotic upper bound for the pebbling number of graphs of diameter d, namely , and this also improves a bound given by Bukh.