Optimal pebbling number of the square grid

Abstract

A pebbling move on a graph removes two pebbles from a vertex and adds one pebble to an adjacent vertex. A vertex is reachable from a pebble distribution if it is possible to move a pebble to that vertex using pebbling moves. The optimal pebbling number ${\pi }_{opt}$ is the smallest number m needed to guarantee a pebble distribution of m pebbles from which any vertex is reachable. The optimal pebbling number of the square grid graph $P_n\square P_m$ was investigated in several papers. In this paper, we present a new method using some recent ideas to give a lower bound on ${\pi }_{opt}$. We apply this technique to prove that ${\pi }_{opt}(P_n\square P_m)\ge \frac{2}{13}nm$. Our method also gives a new proof for ${\pi }_{opt}(P_n)={\pi }_{opt}(C_n)=\lceil \frac{2n}{3}\rceil$.