Optimal pebbling number of the square grid

DOI10.1007/S00373-020-02154-ZMaRDI QIDQ2175808zbMATH OpenOpenAlexFDO

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

Publication date 30 April 2020

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

Copyright license Creative Commons Attribution 4.0 International

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

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)

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

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

Cites work

• scientific article; zbMATH DE number 1145909 (Why is no real title available?)
• Optimal pebbling on grids
• Pebbling and optimal pebbling in graphs
• Pebbling graphs
• Pebbling in Hypercubes
• The Complexity of Graph Pebbling
• The cover pebbling number of graphs
• The optimal pebbling number of staircase graphs
• The optimal pebbling number of the caterpillar
• The optimal pebbling number of the complete \(m\)-ary tree
• t-pebbling and extensions

Cited in

(5)

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

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)