A new lower bound on the pebbling number of the grid

Abstract

A pebbling move on a graph consists of removing $2$ pebbles from a vertex and adding $1$ pebble to one of the neighbouring vertices. A vertex is called reachable if we can put $1$ pebble on it after a sequence of moves. The optimal pebbling number of a graph is the minimum number $m$ such that there exists a distribution of $m$ pebbles so that each vertex is reachable. For the case of a square grid $n\times m$, Győri, Katona and Papp recently showed that its optimal pebbling number is at least $\frac{2}{13}nm\approx 0.1538nm$ and at most $\frac{2}{7}nm+O(n+m)\approx 0.2857nm$. We improve the lower bound to $\frac{5092}{28593}nm+O(m+n)\approx 0.1781nm$.

References in corpus (1)

• Constructions for the optimal pebbling of grids