Let G be a graph and let δ 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 Nd[v]={u∈V(G):d(u,v)≤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∈V(G), we use m(δ,d,v) to denote the maximum number of pebbles that can be moved to v only from the vertices in the set Nd[v]. If m(δ,d,v)≥t for each v∈V(G), then we say that δ is (d,t)-solvable. The optimal (d,t)-pebbling number of G, denoted by π∗(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 Cn with n≥6, π∗(2,t)(Cn)=π∗(2,t−10)(Cn)+4n for t≥13. It follows that if n≥6, then π∗(2,10k+r)(Cn)=π∗(2,r)(Cn)+4kn for k≥1 and 3≤r≤12. Consequently, for n≥6, the problem of determining the exact value of π∗(2,t)(Cn) for all t≥1 can be reduced to the problem of determining the exact value of π∗(2,r)(Cn) for r∈[1,12]. We also consider Cn with 3≤n≤5. When n=3, we have π∗(2,t)(C3)=π∗(1,t)(C3), since the diameter of C3 is one. The exact value of π∗(1,t)(C3) is known. When n=4,5, we determine the exact value of π∗(2,t)(Cn) for t≥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
[1] | Shahbaz Ali, Muhammad Khalid Mahmmod, Raúl M. Falcón . A paradigmatic approach to investigate restricted hyper totient graphs. AIMS Mathematics, 2021, 6(4): 3761-3771. doi: 10.3934/math.2021223 |
[2] | Moussa Benoumhani . Restricted partitions and convex topologies. AIMS Mathematics, 2025, 10(4): 10187-10203. doi: 10.3934/math.2025464 |
[3] | Victoria May P. Mendoza, Renier Mendoza, Youngsuk Ko, Jongmin Lee, Eunok Jung . Managing bed capacity and timing of interventions: a COVID-19 model considering behavior and underreporting. AIMS Mathematics, 2023, 8(1): 2201-2225. doi: 10.3934/math.2023114 |
[4] | Zhenhua Su, Zikai Tang . Minimum distance–unbalancedness of the merged graph of $ C_3 $ and a tree. AIMS Mathematics, 2024, 9(7): 16863-16875. doi: 10.3934/math.2024818 |
[5] | Xingwei Ren . Statistical inference of the mixed linear model with incorrect stochastic linear restrictions. AIMS Mathematics, 2025, 10(5): 11349-11368. doi: 10.3934/math.2025516 |
[6] | Yinzhen Mei, Chengxiao Guo . The minimal degree Kirchhoff index of bicyclic graphs. AIMS Mathematics, 2024, 9(7): 19822-19842. doi: 10.3934/math.2024968 |
[7] | Nesrin Güler, Melek Eriş Büyükkaya . Statistical inference of a stochastically restricted linear mixed model. AIMS Mathematics, 2023, 8(10): 24401-24417. doi: 10.3934/math.20231244 |
[8] | JingJun Yu . Some congruences for $ \ell $-regular partitions with certain restrictions. AIMS Mathematics, 2024, 9(3): 6368-6378. doi: 10.3934/math.2024310 |
[9] | Nik Muhammad Farhan Hakim Nik Badrul Alam, Ku Muhammad Naim Ku Khalif, Nor Izzati Jaini . Synergic ranking of fuzzy Z-numbers based on vectorial distance and spread for application in decision-making. AIMS Mathematics, 2023, 8(5): 11057-11083. doi: 10.3934/math.2023560 |
[10] | Xiao Xu, Hong Liao, Xu Yang . An automatic density peaks clustering based on a density-distance clustering index. AIMS Mathematics, 2023, 8(12): 28926-28950. doi: 10.3934/math.20231482 |
Let G be a graph and let δ 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 Nd[v]={u∈V(G):d(u,v)≤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∈V(G), we use m(δ,d,v) to denote the maximum number of pebbles that can be moved to v only from the vertices in the set Nd[v]. If m(δ,d,v)≥t for each v∈V(G), then we say that δ is (d,t)-solvable. The optimal (d,t)-pebbling number of G, denoted by π∗(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 Cn with n≥6, π∗(2,t)(Cn)=π∗(2,t−10)(Cn)+4n for t≥13. It follows that if n≥6, then π∗(2,10k+r)(Cn)=π∗(2,r)(Cn)+4kn for k≥1 and 3≤r≤12. Consequently, for n≥6, the problem of determining the exact value of π∗(2,t)(Cn) for all t≥1 can be reduced to the problem of determining the exact value of π∗(2,r)(Cn) for r∈[1,12]. We also consider Cn with 3≤n≤5. When n=3, we have π∗(2,t)(C3)=π∗(1,t)(C3), since the diameter of C3 is one. The exact value of π∗(1,t)(C3) is known. When n=4,5, we determine the exact value of π∗(2,t)(Cn) for t≥1.
Let G be a graph. A distribution δ of G is a mapping from V(G) to the set of nonnegative integers. For each vertex v∈V(G), δ(v) denotes the number of pebbles distributed to v. A pebbling move consists of removing two pebbles from one vertex and then placing one pebble at an adjacent vertex. Let δ be a distribution of G, and let H be an induced subgraph of G. For convenience, we use |δ(H)| to denote the number of pebbles distributed onto the vertices of H. For each vertex v∈V(H), we use m(δ,H,v) to denote the maximum number of pebbles that can be moved to v from the vertices of H by using pebbling moves.
Given a positive integer d and a distribution δ of G, if we can move pebbles to any target vertex v in G only from the vertices in the set Nd[v]={u∈V(G):d(u,v)≤d} by pebbling moves, where d(u,v) is the distance between u and v, then such a graph pebbling is said to be distance d-restricted. We use m(δ,d,v) to denote the maximum number of pebbles that can be moved to v only from the vertices in the set Nd[v]. That is, m(δ,d,v)=m(δ,H,v), where H is a subgraph of G induced by Nd[v]. A distribution δ of a graph G is (d,t)-solvable if m(δ,d,v)≥t for each vertex v of G. The optimal (d,t)-pebbling number of G, π∗(d,t)(G), is the minimum number of pebbles needed so that there is a (d,t)-solvable distribution of G. A distribution δ of G is said to be optimal (d,t)-solvable if it is (d,t)-solvable and |δ(G)|=π∗(d,t)(G). When d is not less than the diameter of G, the subgraph induced by Nd[v] is G itself. In this situation, π∗(d,1)(G)=π∗(G), which is known as the optimal pebbling number of G, see [2,5,7,8,9,11] for references. Moreover, π∗(d,t)(G)=π∗t(G), which is the optimal t-pebbling number, see [12,14] for references.
In 2018, the distance-restricted graph pebbling was first proposed by Chen and Shiue [4], and they showed that π∗(2,2)(C3)=4 and π∗(2,2)(Cn)=n for all n≥4. In 2020, Shiue [13] studied distance 1-restricted pebbling in cycles and obtained the following result.
Theorem 2.1. [13] Let Cn be an n-cycle, n≥3. Then
π∗(1,t)(Cn)={nt2, if t is even and nt2 is even ;nt2+1, if t is even and nt2 is odd ;⌈2n3⌉, if t=1;⌈nt2+⌈n/(t+2)⌉2⌉, if t is odd and t≥3. |
In [13], Shiue also showed that if G is an r-regular graph of order n with girth at least 5 and t is a multiple of r2+r+4, then π∗(2,t)(G)=4ntr2+r+4. Since an n-cycle is 2-regular, we have the following.
Corollary 2.1. [13] Let Cn be an n-cycle. If n≥5, then π∗(2,10k)(Cn)=4nk for each positive integer k.
The conclusion of Corollary 2.1 gives the recurrence relation π∗(2,10k)(Cn)=π∗(2,10k−10)(Cn)+4n=π∗(2,10k−10)(Cn)+π∗(2,10)(Cn) for k≥2. Hence, we are interested in the following problem.
Problem 1. For n≥5 and t≥11, determine the values of t that satisfy the recurrence relation
π∗(2,t)(Cn)=π∗(2,t−10)(Cn)+4n. |
It is easy to see that for any graph G and any two positive integers t1 and t2, π∗(2,t1+t2)(G)≤π∗(2,t1)(G)+π∗(2,t2)(G).
Usually, the equality does not hold. For example, π∗(2,2)(C6)=6<8=π∗(2,1)(C6)+π∗(2,1)(C6).
In this article, we mainly study the distance 2-restricted pebbling in cycles. Note that the diameter of C3 is equal to one. This implies that π∗(2,t)(C3)=π∗t(C3)=π∗(1,t)(C3), see Theorem 2.1. As C3=K3, an alternative result about π∗t(C3) can be seen in [12]. Regarding the research on π∗t(Cn), readers can refer to [14]. Note that the authors in [14] have only given an upper and a lower bound for π∗t(Cn) when n≥4 and t≥3. In this article, we show that for t≥13 and n≥6, π∗(2,t)(Cn)=π∗(2,t−10)(Cn)+4n in Section 2 and completely determine the exact value of π∗t(Cn) for n=4,5, and t≥1 in Sections 4 and 5, respectively.
Throughout the rest of this article, let Cn=v0,v1,⋯,vn−1,v0 be an n-cycle, n≥3, and all subscripts referring to the vertices of the cycle Cn will be interpreted modulo n. We write "a mod b" to denote the remainder when a is divided by b. For convenience, we use "[ℓ1,ℓ2]" to denote the set of all integers between ℓ1 and ℓ2 and, if δ is a distribution of pebbles on Cn, we use ⟨x0,x1,⋯,xn−1⟩ to denote δ, where xi=δ(vi). Thus, |δ(Cn)|=∑n−1i=0xi. Note that the diameter of Cn is not more than two for 3≤n≤5. It follows that π∗(2,t)(Cn)=π∗t(Cn) for 3≤n≤5. So we only consider the case when n≥6 in this section. For n≥6, and for i∈[0,n−1],
m(δ,2,vi)=⌊12(⌊xi−22⌋+xi−1)⌋+xi+⌊12(xi+1+⌊xi+22⌋)⌋. | (3.1) |
The following proposition is an important key for solving Problem 1.
Proposition 3.1. For t≥11 and n≥6, if there exists an optimal (2,t)-solvable distribution δ=⟨x0,x1,⋯,xn−1⟩ of Cn such that xi≥4 for i∈[0,n−1], then π∗(2,t)(Cn)=π∗(2,t−10)(Cn)+4n.
Proof. Assume that t≥11 and n≥6. By Corollary 2.1, we have π∗(2,10)(Cn)=4n. It follows that
π∗(2,t)(Cn)≤π∗(2,t−10)(Cn)+π∗(2,10)(Cn)=π∗(2,t−10)(Cn)+4n. |
Thus,
π∗(2,t−10)(Cn)≥π∗(2,t)(Cn)−4n. |
Assume that δ=⟨x0,x1,⋯,xn−1⟩ is an optimal (2,t)-solvable distribution of Cn with xi≥4 for all i∈[0,n−1]. Then let δ′=⟨y0,y1,⋯,yn−1⟩ be a distribution of Cn such that yi=xi−4 for i∈[0,n−1]. Clearly,
|δ′(Cn)|=|δ(Cn)|−4n=π∗(2,t)(Cn)−4n. |
To complete the proof, it is left to show that δ′ is (2,t−10)-solvable. For i∈[0,n−1], by (3.1), we have
m(δ′,2,vi)=⌊⌊yi−22⌋+yi−12⌋+yi+⌊⌊yi+22⌋+yi+12⌋=⌊⌊xi−2−42⌋+xi−1−42⌋+xi−4+⌊⌊xi+2−42⌋+xi+1−42⌋=⌊⌊xi−22⌋+xi−12⌋+xi+⌊⌊xi+22⌋+xi+12⌋−10=m(δ,2,vi)−10≥t−10. |
Thus, δ′ is (2,t−10)-solvable, and we have the proof.
Proposition 3.1 gives a sufficient condition for satisfying the recurrence relation in Problem 1. Now, we will find the values of t that satisfy the assumption of the statement in Proposition 3.1.
Let δ=⟨x0,x1,⋯,xn−1⟩ be a (2,t)-solvable distribution of Cn with n≥6. Consider any subpath
vj−5,vj−4,vj−3,vj−2,vj−1,vj,vj+1,vj+2,vj+3,vj+4,vj+5 |
in Cn, for some j∈[0,n−1]. When 6≤n≤10, the subpath is the cycle Cn. We let n=10−k, where 0≤k≤4. Then the vertex vj+5−i=vj−5+k−i for i∈[0,k]. For example, if n=8, then vj+5=vj−3, vj+4=vj−4, and vj+3=vj−5. By (3.1), we have
m(δ,2,vj)=⌊(⌊xj−2/2⌋+xj−1)/2⌋+xj+⌊(xj+1+⌊xj+2/2⌋)/2⌋≥t. |
It follows that
(⌊xj−2/2⌋+xj−1)+(xj+1+⌊xj+2/2⌋)≥2(t−xj). |
Without loss of generality, we can assume that
⌊xj−2/2⌋+xj−1=t+r−xj, | (3.2) |
where r is a nonnegative integer. Then we have
xj+1+⌊xj+2/2⌋≥t−r−xj. | (3.3) |
It follows that
xj−2≥2(t+r−xj−xj−1) | (3.4) |
and
xj+2≥2(t−r−xj−xj+1). | (3.5) |
By (3.1)–(3.5), we have the following four facts:
Fact 1.
m(δ,2,vj−1)=⌊(⌊xj−3/2⌋+xj−2)/2⌋+xj−1+⌊(xj+⌊xj+1/2⌋)/2⌋≥⌊xj−3/4⌋+⌊xj−2/2⌋+xj−1+⌊(xj+⌊xj+1/2⌋)/2⌋=⌊xj−3/4⌋+(t+r−xj)+⌊(xj+⌊xj+1/2⌋)/2⌋. |
Fact 2.
m(δ,2,vj+1)=⌊(⌊xj−1/2⌋+xj)/2⌋+xj+1+⌊(xj+2+⌊xj+3/2⌋)/2⌋≥⌊(⌊xj−1/2⌋+xj)/2⌋+xj+1+⌊xj+2/2⌋+⌊xj+3/4⌋≥⌊(⌊xj−1/2⌋+xj)/2⌋+(t−r−xj)+⌊xj+3/4⌋. |
Fact 3.
m(δ,2,vj−2)=⌊(⌊xj−4/2⌋+xj−3)/2⌋+xj−2+⌊(xj−1+⌊xj/2⌋)/2⌋≥⌊(⌊xj−4/2⌋+xj−3)/2⌋+2(t+r−xj−xj−1)+⌊(xj−1+⌊xj/2⌋)/2⌋. |
Fact 4.
m(δ,2,vj+2)=⌊(⌊xj/2⌋+xj+1)/2⌋+xj+2+⌊(xj+3+⌊xj+4/2⌋)/2⌋≥⌊(⌊xj/2⌋+xj+1)/2⌋+2(t−r−xj−xj+1)+⌊(xj+3+⌊xj+4/2⌋)/2⌋. |
Fact 5. If xj−2≥8 and δ′=⟨y0,y1,⋯,yn−1⟩ is a distribution of Cn such that yj=xj+2, yj−1=xj−1+2, yj−2=xj−2−8, yj−3=xj−3+4, and yi=xi for i∈[0,n−1]∖[j−3,j], then |δ′(Cn)|=|δ(Cn)|, m(δ′,2,vj−2)≥m(δ,2,vj−2)−5 and m(δ′,2,vi)≥m(δ,2,vi) for i∈[0,n−1]∖{j−2}.
Proof. Clearly, |δ′(Cn)|=|δ(Cn)|. If n≥11, then the vertices
vj−5,vj−4,vj−3,vj−2,vj−1,vj,vj+1,vj+2,vj+3,vj+4,vj+5 |
are all distinct. Otherwise, 6≤n≤10. Let n=10−k, where 0≤k≤4. Then, the vertex vj+5−i=vj−5+k−i for i∈[0,4]. By (3.1), it is easy to see that m(δ′,2,vi)≥m(δ,2,vi) for i∈[0,n−1]∖{j−2,j−1}. So, we only need to check m(δ′,2,vj−2) and m(δ′,2,vj−1). Since n≥6, vi∉{vj−3,vj−2,vj−1,vj} for i∈{j−4,j+1}. By (3.1), we have
m(δ′,2,vj−2)=⌊(⌊yj−4/2⌋+yj−3)/2⌋+yj−2+⌊(yj−1+⌊yj/2⌋)/2⌋=⌊(⌊xj−4/2⌋+xj−3+4)/2⌋+xj−2−8+⌊(xj−1+2+⌊(xj+2)/2⌋)/2⌋≥⌊(⌊xj−4/2⌋+xj−3)/2⌋+xj−2+⌊(xj−1+⌊xj/2⌋)/2⌋+2−8+1=m(δ,2,vj−2)−5, |
and
m(δ′,2,vj−1)=⌊(⌊yj−3/2⌋+yj−2)/2⌋+yj−1+⌊(yj+⌊yj+1/2⌋)/2⌋=⌊(⌊(xj−3+4)/2⌋+xj−2−8)/2⌋+xj−1+2+⌊(xj+2+⌊xj+1/2⌋)/2⌋=⌊(⌊xj−3/2⌋+xj−2)/2⌋+xj−1+⌊(xj+⌊xj+1/2⌋)/2⌋−3+2+1=m(δ,2,vj−1). |
Fact 6. If xj−2≥4 and δ′=⟨y0,y1,⋯,yn−1⟩ is a distribution of Cn such that yj=xj+1, yj−1=xj−1+1, yj−2=xj−2−4, yj−3=xj−3+2 and yi=xi for i∈[0,n−1]∖[j−3,j], then |δ′(Cn)|=|δ(Cn)|, m(δ′,2,vj−2)≥m(δ,2,vj−2)−3, m(δ′,2,vj−1)≥m(δ,2,vj−1)−1 and m(δ′,2,vi)≥m(δ,2,vi) for i∈[0,n−1]∖{j−1,j−2}.
Proof. Clearly, |δ′(Cn)|=|δ(Cn)|. If n≥11, then the vertices
vj−5,vj−4,vj−3,vj−2,vj−1,vj,vj+1,vj+2,vj+3,vj+4,vj+5 |
are all distinct. Otherwise, 6≤n≤10. Let n=10−k, where 0≤k≤4. Then the vertex vj+5−i=vj−5+k−i for i∈[0,4]. By (3.1), it is easy to see that m(δ′,2,vi)≥m(δ,2,vi) for i∈[0,n−1]∖{j−2,j−1}. Now, we only need to check m(δ′,2,vj−2) and m(δ′,2,vj−1). Since n≥6, vi∉{vj−3,vj−2,vj−1,vj} for i∈{j−4,j+1}. By (3.1), we have
m(δ′,2,vj−2)=⌊(⌊yj−4/2⌋+yj−3)/2⌋+yj−2+⌊(yj−1+⌊yj/2⌋)/2⌋=⌊(⌊xj−4/2⌋+xj−3+2)/2⌋+xj−2−4+⌊(xj−1+1+⌊(xj+1)/2⌋)/2⌋≥⌊(⌊xj−4/2⌋+xj−3)/2⌋+xj−2+⌊(xj−1+⌊xj⌋)/2⌋+1−4=m(δ,2,vj−2)−3, |
and
m(δ′,2,vj−1)=⌊(⌊yj−3/2⌋+yj−2)/2⌋+yj−1+⌊(yj+⌊yj+1/2⌋)/2⌋=⌊(⌊(xj−3+2)/2⌋+xj−2−4)/2⌋+xj−1+1+⌊(xj+1+⌊xj+1/2⌋)/2⌋≥⌊(⌊xj−3/2⌋+xj−2)/2⌋+xj−1+⌊(xj+⌊xj+1/2⌋)/2⌋−2+1=m(δ,2,vj−1)−1. |
By using Eq (3.1) to check, we can obtain Facts 7 and 8.
Fact 7. If xj−1≥4 and δ′=⟨y0,y1,⋯,yn−1⟩ is a distribution of Cn such that yj=xj+2, yj−1=xj−1−4, yj−2=xj−2+2, and yi=xi for i∈[0,n−1]∖[j−2,j], then |δ′(Cn)|=|δ(Cn)|, m(δ′,2,vj−1)=m(δ,2,vj−1)−2 and m(δ′,2,vi)≥m(δ,2,vi) for i∈[0,n−1]∖{j−1}.
Fact 8. If xj−1≥2 and δ′=⟨y0,y1,⋯,yn−1⟩ is a distribution of Cn such that yj=xj+1, yj−1=xj−1−2, yj−2=xj−2+1, and yi=xi for i∈[0,n−1]∖[j−2,j], then |δ′(Cn)|=|δ(Cn)|, m(δ′,2,vj−1)≥m(δ,2,vj−1)−2 and m(δ′,2,vi)≥m(δ,2,vi) for i∈[0,n−1]∖{j−1}.
Fact 9. If xj−1 and xj+1 are both odd, and δ′=⟨y0,y1,⋯,yn−1⟩ is a distribution of Cn such that yj=xj+2, yj−1=xj−1−1, yj+1=xj+1−1, and yi=xi for i∈[0,n−1]∖[j−1,j,j+1], then |δ′(Cn)|=|δ(Cn)| and m(δ′,2,vi)≥m(δ,2,vi) for i∈[0,n−1].
Proof. Clearly, |δ′(Cn)|=|δ(Cn)|. If n≥11, then the vertices
vj−5,vj−4,vj−3,vj−2,vj−1,vj,vj+1,vj+2,vj+3,vj+4,vj+5 |
are all distinct. Otherwise, 6≤n≤10. Let n=10−k, where 0≤k≤4. Then, the vertex vj+5−i=vj−5+k−i for i∈[0,4]. By (3.1), it is easy to see that m(δ′,2,vi)=m(δ,2,vi) for i∈[0,n−1]∖{j−3,j−2,j−1,j,j+1,j+2,j+3}. So, we only need to check m(δ′,2,vi) for i∈{j−3,j−2,j−1,j,j+1,j+2,j+3}. Note that xj−1 and xj+1 are both odd. It follows that ⌊(xj−1−1)/2⌋=⌊xj−1/2⌋ and ⌊(xj+1−1)/2⌋=⌊xj+1/2⌋. Since n≥6, vi∉{vj−1,vj,vj+1} for i∈{j−4,j−3,j−2,j+2}. By using (3.1) to check, we can verify that m(δ′,2,vi)≥m(δ,2,vi) for i∈{j,j−1,j−2}. For the value of m(δ′,2,vj−3), if n≥7, then vi∉{vj−1,vj,vj+1} for i∈{j−5,j−4,j−3,j−2}, and
m(δ′,2,vj−3)=⌊(⌊yj−5/2⌋+yj−4)/2⌋+yj−3+⌊(yj−2+⌊yj−1/2⌋)/2⌋=⌊(⌊xj−5/2⌋+xj−4)/2⌋+xj−3+⌊(xj−2+⌊(xj−1−1)/2⌋)/2⌋=⌊(⌊xj−5/2⌋+xj−4)/2⌋+xj−3+⌊(xj−2+⌊xj−1/2⌋)/2⌋=m(δ,2,vj−3). |
Otherwise, n=6, and hence vj−5=vj+1; then we have
m(δ′,2,vj−3)=⌊(⌊yj−5/2⌋+yj−4)/2⌋+yj−3+⌊(yj−2+⌊yj−1/2⌋)/2⌋=⌊(⌊(xj−5−1)/2⌋+xj−4)/2⌋+xj−3+⌊(xj−2+⌊(xj−1−1)/2⌋)/2⌋=⌊(⌊xj−5/2⌋+xj−4)/2⌋+xj−3+⌊(xj−2+⌊xj−1/2⌋)/2⌋=m(δ,2,vj−3). |
By a similar argument as above, we also have m(δ′,2,vi)≥m(δ,2,vi) for i∈{j+1,j+2,j+3}.
Fact 10. If xj−1 and xj are both odd, and δ′=⟨y0,y1,⋯,yn−1⟩ is a distribution of Cn such that yj=xj+1, yj−1=xj−1−1, and yi=xi for i∈[0,n−1]∖[j−1,j], then |δ′(Cn)|=|δ(Cn)|, m(δ′,2,vj−1)≥m(δ,2,vj−1)−1 and m(δ′,2,vi)≥m(δ,2,vi) for i∈[0,n−1]∖{j−1}.
Proof. Clearly, |δ′(Cn)|=|δ(Cn)|. If n≥11, then, the vertices
vj−5,vj−4,vj−3,vj−2,vj−1,vj,vj+1,vj+2,vj+3,vj+4,vj+5 |
are all distinct. Otherwise, 6≤n≤10. Let n=10−k, where 0≤k≤4. Then the vertex vj+5−i=vj−5+k−i for i∈[0,4]. By (3.1), it is easy to see that m(δ′,2,vi)=m(δ,2,vi) for i∈[0,n−1]∖{j−3,j−2,j−1,j,j+1,j+2}. So, we only need to check m(δ′,2,vi) for i∈{j−3,j−2,j−1,j,j+1,j+2}. Note that xj−1 and xj are both odd. It follows that ⌊(xj−1−1)/2⌋=⌊xj−1/2⌋ and ⌊(xj+1)/2⌋=⌊xj/2⌋+1. Since n≥6, vi∉{vj−1,vj} for i∈{j−4,j−3,j−2,j+1,j+2}. By using (3.1) to check, we can verify that m(δ′,2,vj−1)≥m(δ,2,vj−1)−1 and m(δ′,2,vj)≥m(δ,2,vj). For the value of m(δ′,2,vj−2), vi∉{vj−1,vj} for i∈{j−4,j−3,j−2}, and
m(δ′,2,vj−2)=⌊(⌊yj−4/2⌋+yj−3)/2⌋+yj−2+⌊(yj−1+⌊yj/2⌋)/2⌋=⌊(⌊xj−4/2⌋+xj−4)/2⌋+xj−2+⌊(xj−1−1+⌊(xj+1)/2⌋)/2⌋=⌊(⌊xj−4/2⌋+xj−3)/2⌋+xj−2+⌊(xj−1+⌊xj/2⌋)/2⌋=m(δ,2,vj−2). |
For the value of m(δ′,2,vj−3), vi∉{vj−1,vj} for i∈{j−5,j−4,j−3,j−2}, and
m(δ′,2,vj−3)=⌊(⌊yj−5/2⌋+yj−4)/2⌋+yj−3+⌊(yj−2+⌊yj−1/2⌋)/2⌋=⌊(⌊xj−5/2⌋+xj−4)/2⌋+xj−3+⌊(xj−2+⌊(xj−1−1)/2⌋)/2⌋=⌊(⌊xj−5/2⌋+xj−4)/2⌋+xj−3+⌊(xj−2+⌊xj−1/2⌋)/2⌋=m(δ,2,vj−3). |
By a similar argument as above, we also have m(δ′,2,vi)≥m(δ,2,vi) for i∈{j+1,j+2}.
Lemma 3.1. For t≥13 and n≥6, there exists an optimal (2,t)-solvable distribution δ of Cn such that δ(v)≥1 for each vertex v of Cn.
Proof. Let δ=⟨x0,x1,⋯,xn−1⟩ be an optimal (2,t)-solvable distribution of Cn. Suppose that there exists a vertex vj, j∈[0,n−1], with δ(vj)=xj=0. It suffices to show that there exists a (2,t)-solvable distribution δ′ of Cn such that δ′(vj)≥1 and δ′(vk)≥1 or δ′(vk)≥xk for k∈[0,n−1]∖{j} and |δ′(Cn)|≤|δ(Cn)|. By (3.1), we have
(⌊xj−2/2⌋+xj−1)+(xj+1+⌊xj+2/2⌋)≥2(t−xj). |
Without loss of generality, we can assume that ⌊xj−2/2⌋+xj−1=t−xj+r, where r is a nonnegative integer. This implies that (3.2)–(3.5) are valid. Now, we will modify the distribution of pebbles on the vertices in {vi|i∈[j−3,j+3]} if necessary. Let δ′=⟨y0,y1,⋯,yn−1⟩ be a distribution of Cn such that yi=xi for i∈[0,n−1]∖[j−3,j+3]. For i∈[j−3,j+3], yi will be defined according to the following cases. Initially, we let yi=xi for i∈[j−3,j+3].
By (3.4) and Fact 3, we have
xj−2≥2(t+r−xj−xj−1)=2(13+r−xj−1) |
and
m(δ,2,vj−2)≥⌊(⌊xj−4/2⌋+xj−3)/2⌋+2(t+r−xj−xj−1)+⌊(xj−1+⌊xj/2⌋)/2⌋≥t+13+2r−(2xj−1−⌊xj−1/2⌋). |
Case 1. r=0.
If xj−1≤5, then xj−2≥2(13+0−5)=16 and m(δ,2,vj−2)≥t+13+0−(2⋅5−⌊5/2⌋)=t+5. Let yj=xj+2=2, yj−1=xj−1+2, yj−2=xj−2−8≥8, and yj−3=xj−3+4. By Fact 5, |δ′(Cn)|=|δ(Cn)| and δ′ is (2,t)-solvable.
Similarly, if xj+1≤5, then, by (3.5) and Fact 4, we have xj+2≥16 and m(δ,2,vj+2)≥t+5. Let yj=xj+2=2, yj+1=xj+1+2, yj+2=xj+2−8≥8, yj+3=xj+3+4. Then, |δ′(Cn)|=|δ(Cn)| and δ′ is (2,t)-solvable.
Now, we can assume that xj−1≥6 and xj+1≥6. Let yj=xj+1=1, yj−1=xj−1−2≥4, and yj−2=xj−2+1. By Fact 8, we only need to check m(δ′,2,vj−1). By (3.1) and (3.2), we have
m(δ′,2,vj−1)=⌊(⌊yj−3/2⌋+yj−2)/2⌋+yj−1+⌊(yj+⌊yj+1/2⌋)/2⌋≥⌊xj−3/4⌋+⌊(xj−2+1)/2⌋+xj−1−2+⌊(xj+1+⌊xj+1/2⌋)/2⌋≥(t−xj+r)−2+⌊(1+⌊6/2⌋)/2⌋=t. |
Case 2. r=1.
If xj−1≤6, then xj−2≥2(13+1−6)=16 and m(δ,2,vj−2)≥t+13+2−(2⋅6−⌊6/2⌋)=t+6. Let yj=xj+2=2, yj−1=xj−1+2, yj−2=xj−2−8≥8, and yj−3=xj−3+4. Then, by Fact 5, we have |δ′(Cn)|=|δ(Cn)| and δ′ is (2,t)-solvable. Otherwise, xj−1≥7. If xj+1≥4, then, by Fact 1, we have m(δ,2,vj−1)≥(t+r−xj)+⌊(xj+⌊xj+1/2⌋)/2⌋≥t+2. Let yj=xj+2=2, yj−1=xj−1−4≥3, and yj−2=xj−2+2. Then, by Fact 7, we have |δ′(Cn)|=|δ(Cn)| and δ′ is (2,t)-solvable. If xj+1≤3, then, by (3.5) and Fact 4, xj+2≥2(t−r−xj−xj+1)≥2(13−1−0−3)=18 and m(δ,2,vj+2)≥⌊xj+1/2⌋+2(t−r−xj−xj+1)≥⌊3/2⌋+t+13+2(−1−0−3)=t+6. Let yj=xj+2=2, yj+1=xj+1+2, yj+2=xj+2−8≥10, and yj+3=xj+3+4. Then, by Fact 5, |δ′(Cn)|=|δ(Cn)| and δ′ is (2,t)-solvable.
Case 3. r≥2.
If xj−1≤8, then xj−2≥2(13+2−8)=14 and m(δ,2,vj−2)≥t+13+4−(2⋅8−⌊8/2⌋)+4=t+5. Let yj=xj+2=2, yj−1=xj−1+2, yj−2=xj−2−8≥6, and yj−3=xj−3+4. Then, by Fact 5, |δ′(Cn)|=|δ(Cn)| and δ′ is (2,t)-solvable. Otherwise, xj−1≥9. By Fact 1, m(δ,2,vj−1)≥t+r−xj≥t+2. Let yj=xj+2=2, yj−1=xj−1−4≥5, yj−2=xj−2+2. Then, by Fact 7, we have |δ′(Cn)|=|δ(Cn)| and δ′ is (2,t)-solvable.
Lemma 3.2. For t≥13 and n≥6, there exists an optimal (2,t)-solvable distribution δ of Cn such that δ(v)≥2 for each vertex v of Cn.
Proof. By Lemma 3.1, we assume that δ=⟨x0,x1,⋯,xn−1⟩ is an optimal (2,t)-solvable distribution of Cn such that δ(v)≥1 for each vertex v of Cn. Suppose that xj=1 for some j∈[0,n−1]. Then, let δ′=⟨y0,y1,⋯,yn−1⟩ be defined as the description in Lemma 3.1. It suffices to show that δ′(vj)≥2 and δ′(vk)≥2 or δ′(vk)≥xk for k∈[0,n−1]∖{j} and |δ′(Cn)|≤|δ(Cn)|.
By (3.4) and Fact 3, we have xj−2≥2(12+r−xj−1) and m(δ,2,vj−2)≥t+11+2r−(2xj−1−⌊xj−1/2⌋).
Case 1. r=0.
If xj−1≤4, then xj−2≥2(12+0−4)=16 and m(δ,2,vj−2)≥t+11+0−(2⋅4−⌊4/2⌋)=t+5. Let yj=xj+2=3, yj−1=xj−1+2, yj−2=xj−2−8≥8, and yj−3=xj−3+4. By Fact 5, |δ′(Cn)|=|δ(Cn)| and δ′ is (2,t)-solvable.
Similarly, if xj+1≤4, then xj+2≥16 and m(δ,2,vj+2)≥t+5. Let yj=xj+2=3, yj+1=xj+1+2, yj+2=xj+2−8≥8, yj+3=xj+3+4. Then, |δ′(Cn)|=|δ(Cn)| and δ′ is (2,t)-solvable.
Now, we assume that xj−1≥5 and xj+1≥5. Note that xj=1 is odd. If xj−1 is odd, let yj=xj+1=2, and yj−1=xj−1−1≥4. By Fact 10, we only need to check m(δ′,2,vj−1). By using (3.1) and (3.2), we can verify m(δ′,2,vj−1)≥t.
Similarly, if xj+1 is odd, let yj=xj+1=2, and yj+1=xj+1−1≥4. Then, |δ′(Cn)|=|δ(Cn)| and δ′ is (2,t)-solvable.
Now, we can assume that xj−1≥6 and xj+1≥6, and xj−1 and xj+1 are both even. For the case xj−1≥6 and xj+1≥8, let yj=xj+1=2, yj−1=xj−1−2≥4, and yj−2=xj−2+1. Then, by Fact 8, we only need to check m(δ′,2,vj−1). Also, by using (3.1) and (3.2), it is easy to check that m(δ′,2,vj−1)≥t.
Similarly, for the case xj−1≥8 and xj+1≥6, let yj=xj+1=2, yj+1=xj+1−2≥4, and yj+2=xj+2+1. Then, |δ′(Cn)|=|δ(Cn)| and δ′ is (2,t)-solvable.
For the case xj−1=xj+1=6, let yj=xj+1=2, yj−1=xj−1−1=5, yj−2=xj−2−1≥2(t+r−xj−xj−1)−1≥2(13+0−1−6)−1≥11, and yj−3=xj−3+1. Clearly, |δ′(Cn)|=|δ(Cn)|. If n≥11, then the vertices
vj−5,vj−4,vj−3,vj−2,vj−1,vj,vj+1,vj+2,vj+3,vj+4,vj+5 |
are all distinct. Otherwise, 6≤n≤10. Let n=10−k, where 0≤k≤4. Then the vertex vj+5−i=vj−5+k−i for i∈[0,4]. By (3.1), it is easy to see that m(δ′,2,vi)=m(δ,2,vi) for i∈[0,n−1]∖{j−5,j−4,j−3,j−2,j−1,j,j+1,j+2}. If n≥9, vi∉{vj−3,vj−2,vj−1,vj} for i∈{j−7,j−6,j−5,j−4,j+1,j+2,j+3,j+4,j+5}. Note that when n=9, vj+5=vj−4 and vj+4=vj−5, or when n=10, vj+5=vj−5. So, for n≥9, it is easy to see that m(δ′,2,vi)≥m(δ,2,vi) for i∈{j−5,j−4,j+1,j+2}. By (3.1)–(3.3), we also can verify that m(δ′,2,vi)≥t for i∈{j,j−1,j−2,j−3}. For the case that 6≤n≤8, without loss of generality, let j=0. Then, by (3.1)–(3.3), it is easy to verify that δ′ is (2,t)-solvable by checking m(δ′,2,vi) for each i∈[0,n−1].
Case 2. r=1.
If xj−1≤5, then xj−2≥2(12+1−5)=16 and m(δ,2,vj−2)≥t+11+2−(2⋅5−⌊5/2⌋)=t+5. Let yj=xj+2=3, yj−1=xj−1+2, yj−2=xj−2−8≥8, and yj−3=xj−3+4. By Fact 5, |δ′(Cn)|=|δ(Cn)| and δ′ is (2,t)-solvable. If xj+1≤2, then, by (3.5) and Fact 4, xj+2≥2(t−r−xj−xj+1)≥2(13−1−1−2)=18 and m(δ,2,vj+2)≥⌊xj+1/2⌋+2(t−r−xj−xj+1)≥⌊2/2⌋+t+13−2(1+1+2)=t+6. Let yj=xj+2=3, yj+1=xj+1+2, yj+2=xj+2−8≥10, and yj+3=xj+3+4. Then, |δ′(Cn)|=|δ(Cn)| and δ′ is (2,t)-solvable. Now, we can assume that xj−1≥6 and xj+1≥3. If xj+1≥4, let yj=xj+1=2, yj−1=xj−1−2≥4, and yj−2=xj−2+1. By Fact 8, we only need to check m(δ′,2,vj−1). By using (3.1) and (3.2), we can verify that m(δ′,2,vj−1)≥t. For the case xj−1≥6 and xj+1=3, let yj=xj+1=2, yj−1=xj−1−2≥4, yj−2=xj−2+1, yj+1=xj+1+1, yj+2=xj+2−2≥2(13−1−1−3)−2≥14 and yj+3=xj+3+1. By Fact 8, we only need to check m(δ′,2,vj−1) and m(δ′,2,vj+2). By using (3.1), (3.2) and (3.5), we can verify that m(δ′,2,vj−1)≥t and m(δ′,2,vj+2)≥t+4.
Case 3. r≥2.
If xj−1≤6, then xj−2≥2(12+2−6)=16 and m(δ,2,vj−2)≥t+11+4−(2⋅6−⌊6/2⌋)=t+6. Let yj=xj+2=3, yj−1=xj−1+2, yj−2=xj−2−8≥8, and yj−3=xj−3+4. Then, by Fact 5, we have |δ′(Cn)|=|δ(Cn)| and δ′ is (2,t)-solvable. Otherwise, xj−1≥7. Let yj=xj+1=2, yj−1=xj−1−2≥5, and yj−2=xj−2+1. Then, by Fact 8, we only need to check m(δ′,2,vj−1). By using (3.1) and (3.2), we can verify that m(δ′,2,vj−1)≥t.
Lemma 3.3. For t≥13 and n≥6, there exists an optimal (2,t)-solvable distribution δ of Cn such that δ(v)≥3 for each vertex v of Cn.
Proof. By Lemma 3.2, we assume that δ=⟨x0,x1,⋯,xn−1⟩ is an optimal (2,t)-solvable distribution of Cn such that δ(v)≥2 for each vertex v of Cn. Suppose that xj=2 for some j∈[0,n−1]. Then, let δ′=⟨y0,y1,⋯,yn−1⟩ be defined as the description in Lemma 3.1. It suffices to show that δ′(vj)≥3 and δ′(vk)≥3 or δ′(vk)≥xk for k∈[0,n−1]∖{j} and |δ′(Cn)|≤|δ(Cn)|.
By (3.4) and Fact 3, we have xj−2≥2(11+r−xj−1) and m(δ,2,vj−2)≥t+10+2r−(2xj−1−⌊(xj−1+1)/2⌋).
Case 1. r=0.
If xj−1≤3, then xj−2≥2(11+0−3)=16 and m(δ,2,vj−2)≥t+10+0−(2⋅3−⌊(3+1)/2⌋)=t+6. Let yj=xj+2=4, yj−1=xj−1+2, yj−2=xj−2−8≥8, and yj−3=xj−3+4. Similarly, if xj+1≤3, then xj+2≥16 and m(δ,2,vj+2)≥t+6. Let yj=xj+2=4, yj+1=xj+1+2, yj+2=xj+2−8≥8, and yj+3=xj+3+4. By Fact 5, we have |δ′(Cn)|=|δ(Cn)| and δ′ is (2,t)-solvable.
Now, we can assume that xj−1≥4 and xj+1≥4. For the case xj−1=4 and xj+1≥4, we have xj−2≥2(11+0−4)=14 and m(δ,2,vj−2)≥t+10+0−(2⋅4−⌊(4+1)/2⌋)=t+4. Let yj=xj+1=3, yj−1=xj−1+1, yj−2=xj−2−4≥10, and yj−3=xj−3+2. Then, by Fact 6, we only need to check m(δ′,2,vj−1). By (3.1) and (3.2), we can verify m(δ′,2,vj−1)≥t.
Similarly, for the case xj−1≥4 and xj+1=4, let yj=xj+1=3, yj+1=xj+1+1, yj+2=xj+2−4≥10, and yj+3=xj+3+2. Then, |δ′(Cn)|=|δ(Cn)| and δ′ is (2,t)-solvable. Now, we can assume that xj−1≥5 and xj+1≥5. For the case xj−1=xj+1=5, let yj=xj+2=4, yj−1=xj−1−1=4, and yj+1=xj+1−1=4. Note that xj−1 and xj+1 are both odd. By Fact 9, |δ′(Cn)|=|δ(Cn)| and δ′ is (2,t)-solvable. For the case xj−1≥5 and xj+1≥6, let yj=xj+1=3, yj−1=xj−1−2≥3, and yj−2=xj−2+1. Then, by Fact 8, we only need to check m(δ′,2,vj−1). By using (3.1) and (3.2), we can verify m(δ′,2,vj−1)≥t.
Similarly, for the case xj−1≥6 and xj+1≥5, let yj=xj+1=3, yj+1=xj+1−2≥3, and yj+2=xj+2+1. Then, |δ′(Cn)|=|δ(Cn)| and δ′ is (2,t)-solvable.
Case 2. r=1.
If xj−1≤4, then xj−2≥2(11+1−4)=16 and m(δ,2,vj−2)≥t+10+2−(2⋅4−⌊4/2⌋)=t+6. Let yj=xj+2=4, yj−1=xj−1+2, yj−2=xj−2−8≥8, and yj−3=xj−3+4. Then, by Fact 5, |δ′(Cn)|=|δ(Cn)| and δ′ is (2,t)-solvable. Otherwise, xj−1≥5, let yj=xj+1=3, yj−1=xj−1−2≥3, and yj−2=xj−2+1. By Fact 8, we only need to check m(δ′,2,vj−1). By (3.1) and (3.2), we can verify m(δ′,2,vj−1)≥t.
Case 3. r≥2.
If xj−1≤6, then xj−2≥2(11+2−6)=14 and m(δ,2,vj−2)≥t+10+4−(2⋅6−⌊6/2⌋)=t+5. Let yj=xj+2=4, yj−1=xj−1+2, yj−2=xj−2−8≥6, and yj−3=xj−3+4. Then, by Fact 5, |δ′(Cn)|=|δ(Cn)| and δ′ is (2,t)-solvable. Otherwise, xj−1≥7, let yj=xj+1=3, yj−1=xj−1−2≥5, and yj−2=xj−2+1. By Fact 8, we only need to check m(δ′,2,vj−1). By (3.1) and (3.2), we can verify m(δ′,2,vj−1)≥t+1.
Lemma 3.4. For t≥13 and n≥6, there exists an optimal (2,t)-solvable distribution δ of Cn such that δ(v)≥3 for each vertex v of Cn and xk=3 implies xk+1≥4 for any k∈[0,n−1].
Proof. By Lemma 3.3, we assume that δ=⟨x0,x1,⋯,xn−1⟩ is an optimal (2,t)-solvable distribution of Cn such that δ(v)≥3 for each vertex v of Cn. Suppose that xj−1=3 and xj=3 or xj=3 and xj+1=3 for some j∈[0,n−1]. Then, let δ′=⟨y0,y1,⋯,yn−1⟩ be defined as the description in Lemma 3.1. For the case that xj−1=3 and xj=3, it suffices to show that δ′(vk)≥4 for k=j or j−1 and δ′(vi)≥4 or δ′(vi)=xi for i∈[0,n−1]∖{k} and |δ′(Cn)|≤|δ(Cn)|. For the case that xj=3 and xj+1=3, it suffices to show that δ′(vk)≥4 for k=j or j+1 and δ′(vi)≥4 or δ′(vi)=xi for i∈[0,n−1]∖{k} and |δ′(Cn)|≤|δ(Cn)|.
Case 1. xj−1=3 and xj=3.
By (3.4) and Fact 3, we have
xj−2≥2(t+r−xj−xj−1)=2(13+r−3−3)≥14 |
and
m(δ,2,vj−2)≥⌊(⌊xj−4/2⌋+xj−3)/2⌋+2(t+r−xj−xj−1)+⌊(xj−1+⌊xj/2⌋)/2⌋≥⌊(⌊3/2⌋+3)/2⌋+t+13+2r−6−6+⌊(3+⌊3/2⌋)/2⌋≥t+5. |
Let yj=xj+2=5, yj−1=xj−1+2=5, yj−2=xj−2−8≥6, and yj−3=xj−3+4. Then, by Fact 5, δ′ is a desired distribution.
Case 2. xj=3 and xj+1=3.
If r=0, then by (3.5) and Fact 4, we have xj+2≥14 and m(δ,2,vj+2)≥t+5. Let yj=xj+2=5, yj+1=xj+1+2=5, yj+2=xj+2−8≥6, and yj+3=xj+3+4≥7. Then, by Fact 5, δ′ is a desired distribution. Otherwise, r≥1. Suppose that r=1. Then, by (3.5) and Fact 4, we have xj+2≥12 and m(δ,2,vj+2)≥t+3. Let yj+1=xj+1+2=5, yj+2=xj+2−4≥8, and yj+3=xj+3+2≥5. Then, by Fact 7, δ′ is a desired distribution. Suppose that r≥2 and xj−1≤5. Then, by (3.4) and Fact 3, we have xj−2≥14 and m(δ,2,vj−2)≥t+5. Let yj=xj+2=5, yj−1=xj−1+2≥5, yj−2=xj−2−8≥6, and yj−3=xj−3+4≥7. Then, by Fact 5, δ′ is a desired distribution. Suppose that r≥2 and xj−1≥6. Then, by Fact 1, we have m(δ,2,vj−1)≥t+1. If xj−1 is odd, let yj=xj+1=4, yj−1=xj−1−1≥5. We only need to check m(δ′,2,vj−2) and m(δ′,2,vj−3). By using (3.1), it is easy to see that m(δ′,2,vj−2)=m(δ,2,vj−2) and m(δ′,2,vj−3)=m(δ,2,vj−3). Otherwise, xj−1 is even, let yj=xj+1=4, yj−1=xj−1−2≥4, and yj−2=xj−2+1≥4. We only need to check m(δ′,2,vj−1). By (3.1) and (3.2), we have
m(δ′,2,vj−1)=⌊(⌊yj−3/2⌋+yj−2)/2⌋+yj−1+⌊(yj+⌊yj+1/2⌋)/2⌋=⌊(⌊xj−3/2⌋+xj−2+1)/2⌋+xj−1−2+⌊(xj+1+⌊xj+1/2⌋)/2⌋≥⌊(⌊3/2⌋+1)/2⌋+⌊xj−2/2⌋+xj−1−2+⌊(4+⌊xj+1/2⌋)/2⌋≥1+(t+r−xj)−2+2=t. |
This completes the proof.
We demonstrate the techniques of Lemmas 3.1–3.4 with the following example.
Let δ=⟨4,8,12,0,3,14⟩ be a distribution of C6 such that 0=xj. Note that δ is (2,13)-solvable. By Eq (3.2), r=3. Since xj−1≥9, by Case 3 in Lemma 3.1, δ is modified to ⟨4,10,8,2,3,14⟩ with xj=2. Note that at this stage, the new δ is still (2,13)-solvable, δ(v)≥2 for all v∈V(C6) and r=2. Since xj−1≥7, by Case 3 of Lemma 3.3, δ is modified to ⟨4,11,6,3,3,14⟩. Note that at this stage the new δ is still (2,13)-solvable, δ(v)≥3 for all v∈V(C6), xj=xj+1=3, and r=1. By Case 2 of Lemma 3.4, δ is modified to ⟨6,11,6,3,5,10⟩. Note that xj+1≥4 and δ is still (2,13)-solvable. Now, we are in a position to make a (2,13)-solvable δ such that δ(v)≥4 for each vertex v of the cycle with the following proposition.
Proposition 3.2. If t≥13 and n≥6, then there exists an optimal (2,t)-solvable distribution δ of Cn such that δ(v)≥4 for each vertex v of Cn.
Proof. By Lemma 3.4, we assume that δ=⟨x0,x1,⋯,xn−1⟩ is an optimal (2,t)-solvable distribution of Cn such that xi≥3 for all i∈[0,n−1] and xk=3 implies xk+1≥4 for any k∈[0,n−1]. Suppose that xj=3 for some j∈[0,n−1]. Then, let δ′=⟨y0,y1,⋯,yn−1⟩ be defined as the description in Lemma 3.1. It suffices to show that δ′(vj)≥4 and δ′(vk)≥4 or δ′(vk)=xk for k∈[0,n−1]∖{j} and |δ′(Cn)|≤|δ(Cn)|.
By (3.4) and Fact 3, we have xj−2≥2(10+r−xj−1) and m(δ,2,vj−2)≥t+9+2r−(2xj−1−⌊(xj−1+1)/2⌋).
Case 1. r=0.
If 4≤xj−1≤6 and xj+1≥4, let yj=xj+1=4, yj−2=xj−2−2≥2(t+r−xj−xj−1)−2≥2(13+0−3−6)−2≥6, and yj−3=xj−3+1. Clearly, |δ′(Cn)|=|δ(Cn)|. By (3.1), it is easy to see that m(δ′,2,vi)=m(δ,2,vi) for i∈[0,n−1]∖{j−5,j−4,j−3,j−2,j−1,j,j+1,j+2}. For n≥9, vi∉{vj−3,vj−2,vj} for i∈{j−7,j−6,j−5,j−4,j+1,j+2,j+3,j+4,j+5}. By (3.1), it is easy to check that m(δ′,2,vi)≥m(δ,2,vi) for i∈{j−5,j−4,j−3,j,j+1,j+2}. Hence, we only need to check m(δ′,2,vj−1) and m(δ′,2,vj−2). Note that xj−3≥4 or xj−4≥4. It follows that ⌊xj−4/2⌋+xj−3≥5. By (3.1)–(3.3), we have
m(δ′,2,vj−1)=⌊(xj−3+1)/4⌋+⌊(xj−2−2)/2⌋+xj−1+⌊(xj+1+⌊xj+1/2⌋)/2⌋≥⌊(3+1)/4⌋+(t+r−xj)−1+⌊(4+⌊4/2⌋)/2⌋=t, |
and
m(δ′,2,vj−2)=⌊(⌊xj−4/2⌋+xj−3+1)/2⌋+xj−2−2+⌊(xj−1+⌊(xj+1)/2⌋)/2⌋≥⌊(5+1)/2⌋+2(t+r−xj−xj−1)−2+⌊(xj−1+⌊4/2⌋)/2⌋≥t. |
For the case that 6≤n≤8, without loss of generality, let j=0. Then by (3.1)–(3.3), it is easy to verify that δ′ is (2,t)-solvable by checking m(δ′,2,vi) for each i∈[0,n−1].
Similarly, if xj−1≥4 and 4≤xj+1≤6, let yj=xj+1=4, yj+2=xj+2−2≥6, and yj+3=xj+3+1. Then, |δ′(Cn)|=|δ(Cn)| and δ′ is (2,t)-solvable.
Now, we can assume that xj−1≥7 and xj+1≥7. If xj−1=xj+1=7, then xj−1 and xj+1 are both odd. Let yj=xj+2=5, yj−1=xj−1−1=6 and yj+1=xj+1−1=6. Then, by Fact 9, we have |δ′(Cn)|=|δ(Cn)| and δ′ is (2,t)-solvable.
For the case xj−1≥7 and xj+1≥8, let yj=xj+1=4, yj−1=xj−1−2≥5, and yj−2=xj−2+1. Then, by Fact 8, we only need to check m(δ′,2,vj−1). By (3.1) and (3.2), we can verify m(δ′,2,vj−1)≥t.
Similarly, for the case xj−1≥8 and xj+1≥7, let yj=xj+1=4, yj+1=xj+1−2≥5, and yj+2=xj+2+1. Then, |δ′(Cn)|=|δ(Cn)| and δ′ is (2,t)-solvable.
Case 2. r=1.
If xj−1=4, then xj−2≥2(10+1−4)=14 and m(δ,2,vj−2)≥t+9+2−(2⋅4−⌊4/2⌋)=t+5. Let yj=xj+2=5, yj+1=xj+1+2, yj−2=xj−2−8≥6, and yj−3=xj−3+4. By Fact 5, |δ′(Cn)|=|δ(Cn)| and δ′ is (2,t)-solvable. Otherwise, xj−1≥5. If xj−1=5, then xj and xj−1 are both odd. Let yj=xj+1=4 and yj−1=xj−1−1=4. By Fact 10, we only need to check m(δ′,2,vj−1). By (3.1) and (3.2), we can verify m(δ′,2,vj−1)≥t.
Now, we can assume that xj−1≥6. Let yj=xj+1=4, yj−1=xj−1−2≥4, and yj−2=xj−2+1. By Fact 8, we only need to check m(δ′,2,vj−1). By using (3.1) and (3.2), we can verify m(δ′,2,vj−1)≥t.
Case 3. r≥2.
If xj−1≤5, then xj−2≥2(10+2−5)=14 and m(δ,2,vj−2)≥t+9+4−(2⋅5−⌊5/2⌋)=t+5. Let yj=xj+2=5, yj−1=xj−1+2, yj−2=xj−2−8≥6, and yj−3=xj−3+4. By Fact 5, we have |δ′(Cn)|=|δ(Cn)| and δ′ is (2,t)-solvable. Otherwise, xj−1≥6. Let yj=xj+1=4, yj−1=xj−1−2≥4, and yj−2=xj−2+1. By Fact 8, we only need to check m(δ′,2,vj−1). By using (3.1) and (3.2), we can verify m(δ′,2,vj−1)≥t+1.
As a demonstration of the techniques used in the proof of Proposition 3.2, we give one example for each of the three cases.
For t=13,n=6, we let δ=⟨xj−3,xj−2,xj−1,xj,xj+1,xj+2⟩.
If δ=⟨4,12,4,3,4,12⟩, then, δ is a (2,13)-solvable distribution of C6 with xj=3. By Eq (3.2), r=0. Since xj−1=xj+1=4, δ′=⟨5,10,4,4,4,12⟩.
If δ=⟨6,11,6,3,5,10⟩, then δ is (2,13)-solvable and r=1. Since xj−1≥6, δ′=⟨6,12,4,4,5,10⟩. Note that this is a continuation of the example above Proposition 3.2.
If δ=⟨4,12,6,3,4,12⟩, then δ is (2,13)-solvable and r=2. Since xj−1≥6, δ′=⟨4,13,4,4,4,12⟩.
Note that in all examples above δ′(v)≥4 for each v∈V(C6) and δ′ is still (2,13)-solvable.
By combining Propositions 3.1 and 3.2, we have the following.
Theorem 3.1. For t≥13 and n≥6, π∗(2,t)(Cn)=π∗(2,t−10)(Cn)+4n.
By using Theorem 3.1 repeatedly (if necessary), we have the following.
Corollary 3.1. For n≥6, π∗(2,10k+r)(Cn)=π∗(2,r)(Cn)+4kn, where k≥1 and 3≤r≤12.
Let δ=⟨x0,x1,x2,x3⟩ be a (2,t)-solvable distribution of C4. Note that vi−2=vi+2 for all i∈[0,3]. Hence, Eq (3.1) is not true for C4; it must be modified into the following:
m(δ,2,vi)=max{mi|yi−2+yi+2=xi+2}, | (4.1) |
where mi=⌊(⌊yi−2/2⌋+xi−1)/2⌋+xi+⌊(xi+1+⌊yi+2/2⌋)/2⌋.
This implies that if xi+2≤1, then
m(δ,2,vi)=⌊xi−12⌋+xi+⌊xi+12⌋+⌊xi+24⌋. |
Otherwise,
m(δ,2,vi)=xi+⌊12(xi−1+xi+1+⌊xi+22⌋)⌋. |
It follows that 94(x0+x1+x2+x3)≥4t or x0+x1+x2+x3≥16t9. This implies
π∗(2,t)(C4)≥⌈16t9⌉. | (4.2) |
It is not difficult to see ⟨4k,4k,4k,4k⟩ is an optimal (2,9k)-solvable distribution of C4 for k≥1. Thus, we have the following.
Proposition 4.1. For k≥1, π∗(2,9k)(C4)=16k.
Clearly, π∗(2,9k+r)(C4)≤π∗(2,9k)(C4)+π∗(2,r)(C4) for r≥1. Also, by Proposition 4.1, for k≥1, we have
π∗(2,9k+r)(C4)≤16k+π∗(2,r)(C4). | (4.3) |
It is known that π∗(C4)=⌈2×43⌉=3, see [2]. So, we have the following.
Proposition 4.2. π∗(2,1)(C4)=3.
Proposition 4.3. If t=9k+1 and k≥1, then π∗(2,t)(C4)=⌈16t/9⌉.
Proof. For k=1, by (4.2), we have π∗(2,10)(C4)≥⌈160/9⌉=18. By (4.1), it is easy to check that ⟨4,5,4,5⟩ is a (2,10)-solvable distribution of C4. Hence, we have π∗(2,10)(C4)=18. For k≥2, by (4.2), we have π∗(2,9k+1)(C4)≥⌈16(9k+1)/9⌉. Also, by (4.3), we have π∗(2,9k+1)(C4)=π∗(2,9(k−1)+10)(C4)≤16(k−1)+π∗(2,10)(C4)=16(k−1)+18=⌈16(9k+1)/9⌉. This completes the proof.
Proposition 4.4. For r∈{2,3,4,6,7,8}, if t=9k+r and k≥0, then π∗(2,t)(C4)=⌈16t/9⌉.
Proof. For k≥0 and r≥0, by (4.2), we have π∗(2,9k+r)(C4)≥⌈16(9k+r)/9⌉=16k+⌈16r9⌉. Also, by (4.3), we have π∗(2,9k+r)(C4)≤16k+π∗(2,r)(C4). So, it suffices to prove that π∗(2,r)(C4)≤⌈16r9⌉ for r∈{2,3,4,6,7,8}. We will prove it by constructing a (2,r)-solvable distribution with ⌈16r9⌉ pebbles for r∈{2,3,4,6,7,8}. Let
δ2=⟨2,0,2,0⟩,δ3=⟨2,0,4,0⟩,δ4=⟨2,2,2,2⟩,δ6=⟨4,2,3,2⟩,δ7=⟨4,3,3,3⟩,δ8=⟨4,4,3,4⟩. |
It is easy to see |δr(C5)|=⌈16r9⌉ and by using (4.1), it is not difficult to verify that δr is a (2,r)-solvable distribution of C4 for each r∈{2,3,4,6,7,8}.
Proposition 4.5. If t=9k+5 and k≥0, then π∗(2,t)(C4)=⌈16t/9⌉+1.
Proof. For k=0, by (4.1), it is easy to check that ⟨4,2,2,2⟩ is a (2,5)-solvable distribution of C4. Hence, we have π∗(2,5)(C4)≤10. For k≥1, by (∗∗2), we have π∗(2,9k+5)(C4)≤16k+π∗(2,5)(C4)≤16k+10. Assume that δ=⟨x0,x1,x2,x3⟩ is a (2,9k+5)-solvable distribution of C4 with x0+x1+x2+x3=16k+9, where k≥0. Let xi=4k+ri, i=0,1,2,3. Then, r0+r1+r2+r3=9. Without loss of generality, let r0=min{ri|i=0,1,2,3}. By (4.1), we have x0+(x1+x3)/2+x2/4=9k+r0+(r1+r3)/2+r2/4≥m(δ,2,v0)≥9k+5. This implies that r0+(r1+r3)/2+r2/4≥5, equivalently, r0+r1+r2+r3≥10−r0+r2/2. Thus, 9≥10−r0+r2/2, and we have r0≥1+r2/2≥1+r0/2. Hence, r0≥2. This implies that δ is one of the following distributions:
⟨4k+2,4k+3,4k+2,4k+2⟩,⟨4k+2,4k+2,4k+3,4k+2⟩,⟨4k+2,4k+2,4k+2,4k+3⟩. |
It is easy to check that δ is not (2,9k+5)-solvable, which is a contradiction. Therefore, π∗(2,9k+5)(C4)≥16k+10=⌈16(9k+5)/9⌉+1, and we have the proof.
By Propositions 4.1–4.5, we conclude the following.
Theorem 4.1. Let t be a positive integer. If t=1 or tmod9=5, then π∗(2,t)(C4)=⌈16t/9⌉+1. Otherwise, π∗(2,t)(C4)=⌈16t/9⌉.
Let δ=⟨x0,x1,x2,x3,x4⟩ be a (2,t)-solvable distribution of C5. Then we have
xi+(xi+1+xi−1)/2+(xi+2+xi−2)/4≥m(δ,2,vi)≥t. | (5.1) |
for each i∈[0,4]. This implies that 52(x0+x1+x2+x3+x4)≥5t. Thus,
π∗(2,t)(C5)≥2t. | (5.2) |
Note that Eq (3.1) is not always true for C5. For example, let δ=⟨0,1,1,2,0⟩. Then, we can move one pebble to v0 by applying three pebbling moves. First, we can move one pebble to v2 from v3, and then move one pebble to v1 from v2. Finally, we can move one pebble to v0 from v1. But, when we use (3.1), we have ⌊12(⌊x32⌋+x4)⌋+x0+⌊12(x1+⌊x22⌋)⌋=0. So, Eq (3.1) should be modified into the following:
m(δ,2,vi)=max{mi,j|j=1,2,3}, | (5.3) |
where
mi,1=⌊(⌊xi−2/2⌋+xi−1)/2⌋+xi+⌊(xi+1+⌊xi+2/2⌋)/2⌋, |
mi,2={mi,1,if xi−2≤1;⌊⌊(xi−2−2)/2⌋+xi−12⌋+xi+⌊xi+1+⌊(xi+2+1)/2⌋2⌋,otherwise, |
and
mi,2={mi,1,if xi+2≤1;⌊⌊(xi−2+1)/2⌋+xi−12⌋+xi+⌊xi+1+⌊(xi+2−2)/2⌋2⌋,otherwise. |
By Corollary 2.1, we have the following.
Proposition 5.1. π∗(2,10k)(C5)=20k for k≥1.
By Proposition 5.1, we have the following.
Lemma 5.1. π∗(2,10k+r)(C5)≤20k+π∗(2,r)(C5) for k≥1 and r≥1.
Now, we will give a lower bound for π∗(2,t)(C5) when tmod10≠0.
Lemma 5.2. π∗(2,t)(C5)≥2t+1 when tmod10≠0.
Proof. Let δ=⟨x0,x1,x2,x3,x4⟩ be an optimal (2,t)-solvable distribution of C5. By (5.2), we have π∗(2,t)(C5)≥2t. By (5.1), we can write xi+(xi+1+xi−1)/2+(xi+2+xi−2)/4=t+si, where si is a nonnegative real number for each i∈[0,4]. If π∗(2,t)(C5)=2t, then si=0 for all i∈[0,4], and this system of linear equations can be represented as a matrix.
[11/21/41/41/2t1/211/21/41/4t1/41/211/21/4t1/41/41/211/2t1/21/41/41/21t]. |
After Gaussian elimination, we have
[100002t/5010002t/5001002t/5000102t/5000012t/5]. |
Thus, the system of equations has a unique solution x0=x1=x2=x3=x4=2t5. If tmod5≠0, then the solution is not integral, hence, there exists at least one i∈[0,4] such that si>0. This implies π∗(2,t)(C5)≥2t+1 because π∗(2,t)(C5) is an integer. If tmod10=5 and π∗(2,t)(C5)=2t, let t=10k+5, where k is a nonnegative integer, then δ=⟨4k+2,4k+2,4k+2,4k+2,4k+2⟩. It is easy to check that δ is not (2,t)-solvable. It leads to a contradiction and hence π∗(2,t)(C5)≥2t+1. This completes the proof.
It is known that π∗(C5)=⌈2×53⌉=4, see [2]. So, we have the following.
Proposition 5.2. π∗(2,1)(C5)=4.
In 2018, Chen and Shiue [4] showed that π∗(2,2)(C3)=4 and π∗(2,2)(Cn)=n for n≥4. So, we have the following.
Proposition 5.3. π∗(2,2)(C5)=5.
Lemma 5.3. π∗(2,r)(C5)=2r+1 for r∈[2,9]∪{11}.
Proof. By Proposition 5.3, it is true for r=2. By Lemma 5.2, we have π∗(2,r)(C5)≥2r+1 for r∈[3,9]∪{11}. We will prove that the lower bound is also an upper bound by constructing a (2,r)-solvable distribution with 2r+1 pebbles. Let
δ3=⟨1,2,1,2,1⟩,δ4=⟨1,3,1,2,2⟩,δ5=⟨3,2,2,2,2⟩,δ6=⟨4,2,2,3,2⟩,δ7=⟨3,3,3,3,3⟩,δ8=⟨3,4,3,3,4⟩,δ9=⟨3,4,4,4,4⟩,andδ11=⟨5,4,5,5,4⟩. |
Clearly, |δr(C5)|=2r+1. Then, by using (5.3), it is not difficult to verify that δr is a (2,r)-solvable distribution of C5 for each r∈[3,9]∪{11}.
Proposition 5.4. π∗(2,10k+r)(C5)=20k+2r+1 for k≥0 and r∈[2,9]∪{11}.
Proof. By Lemma 5.3, it is true for k=0. By combining Proposition 5.1 and Lemma 5.3, we have π∗(2,10k+r)(C5)≤20k+π∗(2,r)(C5)=20k+2r+1 for k≥1. By Lemma 5.2, we can see that the upper bound is also a lower bound, hence, we have the proof.
By combining Propositions 5.1, 5.2, and 5.4, we have the main result of this section.
Theorem 5.1. Let t be a positive integer. Then,
π∗(2,t)(C5)={4, if t=1;2t, if tmod10=0;2t+1, if t≥2 and tmod10≠0. |
In 2018, the distance-restricted pebbling was first proposed by Chen and Shiue [4], and they showed that π∗(2,2)(C3)=4 and π∗(2,2)(Cn)=n for n≥4. In 2020, Shiue [13] studied distance 1-restricted pebbling in cycles, and he determined the exact value of π∗(1,t)(Cn) for all t≥1 and n≥3; see Theorem 2.1. For t=1, π∗(1,1)(Cn)=π∗(Cn)=⌈2n3⌉; see [2]. This implies that π∗(d,1)(Cn)=⌈2n3⌉ for all d≥1. Thus, we have π∗(2,1)(Cn)=⌈2n3⌉.
"(d,t)-pebbling" can be seen as a generalization of optimal pebbling. In addition to this, it is our belief that (d,t)-pebbling is more applicable than other versions of pebbling. For example, in a transportation and resource allocation system, the resource must be delivered to a target in a set amount of time, thus, in practicality, we need to restrict the distance to the target. Ideally, in such a resource allocation scheme, the storehouses for the resources should have a capacity restriction since the space for the storehouse is limited. Studies on capacity-restricted optimal pebbling can be found in [3,10]. We discussed the optimal capacity and distance-restricted t-fold pebbling, also known as the optimal (c,d,t)-pebbling number, in [15]. In some sense, π∗(d,t)(G) can also be viewed as a distance-based parameter, which is a topic that has been studied before, for example, in [1].
In this article, we give a further study into "(d,t)-pebbling". Our result makes progress towards understanding (d,t)-pebbling for cycles. Specifically, we study (2,t)-pebbling as a continuation from the study of (1,t)-pebbling done in [13]. We were able to show that the optimal (2,t)-pebbling number of cycles can be determined by considering only a finite number of cases, namely, 1≤t≤12. We were also able to completely determine the optimal (2,t)-pebbling number for C4 and C5. For cycles of length greater than 5, our result relies on repeated application of the tools developed in Facts 1–10. For cycles of length not greater than 5, the key to our results is obtained by modifying Eq (3.1). The process of obtaining a lower bound for π∗(2,t)(C5) involves the solution of a system of linear equations whose matrix is positive semi-definite. For arbitrarily large distance d, the matrix can be very large. Thus, in order to obtain a lower bound for π∗(d,t)(Cn) when d>2, one may consider the use of the conjugate gradient method; see [6].
Finally, we will give a summary of progress towards the determination of π∗(2,t)(Cn) for all n≥3 and t≥1. Corollary 3.1 implies that the problem of determining the exact value of π∗(2,t)(Cn) for n≥6 and t≥1 can be reduced to the problem of determining the exact value of π∗(2,r)(Cn) for n≥6 and r∈[1,12]. By the discussion above, we know the exact value of π∗(2,t)(Cn) for n≥3 and t=1,2. Furthermore, note that the diameter of C3 is equal to one. This implies that π∗(2,t)(C3)=π∗(1,t)(C3) for t≥1, see Theorem 2.1. Theorems 4.1 and 5.1 give the exact value of π∗(2,t)(Cn) for n=4,5 and t≥1. So, to completely determine the exact value of π∗(2,t)(Cn) for n≥3 and t≥1, it is left to solve the following problem.
Problem 2. Determine the exact value of π∗(2,t)(Cn) for n≥6 and 3≤t≤12.
Recently, we have shown that π∗(2,3)(Cn)=⌈4n3⌉ for n≥4, see [15]. By combining Corollary 3.1, we have π∗(2,10k+3)(Cn)=⌈4n3⌉+4kn for n≥6 and k≥0. For example, by using the two facts that ⟨4,0,0,4,0,0⟩ is an optimal (2,3)-solvable distribution of C6 (see [15]) and that ⟨4,4,4,4,4,4⟩ is an optimal (2,10)-solvable distribution of C6 (see [13]), we can conclude that ⟨8,4,4,8,4,4⟩ is an optimal (2,13)-solvable distribution of C6.
Chin-Lin Shiue: Conceptualization, Supervision, Writing–original draft; Tzu-Hsien Kwong: Conceptualization, Validation, Writing–review and editing. All authors have read and agreed to the published version of the manuscript.
The authors declare they have not used Artificial Intelligence (AI) tools in the creation of this article.
This research was supported in part by the Ministry of Science and Technology of Taiwan under Grant MOST 111-2115-M-033-003.
The authors declare that there are no conflicts of interest in this paper.
[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 |