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!
|
| Summary: | 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 $. |
|---|---|
| ISSN: | 2473-6988 |