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