{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T10:10:23Z","timestamp":1750155023337,"version":"3.37.3"},"reference-count":13,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2020,3,24]],"date-time":"2020-03-24T00:00:00Z","timestamp":1585008000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2020,3,24]],"date-time":"2020-03-24T00:00:00Z","timestamp":1585008000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100003549","name":"Orsz\u00e1gos Tudom\u00e1nyos Kutat\u00e1si Alapprogramok","doi-asserted-by":"publisher","award":["K132696","K132696"],"award-info":[{"award-number":["K132696","K132696"]}],"id":[{"id":"10.13039\/501100003549","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100003549","name":"Orsz\u00e1gos Tudom\u00e1nyos Kutat\u00e1si Alapprogramok","doi-asserted-by":"publisher","award":["K124171","K124171"],"award-info":[{"award-number":["K124171","K124171"]}],"id":[{"id":"10.13039\/501100003549","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Graphs and Combinatorics"],"published-print":{"date-parts":[[2020,5]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>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 <jats:inline-formula><jats:alternatives><jats:tex-math>$$\\pi _{{{\\,\\mathrm{opt}\\,}}}$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:msub><mml:mi>\u03c0<\/mml:mi><mml:mrow><mml:mspace\/><mml:mi>opt<\/mml:mi><mml:mspace\/><\/mml:mrow><\/mml:msub><\/mml:math><\/jats:alternatives><\/jats:inline-formula> 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 <jats:inline-formula><jats:alternatives><jats:tex-math>$$P_n\\square P_m$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mrow><mml:msub><mml:mi>P<\/mml:mi><mml:mi>n<\/mml:mi><\/mml:msub><mml:mo>\u25a1<\/mml:mo><mml:msub><mml:mi>P<\/mml:mi><mml:mi>m<\/mml:mi><\/mml:msub><\/mml:mrow><\/mml:math><\/jats:alternatives><\/jats:inline-formula> was investigated in several papers (Bunde et al. in J Graph Theory 57(3):215\u2013238, 2008; Xue and Yerger in Graphs Combin 32(3):1229\u20131247, 2016; Gy\u0151ri et al. in Period Polytech Electr Eng Comput Sci 61(2):217\u2013223 2017). In this paper, we present a new method using some recent ideas to give a lower bound on <jats:inline-formula><jats:alternatives><jats:tex-math>$$\\pi _{{{\\,\\mathrm{opt}\\,}}}$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:msub><mml:mi>\u03c0<\/mml:mi><mml:mrow><mml:mspace\/><mml:mi>opt<\/mml:mi><mml:mspace\/><\/mml:mrow><\/mml:msub><\/mml:math><\/jats:alternatives><\/jats:inline-formula>. We apply this technique to prove that <jats:inline-formula><jats:alternatives><jats:tex-math>$$\\pi _{{{\\,\\mathrm{opt}\\,}}}(P_n\\square P_m)\\ge \\frac{2}{13}nm$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mrow><mml:msub><mml:mi>\u03c0<\/mml:mi><mml:mrow><mml:mspace\/><mml:mi>opt<\/mml:mi><mml:mspace\/><\/mml:mrow><\/mml:msub><mml:mrow><mml:mo>(<\/mml:mo><mml:msub><mml:mi>P<\/mml:mi><mml:mi>n<\/mml:mi><\/mml:msub><mml:mo>\u25a1<\/mml:mo><mml:msub><mml:mi>P<\/mml:mi><mml:mi>m<\/mml:mi><\/mml:msub><mml:mo>)<\/mml:mo><\/mml:mrow><mml:mo>\u2265<\/mml:mo><mml:mfrac><mml:mn>2<\/mml:mn><mml:mn>13<\/mml:mn><\/mml:mfrac><mml:mi>n<\/mml:mi><mml:mi>m<\/mml:mi><\/mml:mrow><\/mml:math><\/jats:alternatives><\/jats:inline-formula>. Our method also gives a new proof for <jats:inline-formula><jats:alternatives><jats:tex-math>$$\\pi _{{{\\,\\mathrm{opt}\\,}}}(P_n)=\\pi _{{{\\,\\mathrm{opt}\\,}}}(C_n)=\\left\\lceil \\frac{2n}{3}\\right\\rceil$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mrow><mml:msub><mml:mi>\u03c0<\/mml:mi><mml:mrow><mml:mspace\/><mml:mi>opt<\/mml:mi><mml:mspace\/><\/mml:mrow><\/mml:msub><mml:mrow><mml:mo>(<\/mml:mo><mml:msub><mml:mi>P<\/mml:mi><mml:mi>n<\/mml:mi><\/mml:msub><mml:mo>)<\/mml:mo><\/mml:mrow><mml:mo>=<\/mml:mo><mml:msub><mml:mi>\u03c0<\/mml:mi><mml:mrow><mml:mspace\/><mml:mi>opt<\/mml:mi><mml:mspace\/><\/mml:mrow><\/mml:msub><mml:mrow><mml:mo>(<\/mml:mo><mml:msub><mml:mi>C<\/mml:mi><mml:mi>n<\/mml:mi><\/mml:msub><mml:mo>)<\/mml:mo><\/mml:mrow><mml:mo>=<\/mml:mo><mml:mfenced><mml:mfrac><mml:mrow><mml:mn>2<\/mml:mn><mml:mi>n<\/mml:mi><\/mml:mrow><mml:mn>3<\/mml:mn><\/mml:mfrac><\/mml:mfenced><\/mml:mrow><\/mml:math><\/jats:alternatives><\/jats:inline-formula>.<\/jats:p>","DOI":"10.1007\/s00373-020-02154-z","type":"journal-article","created":{"date-parts":[[2020,3,24]],"date-time":"2020-03-24T07:02:32Z","timestamp":1585033352000},"page":"803-829","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["Optimal Pebbling Number of the Square Grid"],"prefix":"10.1007","volume":"36","author":[{"given":"Ervin","family":"Gy\u0151ri","sequence":"first","affiliation":[]},{"given":"Gyula Y.","family":"Katona","sequence":"additional","affiliation":[]},{"given":"L\u00e1szl\u00f3 F.","family":"Papp","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2020,3,24]]},"reference":[{"issue":"3","key":"2154_CR1","doi-asserted-by":"publisher","first-page":"215","DOI":"10.1002\/jgt.20278","volume":"57","author":"DP Bunde","year":"2008","unstructured":"Bunde, D.P., Chambers, E.W., Cranston, D., Milans, K., West, D.B.: Pebbling and optimal pebbling in graphs. J. Graph Theory 57(3), 215\u2013238 (2008)","journal-title":"J. Graph Theory"},{"issue":"3","key":"2154_CR2","doi-asserted-by":"publisher","first-page":"1229","DOI":"10.1007\/s00373-015-1615-5","volume":"32","author":"C Xue","year":"2016","unstructured":"Xue, C., Yerger, C.: Optimal Pebbling on grids. Graphs Combin. 32(3), 1229\u20131247 (2016)","journal-title":"Graphs Combin."},{"issue":"2","key":"2154_CR3","doi-asserted-by":"publisher","first-page":"217","DOI":"10.3311\/PPee.9724","volume":"61","author":"E Gy\u0151ri","year":"2017","unstructured":"Gy\u0151ri, E., Katona, G.Y., Papp, L.F.: Constructions for the optimal pebbling of grids. Period. Polytech. Electr. Eng. Comput. Sci. 61(2), 217\u2013223 (2017)","journal-title":"Period. Polytech. Electr. Eng. Comput. Sci."},{"issue":"4","key":"2154_CR4","doi-asserted-by":"publisher","first-page":"467","DOI":"10.1137\/0402041","volume":"2","author":"FRK Chung","year":"1989","unstructured":"Chung, F.R.K.: Pebbling in hypercubes SIAM. J. Discr. Math 2(4), 467\u2013472 (1989)","journal-title":"J. Discr. Math"},{"issue":"3","key":"2154_CR5","doi-asserted-by":"publisher","first-page":"769","DOI":"10.1137\/050636218","volume":"20","author":"K Milans","year":"2006","unstructured":"Milans, K., Clark, B.: The complexity of graph pebbling SIAM. J. Discr. Math. 20(3), 769\u2013798 (2006)","journal-title":"J. Discr. Math."},{"key":"2154_CR6","unstructured":"Friedman, T., Wyels, C.: Optimal pebbling of paths and cycles. arXiv:math\/0506076 [math.CO]"},{"key":"2154_CR7","first-page":"65","volume":"107","author":"L Pachter","year":"1995","unstructured":"Pachter, L., Snevily, H.S., Voxman, B.: On pebbling graphs. Congressus Numerantium 107, 65\u201380 (1995)","journal-title":"Congressus Numerantium"},{"issue":"2A","key":"2154_CR8","doi-asserted-by":"publisher","first-page":"419","DOI":"10.11650\/twjm\/1500405346","volume":"13","author":"H Fu","year":"2009","unstructured":"Fu, H., Shiue, C.: The optimal pebbling number of the caterpillar. Taiwan. J. Math. 13(2A), 419\u2013429 (2009)","journal-title":"Taiwan. J. Math."},{"issue":"1\u20133","key":"2154_CR9","doi-asserted-by":"publisher","first-page":"89","DOI":"10.1016\/S0012-365X(00)00008-X","volume":"222","author":"H Fu","year":"2000","unstructured":"Fu, H., Shiue, C.: The optimal pebbling number of the complete m-ary tree. Discr. Math. 222(1\u20133), 89\u2013100 (2000)","journal-title":"Discr. Math."},{"key":"2154_CR10","doi-asserted-by":"publisher","first-page":"2148","DOI":"10.1016\/j.disc.2018.06.042","volume":"342","author":"E Gy\u0151ri","year":"2019","unstructured":"Gy\u0151ri, E., Katona, G.Y., Papp, L.F., Tompkins, C.: The optimal pebbling number of staircase graphs. Discr. Math. 342, 2148\u20132157 (2019)","journal-title":"Discr. Math."},{"key":"2154_CR11","unstructured":"Herscovici, D. S., Hester, B. D., Hurlbert, G. H.: Diameter bounds, fractional pebbling, and pebbling with arbitrary target distributions manuscript"},{"key":"2154_CR12","doi-asserted-by":"publisher","first-page":"15","DOI":"10.1016\/j.disc.2005.03.009","volume":"296","author":"B Crull","year":"2005","unstructured":"Crull, B., Cundiff, T., Feltman, P., Hurlbert, G.H., Pudwell, L., Szaniszlo, Z., Tuza, Z.: The cover pebbling number of graphs. Discr. Math. 296, 15\u201323 (2005)","journal-title":"Discr. Math."},{"key":"2154_CR13","doi-asserted-by":"publisher","first-page":"244","DOI":"10.1016\/0095-8956(92)90043-W","volume":"55","author":"D Moews","year":"1992","unstructured":"Moews, D.: Pebbling graphs. J. Combin. Theory (B) 55, 244\u2013252 (1992)","journal-title":"J. Combin. Theory (B)"}],"container-title":["Graphs and Combinatorics"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00373-020-02154-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00373-020-02154-z\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00373-020-02154-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,3,24]],"date-time":"2021-03-24T00:27:28Z","timestamp":1616545648000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00373-020-02154-z"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,3,24]]},"references-count":13,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2020,5]]}},"alternative-id":["2154"],"URL":"https:\/\/doi.org\/10.1007\/s00373-020-02154-z","relation":{},"ISSN":["0911-0119","1435-5914"],"issn-type":[{"type":"print","value":"0911-0119"},{"type":"electronic","value":"1435-5914"}],"subject":[],"published":{"date-parts":[[2020,3,24]]},"assertion":[{"value":"11 October 2018","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"24 February 2020","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"24 March 2020","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}