Optimal pebbling number of the square grid

DOI10.1007/S00373-020-02154-ZzbMATH Open1439.05155arXiv1810.05266OpenAlexW3013431172MaRDI QIDQ2175808FDOQ2175808

Ervin Győri, László F. Papp, Gyula Y. Katona

Publication date: 30 April 2020

Published in: Graphs and Combinatorics (Search for Journal in Brave)

Abstract: A pebbling move on a graph removes two pebbles from a vertex and adds one pebble to an adjacent vertex. A vertex is reachable from a pebble distribution if it is possible to move a pebble to that vertex using pebbling moves. The optimal pebbling number $p{i}_{opt}$ is the smallest number m needed to guarantee a pebble distribution of m pebbles from which any vertex is reachable. The optimal pebbling number of the square grid graph $P_{n}square{P}_m$ was investigated in several papers. In this paper, we present a new method using some recent ideas to give a lower bound on $p{i}_{opt}$. We apply this technique to prove that $p{i}_{opt}(P_{n}square{P}_m)geqfrac213nm$. Our method also gives a new proof for $p{i}_{opt}(P_n)=p{i}_{opt}(C_n)=leftlceilfrac2n3ightceil$.

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

Recommendations

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

zbMATH Keywords

graph pebblingoptimal pebblingsquare grid graph

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Combinatorial optimization (90C27) Extremal problems in graph theory (05C35) Games on graphs (graph-theoretic aspects) (05C57) Games involving graphs (91A43)

Cites Work

• Pebbling in Hypercubes
• Pebbling graphs
• Optimal pebbling on grids
• \(t\)-pebbling and extensions
• Title not available (Why is that?)
• Pebbling and optimal pebbling in graphs
• The Complexity of Graph Pebbling
• The optimal pebbling number of the complete \(m\)-ary tree
• The cover pebbling number of graphs
• The optimal pebbling number of the caterpillar
• The optimal pebbling number of staircase graphs

Cited In (1)

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

This page was built for publication: Optimal pebbling number of the square grid

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