Back to Search Start Over

A new lower bound on the pebbling number of the grid

Authors :
Petr, Jan
Portier, Julien
Stolarczyk, Szymon
Source :
Discrete Mathematics 346 (2023)
Publication Year :
2021

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\H{o}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$.

Subjects

Subjects :
Mathematics - Combinatorics

Details

Database :
arXiv
Journal :
Discrete Mathematics 346 (2023)
Publication Type :
Report
Accession number :
edsarx.2111.13173
Document Type :
Working Paper
Full Text :
https://doi.org/10.1016/j.disc.2022.113212