In:
Graphs and Combinatorics, Springer Science and Business Media LLC, Vol. 36, No. 3 ( 2020-05), p. 803-829
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 $$\pi _{{{\,\mathrm{opt}\,}}}$$ π 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$$ P n □ P m was investigated in several papers (Bunde et al. in J Graph Theory 57(3):215–238, 2008; Xue and Yerger in Graphs Combin 32(3):1229–1247, 2016; Győri et al. in Period Polytech Electr Eng Comput Sci 61(2):217–223 2017). In this paper, we present a new method using some recent ideas to give a lower bound on $$\pi _{{{\,\mathrm{opt}\,}}}$$ π opt . We apply this technique to prove that $$\pi _{{{\,\mathrm{opt}\,}}}(P_n\square P_m)\ge \frac{2}{13}nm$$ π opt ( P n □ P m ) ≥ 2 13 n m . Our method also gives a new proof for $$\pi _{{{\,\mathrm{opt}\,}}}(P_n)=\pi _{{{\,\mathrm{opt}\,}}}(C_n)=\left\lceil \frac{2n}{3}\right\rceil$$ π opt ( P n ) = π opt ( C n ) = 2 n 3 .
Type of Medium:
Online Resource
ISSN:
0911-0119
,
1435-5914
DOI:
10.1007/s00373-020-02154-z
Language:
English
Publisher:
Springer Science and Business Media LLC
Publication Date:
2020
detail.hit.zdb_id:
1481435-3
SSG:
17,1
Permalink