Loading [MathJax]/jax/output/SVG/jax.js
Research article Special Issues

Distance 2-restricted optimal pebbling in cycles

  • 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]={uV(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 vV(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 vV(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 n6, π(2,t)(Cn)=π(2,t10)(Cn)+4n for t13. It follows that if n6, then π(2,10k+r)(Cn)=π(2,r)(Cn)+4kn for k1 and 3r12. Consequently, for n6, the problem of determining the exact value of π(2,t)(Cn) for all t1 can be reduced to the problem of determining the exact value of π(2,r)(Cn) for r[1,12]. We also consider Cn with 3n5. 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 t1.

    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:

    [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]={uV(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 vV(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 vV(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 n6, π(2,t)(Cn)=π(2,t10)(Cn)+4n for t13. It follows that if n6, then π(2,10k+r)(Cn)=π(2,r)(Cn)+4kn for k1 and 3r12. Consequently, for n6, the problem of determining the exact value of π(2,t)(Cn) for all t1 can be reduced to the problem of determining the exact value of π(2,r)(Cn) for r[1,12]. We also consider Cn with 3n5. 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 t1.



    Let G be a graph. A distribution δ of G is a mapping from V(G) to the set of nonnegative integers. For each vertex vV(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 vV(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]={uV(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 n4. 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, n3. 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 t3.

    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 n5, then π(2,10k)(Cn)=4nk for each positive integer k.

    The conclusion of Corollary 2.1 gives the recurrence relation π(2,10k)(Cn)=π(2,10k10)(Cn)+4n=π(2,10k10)(Cn)+π(2,10)(Cn) for k2. Hence, we are interested in the following problem.

    Problem 1. For n5 and t11, determine the values of t that satisfy the recurrence relation

    π(2,t)(Cn)=π(2,t10)(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 n4 and t3. In this article, we show that for t13 and n6, π(2,t)(Cn)=π(2,t10)(Cn)+4n in Section 2 and completely determine the exact value of πt(Cn) for n=4,5, and t1 in Sections 4 and 5, respectively.

    Throughout the rest of this article, let Cn=v0,v1,,vn1,v0 be an n-cycle, n3, 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,,xn1 to denote δ, where xi=δ(vi). Thus, |δ(Cn)|=n1i=0xi. Note that the diameter of Cn is not more than two for 3n5. It follows that π(2,t)(Cn)=πt(Cn) for 3n5. So we only consider the case when n6 in this section. For n6, and for i[0,n1],

    m(δ,2,vi)=12(xi22+xi1)+xi+12(xi+1+xi+22). (3.1)

    The following proposition is an important key for solving Problem 1.

    Proposition 3.1. For t11 and n6, if there exists an optimal (2,t)-solvable distribution δ=x0,x1,,xn1 of Cn such that xi4 for i[0,n1], then π(2,t)(Cn)=π(2,t10)(Cn)+4n.

    Proof. Assume that t11 and n6. By Corollary 2.1, we have π(2,10)(Cn)=4n. It follows that

    π(2,t)(Cn)π(2,t10)(Cn)+π(2,10)(Cn)=π(2,t10)(Cn)+4n.

    Thus,

    π(2,t10)(Cn)π(2,t)(Cn)4n.

    Assume that δ=x0,x1,,xn1 is an optimal (2,t)-solvable distribution of Cn with xi4 for all i[0,n1]. Then let δ=y0,y1,,yn1 be a distribution of Cn such that yi=xi4 for i[0,n1]. Clearly,

    |δ(Cn)|=|δ(Cn)|4n=π(2,t)(Cn)4n.

    To complete the proof, it is left to show that δ is (2,t10)-solvable. For i[0,n1], by (3.1), we have

    m(δ,2,vi)=yi22+yi12+yi+yi+22+yi+12=xi242+xi142+xi4+xi+242+xi+142=xi22+xi12+xi+xi+22+xi+1210=m(δ,2,vi)10t10.

    Thus, δ is (2,t10)-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,,xn1 be a (2,t)-solvable distribution of Cn with n6. Consider any subpath

    vj5,vj4,vj3,vj2,vj1,vj,vj+1,vj+2,vj+3,vj+4,vj+5

    in Cn, for some j[0,n1]. When 6n10, the subpath is the cycle Cn. We let n=10k, where 0k4. Then the vertex vj+5i=vj5+ki for i[0,k]. For example, if n=8, then vj+5=vj3, vj+4=vj4, and vj+3=vj5. By (3.1), we have

    m(δ,2,vj)=(xj2/2+xj1)/2+xj+(xj+1+xj+2/2)/2t.

    It follows that

    (xj2/2+xj1)+(xj+1+xj+2/2)2(txj).

    Without loss of generality, we can assume that

    xj2/2+xj1=t+rxj, (3.2)

    where r is a nonnegative integer. Then we have

    xj+1+xj+2/2trxj. (3.3)

    It follows that

    xj22(t+rxjxj1) (3.4)

    and

    xj+22(trxjxj+1). (3.5)

    By (3.1)–(3.5), we have the following four facts:

    Fact 1.

    m(δ,2,vj1)=(xj3/2+xj2)/2+xj1+(xj+xj+1/2)/2xj3/4+xj2/2+xj1+(xj+xj+1/2)/2=xj3/4+(t+rxj)+(xj+xj+1/2)/2.

    Fact 2.

    m(δ,2,vj+1)=(xj1/2+xj)/2+xj+1+(xj+2+xj+3/2)/2(xj1/2+xj)/2+xj+1+xj+2/2+xj+3/4(xj1/2+xj)/2+(trxj)+xj+3/4.

    Fact 3.

    m(δ,2,vj2)=(xj4/2+xj3)/2+xj2+(xj1+xj/2)/2(xj4/2+xj3)/2+2(t+rxjxj1)+(xj1+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(trxjxj+1)+(xj+3+xj+4/2)/2.

    Fact 5. If xj28 and δ=y0,y1,,yn1 is a distribution of Cn such that yj=xj+2, yj1=xj1+2, yj2=xj28, yj3=xj3+4, and yi=xi for i[0,n1][j3,j], then |δ(Cn)|=|δ(Cn)|, m(δ,2,vj2)m(δ,2,vj2)5 and m(δ,2,vi)m(δ,2,vi) for i[0,n1]{j2}.

    Proof. Clearly, |δ(Cn)|=|δ(Cn)|. If n11, then the vertices

    vj5,vj4,vj3,vj2,vj1,vj,vj+1,vj+2,vj+3,vj+4,vj+5

    are all distinct. Otherwise, 6n10. Let n=10k, where 0k4. Then, the vertex vj+5i=vj5+ki for i[0,4]. By (3.1), it is easy to see that m(δ,2,vi)m(δ,2,vi) for i[0,n1]{j2,j1}. So, we only need to check m(δ,2,vj2) and m(δ,2,vj1). Since n6, vi{vj3,vj2,vj1,vj} for i{j4,j+1}. By (3.1), we have

    m(δ,2,vj2)=(yj4/2+yj3)/2+yj2+(yj1+yj/2)/2=(xj4/2+xj3+4)/2+xj28+(xj1+2+(xj+2)/2)/2(xj4/2+xj3)/2+xj2+(xj1+xj/2)/2+28+1=m(δ,2,vj2)5,

    and

    m(δ,2,vj1)=(yj3/2+yj2)/2+yj1+(yj+yj+1/2)/2=((xj3+4)/2+xj28)/2+xj1+2+(xj+2+xj+1/2)/2=(xj3/2+xj2)/2+xj1+(xj+xj+1/2)/23+2+1=m(δ,2,vj1).

    Fact 6. If xj24 and δ=y0,y1,,yn1 is a distribution of Cn such that yj=xj+1, yj1=xj1+1, yj2=xj24, yj3=xj3+2 and yi=xi for i[0,n1][j3,j], then |δ(Cn)|=|δ(Cn)|, m(δ,2,vj2)m(δ,2,vj2)3, m(δ,2,vj1)m(δ,2,vj1)1 and m(δ,2,vi)m(δ,2,vi) for i[0,n1]{j1,j2}.

    Proof. Clearly, |δ(Cn)|=|δ(Cn)|. If n11, then the vertices

    vj5,vj4,vj3,vj2,vj1,vj,vj+1,vj+2,vj+3,vj+4,vj+5

    are all distinct. Otherwise, 6n10. Let n=10k, where 0k4. Then the vertex vj+5i=vj5+ki for i[0,4]. By (3.1), it is easy to see that m(δ,2,vi)m(δ,2,vi) for i[0,n1]{j2,j1}. Now, we only need to check m(δ,2,vj2) and m(δ,2,vj1). Since n6, vi{vj3,vj2,vj1,vj} for i{j4,j+1}. By (3.1), we have

    m(δ,2,vj2)=(yj4/2+yj3)/2+yj2+(yj1+yj/2)/2=(xj4/2+xj3+2)/2+xj24+(xj1+1+(xj+1)/2)/2(xj4/2+xj3)/2+xj2+(xj1+xj)/2+14=m(δ,2,vj2)3,

    and

    m(δ,2,vj1)=(yj3/2+yj2)/2+yj1+(yj+yj+1/2)/2=((xj3+2)/2+xj24)/2+xj1+1+(xj+1+xj+1/2)/2(xj3/2+xj2)/2+xj1+(xj+xj+1/2)/22+1=m(δ,2,vj1)1.

    By using Eq (3.1) to check, we can obtain Facts 7 and 8.

    Fact 7. If xj14 and δ=y0,y1,,yn1 is a distribution of Cn such that yj=xj+2, yj1=xj14, yj2=xj2+2, and yi=xi for i[0,n1][j2,j], then |δ(Cn)|=|δ(Cn)|, m(δ,2,vj1)=m(δ,2,vj1)2 and m(δ,2,vi)m(δ,2,vi) for i[0,n1]{j1}.

    Fact 8. If xj12 and δ=y0,y1,,yn1 is a distribution of Cn such that yj=xj+1, yj1=xj12, yj2=xj2+1, and yi=xi for i[0,n1][j2,j], then |δ(Cn)|=|δ(Cn)|, m(δ,2,vj1)m(δ,2,vj1)2 and m(δ,2,vi)m(δ,2,vi) for i[0,n1]{j1}.

    Fact 9. If xj1 and xj+1 are both odd, and δ=y0,y1,,yn1 is a distribution of Cn such that yj=xj+2, yj1=xj11, yj+1=xj+11, and yi=xi for i[0,n1][j1,j,j+1], then |δ(Cn)|=|δ(Cn)| and m(δ,2,vi)m(δ,2,vi) for i[0,n1].

    Proof. Clearly, |δ(Cn)|=|δ(Cn)|. If n11, then the vertices

    vj5,vj4,vj3,vj2,vj1,vj,vj+1,vj+2,vj+3,vj+4,vj+5

    are all distinct. Otherwise, 6n10. Let n=10k, where 0k4. Then, the vertex vj+5i=vj5+ki for i[0,4]. By (3.1), it is easy to see that m(δ,2,vi)=m(δ,2,vi) for i[0,n1]{j3,j2,j1,j,j+1,j+2,j+3}. So, we only need to check m(δ,2,vi) for i{j3,j2,j1,j,j+1,j+2,j+3}. Note that xj1 and xj+1 are both odd. It follows that (xj11)/2=xj1/2 and (xj+11)/2=xj+1/2. Since n6, vi{vj1,vj,vj+1} for i{j4,j3,j2,j+2}. By using (3.1) to check, we can verify that m(δ,2,vi)m(δ,2,vi) for i{j,j1,j2}. For the value of m(δ,2,vj3), if n7, then vi{vj1,vj,vj+1} for i{j5,j4,j3,j2}, and

    m(δ,2,vj3)=(yj5/2+yj4)/2+yj3+(yj2+yj1/2)/2=(xj5/2+xj4)/2+xj3+(xj2+(xj11)/2)/2=(xj5/2+xj4)/2+xj3+(xj2+xj1/2)/2=m(δ,2,vj3).

    Otherwise, n=6, and hence vj5=vj+1; then we have

    m(δ,2,vj3)=(yj5/2+yj4)/2+yj3+(yj2+yj1/2)/2=((xj51)/2+xj4)/2+xj3+(xj2+(xj11)/2)/2=(xj5/2+xj4)/2+xj3+(xj2+xj1/2)/2=m(δ,2,vj3).

    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 xj1 and xj are both odd, and δ=y0,y1,,yn1 is a distribution of Cn such that yj=xj+1, yj1=xj11, and yi=xi for i[0,n1][j1,j], then |δ(Cn)|=|δ(Cn)|, m(δ,2,vj1)m(δ,2,vj1)1 and m(δ,2,vi)m(δ,2,vi) for i[0,n1]{j1}.

    Proof. Clearly, |δ(Cn)|=|δ(Cn)|. If n11, then, the vertices

    vj5,vj4,vj3,vj2,vj1,vj,vj+1,vj+2,vj+3,vj+4,vj+5

    are all distinct. Otherwise, 6n10. Let n=10k, where 0k4. Then the vertex vj+5i=vj5+ki for i[0,4]. By (3.1), it is easy to see that m(δ,2,vi)=m(δ,2,vi) for i[0,n1]{j3,j2,j1,j,j+1,j+2}. So, we only need to check m(δ,2,vi) for i{j3,j2,j1,j,j+1,j+2}. Note that xj1 and xj are both odd. It follows that (xj11)/2=xj1/2 and (xj+1)/2=xj/2+1. Since n6, vi{vj1,vj} for i{j4,j3,j2,j+1,j+2}. By using (3.1) to check, we can verify that m(δ,2,vj1)m(δ,2,vj1)1 and m(δ,2,vj)m(δ,2,vj). For the value of m(δ,2,vj2), vi{vj1,vj} for i{j4,j3,j2}, and

    m(δ,2,vj2)=(yj4/2+yj3)/2+yj2+(yj1+yj/2)/2=(xj4/2+xj4)/2+xj2+(xj11+(xj+1)/2)/2=(xj4/2+xj3)/2+xj2+(xj1+xj/2)/2=m(δ,2,vj2).

    For the value of m(δ,2,vj3), vi{vj1,vj} for i{j5,j4,j3,j2}, and

    m(δ,2,vj3)=(yj5/2+yj4)/2+yj3+(yj2+yj1/2)/2=(xj5/2+xj4)/2+xj3+(xj2+(xj11)/2)/2=(xj5/2+xj4)/2+xj3+(xj2+xj1/2)/2=m(δ,2,vj3).

    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 t13 and n6, there exists an optimal (2,t)-solvable distribution δ of Cn such that δ(v)1 for each vertex v of Cn.

    Proof. Let δ=x0,x1,,xn1 be an optimal (2,t)-solvable distribution of Cn. Suppose that there exists a vertex vj, j[0,n1], 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,n1]{j} and |δ(Cn)||δ(Cn)|. By (3.1), we have

    (xj2/2+xj1)+(xj+1+xj+2/2)2(txj).

    Without loss of generality, we can assume that xj2/2+xj1=txj+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[j3,j+3]} if necessary. Let δ=y0,y1,,yn1 be a distribution of Cn such that yi=xi for i[0,n1][j3,j+3]. For i[j3,j+3], yi will be defined according to the following cases. Initially, we let yi=xi for i[j3,j+3].

    By (3.4) and Fact 3, we have

    xj22(t+rxjxj1)=2(13+rxj1)

    and

    m(δ,2,vj2)(xj4/2+xj3)/2+2(t+rxjxj1)+(xj1+xj/2)/2t+13+2r(2xj1xj1/2).

    Case 1. r=0.

    If xj15, then xj22(13+05)=16 and m(δ,2,vj2)t+13+0(255/2)=t+5. Let yj=xj+2=2, yj1=xj1+2, yj2=xj288, and yj3=xj3+4. By Fact 5, |δ(Cn)|=|δ(Cn)| and δ is (2,t)-solvable.

    Similarly, if xj+15, then, by (3.5) and Fact 4, we have xj+216 and m(δ,2,vj+2)t+5. Let yj=xj+2=2, yj+1=xj+1+2, yj+2=xj+288, yj+3=xj+3+4. Then, |δ(Cn)|=|δ(Cn)| and δ is (2,t)-solvable.

    Now, we can assume that xj16 and xj+16. Let yj=xj+1=1, yj1=xj124, and yj2=xj2+1. By Fact 8, we only need to check m(δ,2,vj1). By (3.1) and (3.2), we have

    m(δ,2,vj1)=(yj3/2+yj2)/2+yj1+(yj+yj+1/2)/2xj3/4+(xj2+1)/2+xj12+(xj+1+xj+1/2)/2(txj+r)2+(1+6/2)/2=t.

    Case 2. r=1.

    If xj16, then xj22(13+16)=16 and m(δ,2,vj2)t+13+2(266/2)=t+6. Let yj=xj+2=2, yj1=xj1+2, yj2=xj288, and yj3=xj3+4. Then, by Fact 5, we have |δ(Cn)|=|δ(Cn)| and δ is (2,t)-solvable. Otherwise, xj17. If xj+14, then, by Fact 1, we have m(δ,2,vj1)(t+rxj)+(xj+xj+1/2)/2t+2. Let yj=xj+2=2, yj1=xj143, and yj2=xj2+2. Then, by Fact 7, we have |δ(Cn)|=|δ(Cn)| and δ is (2,t)-solvable. If xj+13, then, by (3.5) and Fact 4, xj+22(trxjxj+1)2(13103)=18 and m(δ,2,vj+2)xj+1/2+2(trxjxj+1)3/2+t+13+2(103)=t+6. Let yj=xj+2=2, yj+1=xj+1+2, yj+2=xj+2810, and yj+3=xj+3+4. Then, by Fact 5, |δ(Cn)|=|δ(Cn)| and δ is (2,t)-solvable.

    Case 3. r2.

    If xj18, then xj22(13+28)=14 and m(δ,2,vj2)t+13+4(288/2)+4=t+5. Let yj=xj+2=2, yj1=xj1+2, yj2=xj286, and yj3=xj3+4. Then, by Fact 5, |δ(Cn)|=|δ(Cn)| and δ is (2,t)-solvable. Otherwise, xj19. By Fact 1, m(δ,2,vj1)t+rxjt+2. Let yj=xj+2=2, yj1=xj145, yj2=xj2+2. Then, by Fact 7, we have |δ(Cn)|=|δ(Cn)| and δ is (2,t)-solvable.

    Lemma 3.2. For t13 and n6, 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,,xn1 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,n1]. Then, let δ=y0,y1,,yn1 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,n1]{j} and |δ(Cn)||δ(Cn)|.

    By (3.4) and Fact 3, we have xj22(12+rxj1) and m(δ,2,vj2)t+11+2r(2xj1xj1/2).

    Case 1. r=0.

    If xj14, then xj22(12+04)=16 and m(δ,2,vj2)t+11+0(244/2)=t+5. Let yj=xj+2=3, yj1=xj1+2, yj2=xj288, and yj3=xj3+4. By Fact 5, |δ(Cn)|=|δ(Cn)| and δ is (2,t)-solvable.

    Similarly, if xj+14, then xj+216 and m(δ,2,vj+2)t+5. Let yj=xj+2=3, yj+1=xj+1+2, yj+2=xj+288, yj+3=xj+3+4. Then, |δ(Cn)|=|δ(Cn)| and δ is (2,t)-solvable.

    Now, we assume that xj15 and xj+15. Note that xj=1 is odd. If xj1 is odd, let yj=xj+1=2, and yj1=xj114. By Fact 10, we only need to check m(δ,2,vj1). By using (3.1) and (3.2), we can verify m(δ,2,vj1)t.

    Similarly, if xj+1 is odd, let yj=xj+1=2, and yj+1=xj+114. Then, |δ(Cn)|=|δ(Cn)| and δ is (2,t)-solvable.

    Now, we can assume that xj16 and xj+16, and xj1 and xj+1 are both even. For the case xj16 and xj+18, let yj=xj+1=2, yj1=xj124, and yj2=xj2+1. Then, by Fact 8, we only need to check m(δ,2,vj1). Also, by using (3.1) and (3.2), it is easy to check that m(δ,2,vj1)t.

    Similarly, for the case xj18 and xj+16, let yj=xj+1=2, yj+1=xj+124, and yj+2=xj+2+1. Then, |δ(Cn)|=|δ(Cn)| and δ is (2,t)-solvable.

    For the case xj1=xj+1=6, let yj=xj+1=2, yj1=xj11=5, yj2=xj212(t+rxjxj1)12(13+016)111, and yj3=xj3+1. Clearly, |δ(Cn)|=|δ(Cn)|. If n11, then the vertices

    vj5,vj4,vj3,vj2,vj1,vj,vj+1,vj+2,vj+3,vj+4,vj+5

    are all distinct. Otherwise, 6n10. Let n=10k, where 0k4. Then the vertex vj+5i=vj5+ki for i[0,4]. By (3.1), it is easy to see that m(δ,2,vi)=m(δ,2,vi) for i[0,n1]{j5,j4,j3,j2,j1,j,j+1,j+2}. If n9, vi{vj3,vj2,vj1,vj} for i{j7,j6,j5,j4,j+1,j+2,j+3,j+4,j+5}. Note that when n=9, vj+5=vj4 and vj+4=vj5, or when n=10, vj+5=vj5. So, for n9, it is easy to see that m(δ,2,vi)m(δ,2,vi) for i{j5,j4,j+1,j+2}. By (3.1)–(3.3), we also can verify that m(δ,2,vi)t for i{j,j1,j2,j3}. For the case that 6n8, 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,n1].

    Case 2. r=1.

    If xj15, then xj22(12+15)=16 and m(δ,2,vj2)t+11+2(255/2)=t+5. Let yj=xj+2=3, yj1=xj1+2, yj2=xj288, and yj3=xj3+4. By Fact 5, |δ(Cn)|=|δ(Cn)| and δ is (2,t)-solvable. If xj+12, then, by (3.5) and Fact 4, xj+22(trxjxj+1)2(13112)=18 and m(δ,2,vj+2)xj+1/2+2(trxjxj+1)2/2+t+132(1+1+2)=t+6. Let yj=xj+2=3, yj+1=xj+1+2, yj+2=xj+2810, and yj+3=xj+3+4. Then, |δ(Cn)|=|δ(Cn)| and δ is (2,t)-solvable. Now, we can assume that xj16 and xj+13. If xj+14, let yj=xj+1=2, yj1=xj124, and yj2=xj2+1. By Fact 8, we only need to check m(δ,2,vj1). By using (3.1) and (3.2), we can verify that m(δ,2,vj1)t. For the case xj16 and xj+1=3, let yj=xj+1=2, yj1=xj124, yj2=xj2+1, yj+1=xj+1+1, yj+2=xj+222(13113)214 and yj+3=xj+3+1. By Fact 8, we only need to check m(δ,2,vj1) and m(δ,2,vj+2). By using (3.1), (3.2) and (3.5), we can verify that m(δ,2,vj1)t and m(δ,2,vj+2)t+4.

    Case 3. r2.

    If xj16, then xj22(12+26)=16 and m(δ,2,vj2)t+11+4(266/2)=t+6. Let yj=xj+2=3, yj1=xj1+2, yj2=xj288, and yj3=xj3+4. Then, by Fact 5, we have |δ(Cn)|=|δ(Cn)| and δ is (2,t)-solvable. Otherwise, xj17. Let yj=xj+1=2, yj1=xj125, and yj2=xj2+1. Then, by Fact 8, we only need to check m(δ,2,vj1). By using (3.1) and (3.2), we can verify that m(δ,2,vj1)t.

    Lemma 3.3. For t13 and n6, 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,,xn1 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,n1]. Then, let δ=y0,y1,,yn1 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,n1]{j} and |δ(Cn)||δ(Cn)|.

    By (3.4) and Fact 3, we have xj22(11+rxj1) and m(δ,2,vj2)t+10+2r(2xj1(xj1+1)/2).

    Case 1. r=0.

    If xj13, then xj22(11+03)=16 and m(δ,2,vj2)t+10+0(23(3+1)/2)=t+6. Let yj=xj+2=4, yj1=xj1+2, yj2=xj288, and yj3=xj3+4. Similarly, if xj+13, then xj+216 and m(δ,2,vj+2)t+6. Let yj=xj+2=4, yj+1=xj+1+2, yj+2=xj+288, and yj+3=xj+3+4. By Fact 5, we have |δ(Cn)|=|δ(Cn)| and δ is (2,t)-solvable.

    Now, we can assume that xj14 and xj+14. For the case xj1=4 and xj+14, we have xj22(11+04)=14 and m(δ,2,vj2)t+10+0(24(4+1)/2)=t+4. Let yj=xj+1=3, yj1=xj1+1, yj2=xj2410, and yj3=xj3+2. Then, by Fact 6, we only need to check m(δ,2,vj1). By (3.1) and (3.2), we can verify m(δ,2,vj1)t.

    Similarly, for the case xj14 and xj+1=4, let yj=xj+1=3, yj+1=xj+1+1, yj+2=xj+2410, and yj+3=xj+3+2. Then, |δ(Cn)|=|δ(Cn)| and δ is (2,t)-solvable. Now, we can assume that xj15 and xj+15. For the case xj1=xj+1=5, let yj=xj+2=4, yj1=xj11=4, and yj+1=xj+11=4. Note that xj1 and xj+1 are both odd. By Fact 9, |δ(Cn)|=|δ(Cn)| and δ is (2,t)-solvable. For the case xj15 and xj+16, let yj=xj+1=3, yj1=xj123, and yj2=xj2+1. Then, by Fact 8, we only need to check m(δ,2,vj1). By using (3.1) and (3.2), we can verify m(δ,2,vj1)t.

    Similarly, for the case xj16 and xj+15, let yj=xj+1=3, yj+1=xj+123, and yj+2=xj+2+1. Then, |δ(Cn)|=|δ(Cn)| and δ is (2,t)-solvable.

    Case 2. r=1.

    If xj14, then xj22(11+14)=16 and m(δ,2,vj2)t+10+2(244/2)=t+6. Let yj=xj+2=4, yj1=xj1+2, yj2=xj288, and yj3=xj3+4. Then, by Fact 5, |δ(Cn)|=|δ(Cn)| and δ is (2,t)-solvable. Otherwise, xj15, let yj=xj+1=3, yj1=xj123, and yj2=xj2+1. By Fact 8, we only need to check m(δ,2,vj1). By (3.1) and (3.2), we can verify m(δ,2,vj1)t.

    Case 3. r2.

    If xj16, then xj22(11+26)=14 and m(δ,2,vj2)t+10+4(266/2)=t+5. Let yj=xj+2=4, yj1=xj1+2, yj2=xj286, and yj3=xj3+4. Then, by Fact 5, |δ(Cn)|=|δ(Cn)| and δ is (2,t)-solvable. Otherwise, xj17, let yj=xj+1=3, yj1=xj125, and yj2=xj2+1. By Fact 8, we only need to check m(δ,2,vj1). By (3.1) and (3.2), we can verify m(δ,2,vj1)t+1.

    Lemma 3.4. For t13 and n6, 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+14 for any k[0,n1].

    Proof. By Lemma 3.3, we assume that δ=x0,x1,,xn1 is an optimal (2,t)-solvable distribution of Cn such that δ(v)3 for each vertex v of Cn. Suppose that xj1=3 and xj=3 or xj=3 and xj+1=3 for some j[0,n1]. Then, let δ=y0,y1,,yn1 be defined as the description in Lemma 3.1. For the case that xj1=3 and xj=3, it suffices to show that δ(vk)4 for k=j or j1 and δ(vi)4 or δ(vi)=xi for i[0,n1]{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,n1]{k} and |δ(Cn)||δ(Cn)|.

    Case 1. xj1=3 and xj=3.

    By (3.4) and Fact 3, we have

    xj22(t+rxjxj1)=2(13+r33)14

    and

    m(δ,2,vj2)(xj4/2+xj3)/2+2(t+rxjxj1)+(xj1+xj/2)/2(3/2+3)/2+t+13+2r66+(3+3/2)/2t+5.

    Let yj=xj+2=5, yj1=xj1+2=5, yj2=xj286, and yj3=xj3+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+214 and m(δ,2,vj+2)t+5. Let yj=xj+2=5, yj+1=xj+1+2=5, yj+2=xj+286, and yj+3=xj+3+47. Then, by Fact 5, δ is a desired distribution. Otherwise, r1. Suppose that r=1. Then, by (3.5) and Fact 4, we have xj+212 and m(δ,2,vj+2)t+3. Let yj+1=xj+1+2=5, yj+2=xj+248, and yj+3=xj+3+25. Then, by Fact 7, δ is a desired distribution. Suppose that r2 and xj15. Then, by (3.4) and Fact 3, we have xj214 and m(δ,2,vj2)t+5. Let yj=xj+2=5, yj1=xj1+25, yj2=xj286, and yj3=xj3+47. Then, by Fact 5, δ is a desired distribution. Suppose that r2 and xj16. Then, by Fact 1, we have m(δ,2,vj1)t+1. If xj1 is odd, let yj=xj+1=4, yj1=xj115. We only need to check m(δ,2,vj2) and m(δ,2,vj3). By using (3.1), it is easy to see that m(δ,2,vj2)=m(δ,2,vj2) and m(δ,2,vj3)=m(δ,2,vj3). Otherwise, xj1 is even, let yj=xj+1=4, yj1=xj124, and yj2=xj2+14. We only need to check m(δ,2,vj1). By (3.1) and (3.2), we have

     m(δ,2,vj1)=(yj3/2+yj2)/2+yj1+(yj+yj+1/2)/2=(xj3/2+xj2+1)/2+xj12+(xj+1+xj+1/2)/2(3/2+1)/2+xj2/2+xj12+(4+xj+1/2)/21+(t+rxj)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 xj19, 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 vV(C6) and r=2. Since xj17, 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 vV(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+14 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 t13 and n6, 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,,xn1 is an optimal (2,t)-solvable distribution of Cn such that xi3 for all i[0,n1] and xk=3 implies xk+14 for any k[0,n1]. Suppose that xj=3 for some j[0,n1]. Then, let δ=y0,y1,,yn1 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,n1]{j} and |δ(Cn)||δ(Cn)|.

    By (3.4) and Fact 3, we have xj22(10+rxj1) and m(δ,2,vj2)t+9+2r(2xj1(xj1+1)/2).

    Case 1. r=0.

    If 4xj16 and xj+14, let yj=xj+1=4, yj2=xj222(t+rxjxj1)22(13+036)26, and yj3=xj3+1. Clearly, |δ(Cn)|=|δ(Cn)|. By (3.1), it is easy to see that m(δ,2,vi)=m(δ,2,vi) for i[0,n1]{j5,j4,j3,j2,j1,j,j+1,j+2}. For n9, vi{vj3,vj2,vj} for i{j7,j6,j5,j4,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{j5,j4,j3,j,j+1,j+2}. Hence, we only need to check m(δ,2,vj1) and m(δ,2,vj2). Note that xj34 or xj44. It follows that xj4/2+xj35. By (3.1)–(3.3), we have

    m(δ,2,vj1)=(xj3+1)/4+(xj22)/2+xj1+(xj+1+xj+1/2)/2(3+1)/4+(t+rxj)1+(4+4/2)/2=t,

    and

    m(δ,2,vj2)=(xj4/2+xj3+1)/2+xj22+(xj1+(xj+1)/2)/2(5+1)/2+2(t+rxjxj1)2+(xj1+4/2)/2t.

    For the case that 6n8, 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,n1].

    Similarly, if xj14 and 4xj+16, let yj=xj+1=4, yj+2=xj+226, and yj+3=xj+3+1. Then, |δ(Cn)|=|δ(Cn)| and δ is (2,t)-solvable.

    Now, we can assume that xj17 and xj+17. If xj1=xj+1=7, then xj1 and xj+1 are both odd. Let yj=xj+2=5, yj1=xj11=6 and yj+1=xj+11=6. Then, by Fact 9, we have |δ(Cn)|=|δ(Cn)| and δ is (2,t)-solvable.

    For the case xj17 and xj+18, let yj=xj+1=4, yj1=xj125, and yj2=xj2+1. Then, by Fact 8, we only need to check m(δ,2,vj1). By (3.1) and (3.2), we can verify m(δ,2,vj1)t.

    Similarly, for the case xj18 and xj+17, let yj=xj+1=4, yj+1=xj+125, and yj+2=xj+2+1. Then, |δ(Cn)|=|δ(Cn)| and δ is (2,t)-solvable.

    Case 2. r=1.

    If xj1=4, then xj22(10+14)=14 and m(δ,2,vj2)t+9+2(244/2)=t+5. Let yj=xj+2=5, yj+1=xj+1+2, yj2=xj286, and yj3=xj3+4. By Fact 5, |δ(Cn)|=|δ(Cn)| and δ is (2,t)-solvable. Otherwise, xj15. If xj1=5, then xj and xj1 are both odd. Let yj=xj+1=4 and yj1=xj11=4. By Fact 10, we only need to check m(δ,2,vj1). By (3.1) and (3.2), we can verify m(δ,2,vj1)t.

    Now, we can assume that xj16. Let yj=xj+1=4, yj1=xj124, and yj2=xj2+1. By Fact 8, we only need to check m(δ,2,vj1). By using (3.1) and (3.2), we can verify m(δ,2,vj1)t.

    Case 3. r2.

    If xj15, then xj22(10+25)=14 and m(δ,2,vj2)t+9+4(255/2)=t+5. Let yj=xj+2=5, yj1=xj1+2, yj2=xj286, and yj3=xj3+4. By Fact 5, we have |δ(Cn)|=|δ(Cn)| and δ is (2,t)-solvable. Otherwise, xj16. Let yj=xj+1=4, yj1=xj124, and yj2=xj2+1. By Fact 8, we only need to check m(δ,2,vj1). By using (3.1) and (3.2), we can verify m(δ,2,vj1)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 δ=xj3,xj2,xj1,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 xj1=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 xj16, δ=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 xj16, δ=4,13,4,4,4,12.

    Note that in all examples above δ(v)4 for each vV(C6) and δ is still (2,13)-solvable.

    By combining Propositions 3.1 and 3.2, we have the following.

    Theorem 3.1. For t13 and n6, π(2,t)(Cn)=π(2,t10)(Cn)+4n.

    By using Theorem 3.1 repeatedly (if necessary), we have the following.

    Corollary 3.1. For n6, π(2,10k+r)(Cn)=π(2,r)(Cn)+4kn, where k1 and 3r12.

    Let δ=x0,x1,x2,x3 be a (2,t)-solvable distribution of C4. Note that vi2=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|yi2+yi+2=xi+2}, (4.1)

    where mi=(yi2/2+xi1)/2+xi+(xi+1+yi+2/2)/2.

    This implies that if xi+21, then

    m(δ,2,vi)=xi12+xi+xi+12+xi+24.

    Otherwise,

    m(δ,2,vi)=xi+12(xi1+xi+1+xi+22).

    It follows that 94(x0+x1+x2+x3)4t or x0+x1+x2+x316t9. 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 k1. Thus, we have the following.

    Proposition 4.1. For k1, π(2,9k)(C4)=16k.

    Clearly, π(2,9k+r)(C4)π(2,9k)(C4)+π(2,r)(C4) for r1. Also, by Proposition 4.1, for k1, 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 k1, 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 k2, 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(k1)+10)(C4)16(k1)+π(2,10)(C4)=16(k1)+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 k0, then π(2,t)(C4)=16t/9.

    Proof. For k0 and r0, 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 k0, 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 k1, 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 k0. 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/4m(δ,2,v0)9k+5. This implies that r0+(r1+r3)/2+r2/45, equivalently, r0+r1+r2+r310r0+r2/2. Thus, 910r0+r2/2, and we have r01+r2/21+r0/2. Hence, r02. 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+xi1)/2+(xi+2+xi2)/4m(δ,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=(xi2/2+xi1)/2+xi+(xi+1+xi+2/2)/2,
    mi,2={mi,1,if xi21;(xi22)/2+xi12+xi+xi+1+(xi+2+1)/22,otherwise,

    and

    mi,2={mi,1,if xi+21;(xi2+1)/2+xi12+xi+xi+1+(xi+22)/22,otherwise.

    By Corollary 2.1, we have the following.

    Proposition 5.1. π(2,10k)(C5)=20k for k1.

    By Proposition 5.1, we have the following.

    Lemma 5.1. π(2,10k+r)(C5)20k+π(2,r)(C5) for k1 and r1.

    Now, we will give a lower bound for π(2,t)(C5) when tmod100.

    Lemma 5.2. π(2,t)(C5)2t+1 when tmod100.

    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+xi1)/2+(xi+2+xi2)/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 tmod50, 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 n4. 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 k0 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 k1. 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 t2 and tmod100.

    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 n4. In 2020, Shiue [13] studied distance 1-restricted pebbling in cycles, and he determined the exact value of π(1,t)(Cn) for all t1 and n3; see Theorem 2.1. For t=1, π(1,1)(Cn)=π(Cn)=2n3; see [2]. This implies that π(d,1)(Cn)=2n3 for all d1. 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, 1t12. 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 n3 and t1. Corollary 3.1 implies that the problem of determining the exact value of π(2,t)(Cn) for n6 and t1 can be reduced to the problem of determining the exact value of π(2,r)(Cn) for n6 and r[1,12]. By the discussion above, we know the exact value of π(2,t)(Cn) for n3 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 t1, see Theorem 2.1. Theorems 4.1 and 5.1 give the exact value of π(2,t)(Cn) for n=4,5 and t1. So, to completely determine the exact value of π(2,t)(Cn) for n3 and t1, it is left to solve the following problem.

    Problem 2. Determine the exact value of π(2,t)(Cn) for n6 and 3t12.

    Recently, we have shown that π(2,3)(Cn)=4n3 for n4, see [15]. By combining Corollary 3.1, we have π(2,10k+3)(Cn)=4n3+4kn for n6 and k0. 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
  • 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(464) PDF downloads(18) Cited by(0)

Other Articles By Authors

/

DownLoad:  Full-Size Img  PowerPoint
Return
Return

Catalog