Pebbling Graphs of Fixed Diameter

Given a configuration of indistinguishable pebbles on the vertices of a connected graph G on n vertices, a pebbling move is defined as the removal of two pebbles from some vertex, and the placement of one pebble on an adjacent vertex. The m ‐pebbling number of a graph G ,π m ( 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 m pebbles on v . When m = 1 , it is simply called the pebbling number of a graph. We prove that if G is a graph of diameter d and k , m ≥ 1 are integers, thenπ m ( G ) ≤ f ( k ) n + 2 k + d m + ( 2 k ( 2 d − 1 ) − f ( k ) ) d o m k ( G ) , where d o m k ( G )denotes the size of the smallest distance k dominating set, that is the smallest subset of vertices such that every vertex is at most distance k from the set, and, f ( k ) = ( 2 k − 1 ) / k . This generalizes the work of Chan and Godbole (Discrete Math 208 (2008), 15–23) who proved this formula for k = m = 1 . As a corollary, we prove thatπ m ( G ) ≤ f ( ⌈ d / 2 ⌉ ) n + O ( m + n ln n ) . Furthermore, we prove that if d is odd, thenπ m ( G ) ≤ f ( ⌈ d / 2 ⌉ ) n + O ( m ) , which in the case of m = 1 answers for odd d , up to a constant additive factor, a question of Bukh (J Graph Theory 52 (2006), 353–357) about the best possible bound on the pebbling number of a graph with respect to its diameter.