Distance 2-restricted optimal pebbling in cycles
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 $...
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
AIMS Press
2025-02-01
|
| Series: | AIMS Mathematics |
| Subjects: | |
| Online Access: | https://www.aimspress.com/article/doi/10.3934/math.2025201 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1850151307587878912 |
|---|---|
| author | Chin-Lin Shiue Tzu-Hsien Kwong |
| author_facet | Chin-Lin Shiue Tzu-Hsien Kwong |
| author_sort | Chin-Lin Shiue |
| collection | DOAJ |
| description | 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 $. |
| format | Article |
| id | doaj-art-61c013bcf2da43f8ae2ac7bc3395bc31 |
| institution | OA Journals |
| issn | 2473-6988 |
| language | English |
| publishDate | 2025-02-01 |
| publisher | AIMS Press |
| record_format | Article |
| series | AIMS Mathematics |
| spelling | doaj-art-61c013bcf2da43f8ae2ac7bc3395bc312025-08-20T02:26:19ZengAIMS PressAIMS Mathematics2473-69882025-02-011024355437310.3934/math.2025201Distance 2-restricted optimal pebbling in cyclesChin-Lin Shiue0Tzu-Hsien Kwong1Department of Applied Mathematics, Chung Yuan Christian University, No. 200, Zhongbei Rd., Zhongli Dist., Taoyuan City 320314, TaiwanDepartment of Applied Mathematics, Chung Yuan Christian University, No. 200, Zhongbei Rd., Zhongli Dist., Taoyuan City 320314, TaiwanLet $ 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 $.https://www.aimspress.com/article/doi/10.3934/math.2025201graph pebblingoptimal pebblingcapacity-restricted pebblingdistance-restricted pebblingcycle |
| spellingShingle | Chin-Lin Shiue Tzu-Hsien Kwong Distance 2-restricted optimal pebbling in cycles AIMS Mathematics graph pebbling optimal pebbling capacity-restricted pebbling distance-restricted pebbling cycle |
| title | Distance 2-restricted optimal pebbling in cycles |
| title_full | Distance 2-restricted optimal pebbling in cycles |
| title_fullStr | Distance 2-restricted optimal pebbling in cycles |
| title_full_unstemmed | Distance 2-restricted optimal pebbling in cycles |
| title_short | Distance 2-restricted optimal pebbling in cycles |
| title_sort | distance 2 restricted optimal pebbling in cycles |
| topic | graph pebbling optimal pebbling capacity-restricted pebbling distance-restricted pebbling cycle |
| url | https://www.aimspress.com/article/doi/10.3934/math.2025201 |
| work_keys_str_mv | AT chinlinshiue distance2restrictedoptimalpebblingincycles AT tzuhsienkwong distance2restrictedoptimalpebblingincycles |