Pebbling Graph Products

Abstract

A pebbling step on a graph consists of removing two pebbles from one vertex and placing one pebble on an adjacent vertex. We consider all weight functions defined on the vertices of a graph that satisfy some property $P$. The $P$-pebbling number of a graph is the minimum number of pebbles needed in an arbitrary initial configuration so that, for any such weight function, there is a sequence of pebbling moves at the end of which each vertex has at least as many pebbles as required by the weight function. Some natural properties on graph products are induced by properties defined on the factor graphs. In this paper, we give a bound for the $P^{\prime }$-pebbling number associated with a particular kind of product property $P^{\prime }$ in terms of the $P_i$-pebbling numbers associated with the factor properties $P_1$ and $P_2$. We do this by introducing color pebbling, which may be of interest in its own right.