Back to Search
Start Over
A new lower bound on the pebbling number of the grid
- 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 :
- Mathematics - Combinatorics
Subjects
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