A new lower bound on the optimal pebbling number of the grid

DOI10.1016/J.DISC.2022.113212zbMATH Open1502.05166arXiv2111.13173OpenAlexW4304099456MaRDI QIDQ2092437FDOQ2092437

Julien Portier, Jan Petr, Szymon Stolarczyk

Publication date: 2 November 2022

Published in: Discrete Mathematics (Search for Journal in Brave)

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 $nimesm$, GyH{o}ri, Katona and Papp recently showed that its optimal pebbling number is at least $frac213nmapprox0.1538nm$ and at most $frac27nm+O(n+m)approx0.2857nm$. We improve the lower bound to $frac509228593nm+O(m+n)approx0.1781nm$.

Full work available at URL: https://arxiv.org/abs/2111.13173

zbMATH Keywords

graph pebblingsquare grid

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Games on graphs (graph-theoretic aspects) (05C57) Games involving graphs (91A43)

Cites Work

• Pebbling in Hypercubes
• Optimally pebbling hypercubes and powers
• Pebbling and optimal pebbling in graphs
• The Complexity of Graph Pebbling
• The optimal pebbling number of the complete \(m\)-ary tree
• Optimal pebbling number of the square grid

Cited In (4)

• A note on optimal pebbling of hypercubes
• An improved upper bound for the pebbling threshold of the \(n\)-path
• A tight bound for black and white pebbles on the pyramid
• Girth, Pebbling, and Grid Thresholds

This page was built for publication: A new lower bound on the optimal pebbling number of the grid

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2092437)