Research article Special Issues

Distance 2-restricted optimal pebbling in cycles

  • Received: 19 November 2024 Revised: 19 February 2025 Accepted: 21 February 2025 Published: 28 February 2025
  • MSC : 05C38, 05C78

  • Let $ G $ be a graph and let $ \delta $ be a distribution of pebbles on $ G $. A pebbling move on the graph $ G $ consists of removing two pebbles from one vertex and then placing one pebble at an adjacent vertex. Given a positive integer $ d $, if we can move pebbles to any target vertex $ v $ in $ G $ only from the vertices in the set $ N_d[v] = \{u\in V(G):d(u, v)\le d\} $ by pebbling moves, where $ d(u, v) $ is the distance between $ u $ and $ v $, then such a graph pebbling played on $ G $ is said to be distance $ d $-restricted. For each target vertex $ v\in V(G) $, we use $ m(\delta, d, v) $ to denote the maximum number of pebbles that can be moved to $ v $ only from the vertices in the set $ N_d[v] $. If $ m(\delta, d, v)\ge t $ for each $ v\in V(G) $, then we say that $ \delta $ is $ (d, t) $-solvable. The optimal $ (d, t) $-pebbling number of $ G $, denoted by $ \pi^*_{(d, t)}(G) $, is the minimum number of pebbles needed so that there is a $ (d, t) $-solvable distribution of $ G $. In this article, we study distance $ 2 $-restricted pebbling in cycles and show that for any $ n $-cycle $ C_n $ with $ n\ge 6 $, $ \pi^*_{(2, t)}(C_n) = \pi^*_{(2, t-10)}(C_n)+4n $ for $ t \ge 13 $. It follows that if $ n\ge 6 $, then $ \pi^*_{(2, 10k+r)}(C_n) = \pi^*_{(2, r)}(C_n)+4kn $ for $ k\ge 1 $ and $ 3 \le r \le 12 $. Consequently, for $ n\ge 6 $, the problem of determining the exact value of $ \pi^*_{(2, t)}(C_n) $ for all $ t\ge 1 $ can be reduced to the problem of determining the exact value of $ \pi^*_{(2, r)}(C_n) $ for $ r\in[1, 12] $. We also consider $ C_n $ with $ 3\le n \le 5 $. When $ n = 3 $, we have $ \pi^*_{(2, t)}(C_3) = \pi^*_{(1, t)}(C_3) $, since the diameter of $ C_3 $ is one. The exact value of $ \pi^*_{(1, t)}(C_3) $ is known. When $ n = 4, 5 $, we determine the exact value of $ \pi^*_{(2, t)}(C_n) $ for $ t\ge 1 $.

    Citation: Chin-Lin Shiue, Tzu-Hsien Kwong. Distance 2-restricted optimal pebbling in cycles[J]. AIMS Mathematics, 2025, 10(2): 4355-4373. doi: 10.3934/math.2025201

    Related Papers:

  • Let $ G $ be a graph and let $ \delta $ be a distribution of pebbles on $ G $. A pebbling move on the graph $ G $ consists of removing two pebbles from one vertex and then placing one pebble at an adjacent vertex. Given a positive integer $ d $, if we can move pebbles to any target vertex $ v $ in $ G $ only from the vertices in the set $ N_d[v] = \{u\in V(G):d(u, v)\le d\} $ by pebbling moves, where $ d(u, v) $ is the distance between $ u $ and $ v $, then such a graph pebbling played on $ G $ is said to be distance $ d $-restricted. For each target vertex $ v\in V(G) $, we use $ m(\delta, d, v) $ to denote the maximum number of pebbles that can be moved to $ v $ only from the vertices in the set $ N_d[v] $. If $ m(\delta, d, v)\ge t $ for each $ v\in V(G) $, then we say that $ \delta $ is $ (d, t) $-solvable. The optimal $ (d, t) $-pebbling number of $ G $, denoted by $ \pi^*_{(d, t)}(G) $, is the minimum number of pebbles needed so that there is a $ (d, t) $-solvable distribution of $ G $. In this article, we study distance $ 2 $-restricted pebbling in cycles and show that for any $ n $-cycle $ C_n $ with $ n\ge 6 $, $ \pi^*_{(2, t)}(C_n) = \pi^*_{(2, t-10)}(C_n)+4n $ for $ t \ge 13 $. It follows that if $ n\ge 6 $, then $ \pi^*_{(2, 10k+r)}(C_n) = \pi^*_{(2, r)}(C_n)+4kn $ for $ k\ge 1 $ and $ 3 \le r \le 12 $. Consequently, for $ n\ge 6 $, the problem of determining the exact value of $ \pi^*_{(2, t)}(C_n) $ for all $ t\ge 1 $ can be reduced to the problem of determining the exact value of $ \pi^*_{(2, r)}(C_n) $ for $ r\in[1, 12] $. We also consider $ C_n $ with $ 3\le n \le 5 $. When $ n = 3 $, we have $ \pi^*_{(2, t)}(C_3) = \pi^*_{(1, t)}(C_3) $, since the diameter of $ C_3 $ is one. The exact value of $ \pi^*_{(1, t)}(C_3) $ is known. When $ n = 4, 5 $, we determine the exact value of $ \pi^*_{(2, t)}(C_n) $ for $ t\ge 1 $.



    加载中


    [1] H. Ahmad, M. K. Siddiqui, M. F. Hanif, B. Gegbe, Exploring the distance‐based topological indices for total graphs via numerical comparison, J. Math., 2024 (2024), 4423113. https://doi.org/10.1155/jom/4423113 doi: 10.1155/jom/4423113
    [2] D. P. Bunde, E. W. Chambers, D. Cranston, K. Milans, D. B. West, Pebbling and optimal pebbling in graphs, J. Graph Theory, 57 (2008), 215–238. https://doi.org/10.1002/jgt.20278 doi: 10.1002/jgt.20278
    [3] M. Chellali, T. W. Haynes, S. T. Hedetniemi, T. M. Lewis, Restricted optimal pebbling and domination in graphs, Discrete Appl. Math., 221 (2017), 46–53. https://doi.org/10.1016/j.dam.2016.12.029 doi: 10.1016/j.dam.2016.12.029
    [4] J. C. Chen, C. L. Shiue, An investigation of the game of defend the island, ICGA J., 40 (2018), 330–340. https://doi.org/10.3233/ICG-180052 doi: 10.3233/ICG-180052
    [5] A. Czygrinow, G. Hurlbert, G. Y. Katona, L. F. Papp, Optimal pebbling number of graphs with given minimum degree, Discrete Appl. Math., 260 (2019), 117–130. https://doi.org/10.1016/j.dam.2019.01.023 doi: 10.1016/j.dam.2019.01.023
    [6] Z. F. Dai, X. H. Chen, F. H. Wen, A modified Perry's conjugate gradient method-based derivative-free method for solving large-scale nonlinear monotone equations, Appl. Math. Comput., 270 (2015), 378–386. https://doi.org/10.1016/j.amc.2015.08.014 doi: 10.1016/j.amc.2015.08.014
    [7] E. Győri, G. Y. Katona, L. F. Papp, Optimal pebbling number of the square grid, Graphs Combin., 36 (2020), 803–829. https://doi.org/10.1007/s00373-020-02154-z doi: 10.1007/s00373-020-02154-z
    [8] D. Moews, Optimally pebbling hypercubes and powers, Discrete Math., 190 (1998), 271–276. https://doi.org/10.1016/S0012-365X(98)00154-X doi: 10.1016/S0012-365X(98)00154-X
    [9] L. Pachter, H. S. Snevily, B. Voxman, On pebbling graph, Congr. Numer., 107 (1995), 65–80.
    [10] L. F. Papp, Restricted optimal pebbling is NP-hard, Discrete Appl. Math., 357 (2024), 258–263. https://doi.org/10.1016/j.dam.2024.06.013 doi: 10.1016/j.dam.2024.06.013
    [11] J. Petr, J. Portier, S. Stolarczyk, A new lower bound on the optimal pebbling number of the grid, Discrete Math., 346 (2023), 113212. https://doi.org/10.1016/j.disc.2022.113212 doi: 10.1016/j.disc.2022.113212
    [12] C. L. Shiue, Optimally $t$-pebbling graphs, Util. Math., 98 (2015), 311–325.
    [13] C. L. Shiue, Distance restricted optimal pebbling in cycles, Discrete Appl. Math., 279 (2020), 125–133. https://doi.org/10.1016/j.dam.2019.10.017 doi: 10.1016/j.dam.2019.10.017
    [14] C. L. Shiue, H. H. Chiang, M. M. Wong, H. M. Srivastava, Optimal $t$-pebbling in cycles, Util. Math., 111 (2019), 49–66.
    [15] C. L. Shiue, T. H. Kwong, Distance and capacity restricted optimal 3-fold pebbling in cycles, SSRN, 2023, 1–21. https://doi.org/10.2139/ssrn.4694290
  • Reader Comments
  • © 2025 the Author(s), licensee AIMS Press. This is an open access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/4.0)
通讯作者: 陈斌, bchen63@163.com
  • 1. 

    沈阳化工大学材料科学与工程学院 沈阳 110142

  1. 本站搜索
  2. 百度学术搜索
  3. 万方数据库搜索
  4. CNKI搜索

Metrics

Article views(38) PDF downloads(6) Cited by(0)

Article outline

Other Articles By Authors

/

DownLoad:  Full-Size Img  PowerPoint
Return
Return

Catalog