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 a bound of Bukh by showing that the pebbling number of a graph of diameter three on n vertices is at most ⌊ 3 n / 2 ⌋ + 2 , and this bound is best possible. Further, we obtain an asymptotic bound of 3 n / 2 + Θ ( 1 ) for the pebbling number of graphs of diameter four. Finally, we prove an asymptotic bound for pebbling graphs of arbitrary diameter, namely that the pebbling number for a diameter d graph on n vertices is at most( 2 ⌈ d 2 ⌉ − 1 ) n + C ′ ( d ) , whereC ′ ( d )is a constant depending upon d . This also improves another bound of Bukh.