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

DOI10.1016/J.DISC.2022.113212MaRDI QIDQ2092437zbMATH OpenOpenAlexFDO

Authors Jan Petr, Julien Portier, Szymon Stolarczyk

Publication date 2 November 2022

Published in Discrete Mathematics (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

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)

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$.

Recommendations

• Optimal pebbling number of the square grid
• Optimal pebbling on grids
• The optimal pebbling number of staircase graphs
• Optimal pebbling of graphs
• The optimal pebbling number of square of paths and cycles.

Cites work

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

Cited in

(7)

• Girth, Pebbling, and Grid Thresholds
• A note on optimal pebbling of hypercubes
• Optimal pebbling number of graphs with given minimum degree
• An improved upper bound for the pebbling threshold of the \(n\)-path
• Optimal pebbling number of the square grid
• A tight bound for black and white pebbles on the pyramid
• Optimal pebbling on grids

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)