Bounds for the pebbling number of product graphs

Let G be a connected graph. Given a configuration of a fixed number of pebbles on the vertex set of G, a pebbling move on G is the process of removing two pebbles from a vertex and adding one pebble on an adjacent vertex. The pebbling number of G, denoted by \pi(G), is defined to be the least number of pebbles to guarantee that there is a sequence of pebbling movement that places at least one pebble on each vertex v, for any configuration of pebbles on G. In this paper, we improve the upper bound of \pi(G\square H) from ۲\pi(G)\pi(H) to \left(۲-\frac{۱}{\min\{\pi(G),\pi(H)\}}\right)\pi(G)\pi(H) where \pi(G), \pi(H) and \pi(G\square H) are the pebbling number of graphs G, H and the Cartesian product graph G\square H, respectively. Moreover, we also discuss such bound for strong product graphs, cross product graphs and coronas.

Keywords:

Graph pebbling , Graham's conjecture , product graph , corona