# The Optimal Rubbling Number of Paths, Cycles, and Grids

Authors: Zheng-Jiang Xia; Zhen-Mu Hong
Journal: Complexity
 (2021)

---

## Abstract

A pebbling move on a graphG consists of the removal of two pebbles from one vertex and the placement of one pebble on an adjacent vertex. Rubbling is a version of pebbling where an additional move is allowed, which is also called the strict rubbling move. In this new move, one pebble each is removed from u and v adjacent to a vertex w, and one pebble is added on w. The rubbling number of a graph G is the smallest number m, such that one pebble can be moved to each vertex from every distribution with m pebbles. The optimal rubbling number of a graph G is the smallest number m, such that one pebble can be moved to each vertex from some distribution with m pebbles. In this paper, we give short proofs to determine the rubbling number of cycles and the optimal rubbling number of paths, cycles, and the grid P2×Pn; moreover, we give an upper bound of the optimal rubbling number of Pm×Pn.


---

## Body

## 1. Introduction

Pebbling in graphs was first introduced by Chung [1]. It has its origin in number theory and also can be viewed as a model for the transportation of resources, starting from a pebble distribution on the vertices of a connected graph.LetG be a simple connected graph; we use VG and EG to denote the vertex set and edge set of G, respectively. du,v is the distance of u and v, and we write u∼v if they are adjacent. Nv=u|u∼v is the neighbour of v, and dv=Nv is the degree of v. Let H be a subgraph of G, and we use dHv to denote the degree of v in H. A pebble distribution D on G is a function D:VG⟶N (N is the set of nonnegative integers), where Dv is the number of pebbles on v and D=∑v∈VDDv is the size of D.Apebbling move consists of the removal of two pebbles from a vertex and the placement of one pebble on an adjacent vertex. For two pebble distributions D and D′ of G, we say that D contains D′ if Dv≥D′v for all v∈VG; and D′ is reachable from D if we can obtain a distribution which contains D′ from D by pebbling moves. For a graph G and a vertex v, we call v a root (or target vertex) if the goal is to place pebbles on v. If t pebbles can be moved to v from D by a sequence of pebbling moves, then we say that D is t-foldv-solvable, and v is t-reachable from D. If D is t-fold v-solvable for every vertex v, we say that D is t-solvable. Let S be a subset of VG. If D is v-solvable for all v∈S, then we say DisS-solvable.Thet-pebbling number of a graphG, denoted by ftG, is the smallest number m, such that every distribution with size m is t-solvable. While t=1, we use fG instead of f1G, which is called the pebbling number of graph G. The optimal pebbling numberfoptG of a graph G is the minimum number m such that there exists a solvable distribution with size m.Rubbling is a version of pebbling where an additional move is allowed, which is also calledthe strict rubbling move. In this new move, one pebble each is removed from u and v adjacent to a vertex w, and one pebble is added on w. Thet-rubbling number of a graphG, denoted by ρtG, is the smallest number m, such that every distribution with size m is t-solvable by rubbling moves. Similarly, while t=1, we use ρG instead of ρ1G, which is called the rubbling number of graphG. The optimal rubbling numberρoptG of a graph G is the minimum number m such that there exists a solvable distribution with size m by rubbling moves.There are many papers about pebbling on graphs; one can view the survey paper [2] written by Hurlbert. Rubbling is a new parameter with few results. The basic theory about rubbling and optimal rubbling was developed by Belford and Sieben [3]; they determined the rubbling numbers of trees and cycles, the optimal rubbling numbers of paths and cycles, and so on. The rubbling numbers of complete m-ary trees are studied in [4], the rubbling numbers of caterpillars are given in [5], the optimal rubbling numbers of ladders, prisms, and Möbius ladders are determined in [6], and in [7], they give the bounds for the rubbling numbers of diameter 2 graphs.In this paper, we give some new proofs to determine the rubbling numbers of cycles and the optimal rubbling numbers of paths, cycles, ladders, prisms, and Möbius ladders. Also, we give an upper bound of the optimal rubbling number ofP3×Pn, from which we also get an upper bound of the optimal rubbling number of Pm×Pn.


## 2. Main Result

Assume thatv,w∈Nu. A pebbling move from v to u is the removal of two pebbles from v and addition of one pebble on u, denoted by v,v⟶u; a rubbling move from v,w to u is the removal of one pebble from v and one pebble from w and addition of one pebble on u, denoted by v,w⟶u.The following lemma holds clearly.Lemma 1.
(see [3]). 2dG≤ρG≤fG.Definition 1.
(see [3]). Given a multiset S of rubbling moves on G, the transition digraph TG,S is a directed multigraph whose vertex set is VG, and each move v,w⟶u in S isrepresented by two directed edges v,u and w,u. The transition digraph of a rubbling sequence S=S1,…,sn is TG,s=TG,S, where S=s1,…,sn is the multiset of moves in s.Lemma 2.
(see [3, 8], no-cycle lemma). Let S be a sequence of rubbling moves on G, reaching a distribution D. Then, there exists a sequence S∗ of rubbling moves, reaching a distribution D∗, such that(1)
On each vertexv, D∗v≥Dv.(2)
TG,S∗ does not contain any directed cycles.
A thread in a graph is a path containing vertices of degree 2. By Lemma2, we can get the following.Lemma 3.
(see [3]). Let P be a thread in G; if vertex x∉VP is t-reachable from the pebble distribution D by a sequence of rubbling moves, then x is t-reachable from a rubbling sequence in which there is no strict rubbling move of the form v,w⟶u for u∈VP.Definition 2.
(see [9]). For a given distribution D on VG, assume dv=2 and Dv≥3. A smoothing move from v changes D by removing two pebbles from v and adding one pebble on each neighbour of v.Lemma 4.
(see [9]). Let D be a distribution on a graph G with distinct vertices u and v, where dv=2, Dv≥3. If u is t-reachable under D, then u is t-reachable under the distribution D′ obtained by making a smoothing move from v.
A distribution issmooth, if it has at most two pebbles on every vertex with degree 2. A vertex v is unoccupied under D if Dv=0.Lemma 5.
(smoothing lemma, [9]). If G is a connected n-vertex graph, with n≥3, then G has a smooth optimal distribution with all leaves unoccupied.Lemma 6.
(see [9]). In a path with a smooth distribution D having at most two pebbles on each endpoint, let v be an unoccupied vertex. If v is an endpoint, then v is not 2-reachable under D. If v is an inner vertex, then no pebble can be moved out from v without using an edge in both directions.Definition 3.
(see [9]). A graph H is a quotient of a graph G if the vertices of H correspond to the sets in a partition of VG, and distinct vertices of H are adjacent if at least one edge of G has endpoints in the sets corresponding to both vertices of H. In other words, each set in the partition of VG collapses to a single vertex of H. If H is a quotient of G via the surjective map ϕ:VG⟶VH and D is a distribution on G, then the quotient distribution D∗ is the distribution on H defined by D∗u=∑v∈ϕ−1uDv.Lemma 7.
(collapsing lemma, [9]). Let H be a quotient of G and D∗ be the quotient distribution in H. Then, D is t-fold v-solvable by a sequence of pebbling moves ⇒D∗ is t-fold ϕv-solvable by a sequence of pebbling moves. In particular, foptG≥foptH.
Similarly, we can get the collapsing lemma on rubbling.Lemma 8.
LetH be a quotient of G and D∗ be the quotient distribution on H. Then, D is t-fold v-solvable by a sequence of rubbling moves ⇒D∗ is t-fold ϕv-solvable by a sequence of rubbling moves. In particular, ρoptG≥ρoptH.Proof.
The proof is similar to the proof of Lemma 7 in [9].


### 2.1. Rubbling and Optimal Rubbling in Paths and Cycles

Lemma 9.
(see [10, 11]). Thet-pebbling numbers of the cycles C2n+1 and C2n are(1)ftC2n+1=22n+13+t−12n+1,ftC2n=2nt.
In this section, we give short proofs about the rubbling number of cycles and the optimal rubbling numbers of paths and cycles, which are determined in [3].Theorem 1.
(see [3]). The rubbling numbers of cycles are(2)ρC2n=2n,ρC2n+1=7⋅2n−1−23+1.Proof.
For the even cycleC2n, by Lemma 1, we have 2n≤ρC2n≤fC2n=2n, over.
For the odd cycleC2n+1, assume the target vertex is v0 which is adjacent to v1 and v−1. Let D be a pebble distribution on C2n+1, and Dv0=0. We collapse the vertices v−1,v0,v1 into one vertex x to get a new graph C2n−1 and the quotient distribution D∗ on C2n−1, with D∗x=Dv−1+Dv0+Dv1 and D∗y=Dy for y≠x.
By Lemma3, we may assume that there is no strict rubbling move of the form v,w⟶u where u≠v0. So, one pebble can be moved to v0 from D on C2n+1 by a sequence of rubbling moves ⇔ two pebbles can be moved to x from D∗ on C2n−1 by a sequence of pebbling moves. Thus, ρC2n+1=f2C2n−1=2⌊2n/3⌋+2n−1+1 (the last equality holds from Lemma 9). A simple calculation can show that 2⌊2n/3⌋+2n−1+1=⌊7⋅2n−1−2/3⌋+1.Lemma 10.
(see [9]). The optimal pebbling numbers of paths and cycles are(3)foptPn=foptCn=2n3.
Moreover, we can get the following lemma.Lemma 11.
LetD be a pebble distribution with 2k pebbles on P3k=v1,…,v3k. If D is solvable by pebbling moves, then Dv3i+2=2 for 0≤i≤k−1, and Dv=0 otherwise.Proof.
We show it by induction onk; it holds for k=1.
We can move⌊Dv1/2⌋ pebbles from v1 to P3k−1=v2,…,v3k, so by induction, 2k−Dv1+⌊Dv1/2⌋≥foptP3k−1=2k, and thus Dv1=0. Similarly, Dv3k=0.
We make smoothing moves onP3k from D to obtain a smooth pebble distribution D∗.
SinceD=2k<n=3k, there exist many vertices unoccupied under D∗. Assume vi is a vertex unoccupied under D∗. Let L1=v1,…,vi and L2=vi+1,…,v3k. By Lemma 6, we cannot move two pebbles to vi using only one direction.
Ifvi is solvable by vi−1,vi−1⟶vi, then we can get that D∗|Li is Li-solvable, and thus D∗≥foptPi+foptP3k−i. Assume i=3j+r for 0≤r≤2. If r=0, then D∗≥2j+2k−j=2k. If r=1, then D∗≥2j+1+2k−j=2k+1, a contradiction to D=2k. If r=2, then D∗≥2j+2+2k−j−1+1=2k+1, a contradiction to D=2k, and thus i=3j.
By a similar argument, ifvi is solvable by vi+1,vi+1⟶vi, then we can get i=3j+1.
Thus, we can always partition the pathP3k into two paths L1=v1,…,v3j and L2=v3j+1,…,v3k, and D∗|Li is solvable in Li for i=1,2, respectively.
By induction, we know thatD∗v3i+2=2 for 0≤i≤k−1, and D∗v=0 otherwise.
Note that making a smooth move on the vertexv leaves at least one pebble on v, which means that if we can make a smooth move under D, then at least two adjacent vertices have pebbles under D∗, a contradiction to D∗v3i+2=2, and D∗v=0 otherwise. So, D=D∗, which completes the proof.
In [3], Belford and Sieben determined the optimal rubbling number of paths and cycles; here we give a short proof.Theorem 2.
(see [3]). The optimal rubbling number of path is ρoptPn=⌈n+1/2⌉, and the optimal rubbling number of cycle is ρoptCn=⌈n/2⌉ for n≥3.Proof.
Upper Bound. For Pn=v1,v2,…,vn, let D be a distribution so that Dvi=1 for i is odd or i=n, and Dvi=0 otherwise; clearly D is solvable, and D=⌈n+1/2⌉. For Cn=v1,v2,…,vn, let D be a distribution so that Dvi=1 for i is odd, and Dvi=0 otherwise; clearly D is solvable, and D=⌈n/2⌉.Lower Bound. First we show it for the path Pn. We use induction on n. By a simple calculation, one can show that it holds for n≤3.
Ifn>3, assume it holds for Pj for all j<n. From the upper bound and Lemma 10, we know that ρoptPn<foptPn. Let D be a solvable pebble distribution with ρoptPn pebbles on Pn; there must exist a vertex vi, which is reachable only by the strict rubbling move vi−1,vi+1⟶vi. Let P1=v1,…,vi−1, P2=vi+1,…,vn be two subpaths of Pn; then, by Lemma 3, we do not need the strict rubbling move vi−1,vi+1⟶vi to solve the vertices in Pi for i=1,2. That means D|Pi is v-solvable for all v∈Pi (i=1,2), so D|Pi≥ρoptPi for i=1,2. So, D=D|P1+D|P2≥⌈i/2⌉+⌈n−i+1/2⌉≥⌈n+1/2⌉.
Now we show it for the cycleCn; similarly, by a simple calculation, one can show that it holds for n=3.
Ifn>3, from the upper bound and Lemma 10, we know that ρoptCn<foptCn. Thus, let D be an optimal pebble distribution with ρoptCn pebbles on Cn, and there must exist a vertex vi, which is reachable only by a strict rubbling move vi−1,vi+1⟶vi. Then, by Lemma 3, we do not need the strict rubbling move vi−1,vi+1⟶vi to solve the vertices in Cn\vi, and thus D is solvable on Pn−1=Cn\vi, so D≥ρoptPn−1=⌈n/2⌉, which completes the proof.


## 2.1. Rubbling and Optimal Rubbling in Paths and Cycles

Lemma 9.
(see [10, 11]). Thet-pebbling numbers of the cycles C2n+1 and C2n are(1)ftC2n+1=22n+13+t−12n+1,ftC2n=2nt.
In this section, we give short proofs about the rubbling number of cycles and the optimal rubbling numbers of paths and cycles, which are determined in [3].Theorem 1.
(see [3]). The rubbling numbers of cycles are(2)ρC2n=2n,ρC2n+1=7⋅2n−1−23+1.Proof.
For the even cycleC2n, by Lemma 1, we have 2n≤ρC2n≤fC2n=2n, over.
For the odd cycleC2n+1, assume the target vertex is v0 which is adjacent to v1 and v−1. Let D be a pebble distribution on C2n+1, and Dv0=0. We collapse the vertices v−1,v0,v1 into one vertex x to get a new graph C2n−1 and the quotient distribution D∗ on C2n−1, with D∗x=Dv−1+Dv0+Dv1 and D∗y=Dy for y≠x.
By Lemma3, we may assume that there is no strict rubbling move of the form v,w⟶u where u≠v0. So, one pebble can be moved to v0 from D on C2n+1 by a sequence of rubbling moves ⇔ two pebbles can be moved to x from D∗ on C2n−1 by a sequence of pebbling moves. Thus, ρC2n+1=f2C2n−1=2⌊2n/3⌋+2n−1+1 (the last equality holds from Lemma 9). A simple calculation can show that 2⌊2n/3⌋+2n−1+1=⌊7⋅2n−1−2/3⌋+1.Lemma 10.
(see [9]). The optimal pebbling numbers of paths and cycles are(3)foptPn=foptCn=2n3.
Moreover, we can get the following lemma.Lemma 11.
LetD be a pebble distribution with 2k pebbles on P3k=v1,…,v3k. If D is solvable by pebbling moves, then Dv3i+2=2 for 0≤i≤k−1, and Dv=0 otherwise.Proof.
We show it by induction onk; it holds for k=1.
We can move⌊Dv1/2⌋ pebbles from v1 to P3k−1=v2,…,v3k, so by induction, 2k−Dv1+⌊Dv1/2⌋≥foptP3k−1=2k, and thus Dv1=0. Similarly, Dv3k=0.
We make smoothing moves onP3k from D to obtain a smooth pebble distribution D∗.
SinceD=2k<n=3k, there exist many vertices unoccupied under D∗. Assume vi is a vertex unoccupied under D∗. Let L1=v1,…,vi and L2=vi+1,…,v3k. By Lemma 6, we cannot move two pebbles to vi using only one direction.
Ifvi is solvable by vi−1,vi−1⟶vi, then we can get that D∗|Li is Li-solvable, and thus D∗≥foptPi+foptP3k−i. Assume i=3j+r for 0≤r≤2. If r=0, then D∗≥2j+2k−j=2k. If r=1, then D∗≥2j+1+2k−j=2k+1, a contradiction to D=2k. If r=2, then D∗≥2j+2+2k−j−1+1=2k+1, a contradiction to D=2k, and thus i=3j.
By a similar argument, ifvi is solvable by vi+1,vi+1⟶vi, then we can get i=3j+1.
Thus, we can always partition the pathP3k into two paths L1=v1,…,v3j and L2=v3j+1,…,v3k, and D∗|Li is solvable in Li for i=1,2, respectively.
By induction, we know thatD∗v3i+2=2 for 0≤i≤k−1, and D∗v=0 otherwise.
Note that making a smooth move on the vertexv leaves at least one pebble on v, which means that if we can make a smooth move under D, then at least two adjacent vertices have pebbles under D∗, a contradiction to D∗v3i+2=2, and D∗v=0 otherwise. So, D=D∗, which completes the proof.
In [3], Belford and Sieben determined the optimal rubbling number of paths and cycles; here we give a short proof.Theorem 2.
(see [3]). The optimal rubbling number of path is ρoptPn=⌈n+1/2⌉, and the optimal rubbling number of cycle is ρoptCn=⌈n/2⌉ for n≥3.Proof.
Upper Bound. For Pn=v1,v2,…,vn, let D be a distribution so that Dvi=1 for i is odd or i=n, and Dvi=0 otherwise; clearly D is solvable, and D=⌈n+1/2⌉. For Cn=v1,v2,…,vn, let D be a distribution so that Dvi=1 for i is odd, and Dvi=0 otherwise; clearly D is solvable, and D=⌈n/2⌉.Lower Bound. First we show it for the path Pn. We use induction on n. By a simple calculation, one can show that it holds for n≤3.
Ifn>3, assume it holds for Pj for all j<n. From the upper bound and Lemma 10, we know that ρoptPn<foptPn. Let D be a solvable pebble distribution with ρoptPn pebbles on Pn; there must exist a vertex vi, which is reachable only by the strict rubbling move vi−1,vi+1⟶vi. Let P1=v1,…,vi−1, P2=vi+1,…,vn be two subpaths of Pn; then, by Lemma 3, we do not need the strict rubbling move vi−1,vi+1⟶vi to solve the vertices in Pi for i=1,2. That means D|Pi is v-solvable for all v∈Pi (i=1,2), so D|Pi≥ρoptPi for i=1,2. So, D=D|P1+D|P2≥⌈i/2⌉+⌈n−i+1/2⌉≥⌈n+1/2⌉.
Now we show it for the cycleCn; similarly, by a simple calculation, one can show that it holds for n=3.
Ifn>3, from the upper bound and Lemma 10, we know that ρoptCn<foptCn. Thus, let D be an optimal pebble distribution with ρoptCn pebbles on Cn, and there must exist a vertex vi, which is reachable only by a strict rubbling move vi−1,vi+1⟶vi. Then, by Lemma 3, we do not need the strict rubbling move vi−1,vi+1⟶vi to solve the vertices in Cn\vi, and thus D is solvable on Pn−1=Cn\vi, so D≥ρoptPn−1=⌈n/2⌉, which completes the proof.


## 3. Optimal Rubbling in Ladders and Prisms

LetG and H be simple connected graphs; we define the Cartesian product G×H to be the graph with vertex set VG×H and edge set the union of av,bv|a,b∈EG,v∈EH and ux,uy|u∈VG,x,y∈EH. We call Pn×P2 a ladder and Cn×P2 a prism. It is clear that a prism can be obtained from a ladder by joining the 4 endvertices by two edges to form two vertex-disjoint Cn subgraphs. If the four endvertices are joined by two new edges in a switched way to get a C2n subgraph, then a Möbius ladderMn is obtained.The optimal rubbling numbers of ladders, prisms, and Möbius ladders are determined in [6]; here we give new proofs of these results.LetPn=v1,v2,…,vn and P2=xy. The vertices of Pn×P2 are denoted by vix and viy for 1≤i≤n. Let Hn=Pn+1×P2\vn+1x. Then, we have the following.Theorem 3.
Letn=3k+r, 0≤r≤2; the optimal rubbling number of the ladder Pn×P2 [6] is(4)ρoptP3k+r×P2=2k+1ifr=02k+2ifr=12k+2ifr=2=2n+13.
The optimal rubbling number ofHn is(5)ρHn=ρPn−1×P2+1.Proof.
Upper Bound. Let D be a distribution on Pn×P2 or Hn×P2.Ifr=0, then Dvix=1 for i≡1mod3; Dviy=1 for i≡2mod3 and i≠n−1; Dvny=2 and Dv=0 otherwise.Ifr=1, then Dvix=1 for i≡1mod3 and i≠n; Dviy=1 for i≡2mod3; Dvny=2 and Dv=0 otherwise.Ifr=2, for Pn×P2, then Dvix=1 for i≡1mod3; Dviy=1 for i≡2mod3; Dv=0 otherwise. For Hn, we add one more pebble on vn+1y.One can check thatD is solvable for all Pn×P2 and Hn.Lower Bound. Note that the diameter of Pn×P2 is n, and let Ri be the set of vertices with distance i from v1x (1≤i≤n), R0=v1x; if we collapse Ri into one vertex ri for 0≤i≤n, then we can get a path P˜n+1=r0,…,rn (see Figure 1). By Lemma 10, the optimal pebbling number of P˜n+1 is foptP˜n+1=⌈2n+1/3⌉. By Lemma 8, ρoptHn≥ρoptPn×P2. So, we only need to show that ρoptPn×P2≥foptP˜n+1 and ρoptH3k+2≥2k+3.
We use induction onn for both Hn (only need to show while n≡2mod3) and Pn×P2; it holds for n≤2 clearly.
Assume it holds forh<n.Figure 1
Pn×P2.Case 1.
First we considerPn×P2, and let D be a solvable distribution on Pn×P2 with ρoptPn×P2 pebbles; then, we collapse Ri into one vertex ri for 0≤i≤n to get a path P˜n+1 with length n and the quotient distribution D∗ on P˜n+1. By Lemma 8, D∗ is solvable in P˜n+1. We will show that ρoptPn×P2≥foptP˜n+1.
AssumeρoptPn×P2<foptP˜n+1; since D∗ is a solvable distribution on P˜n+1, there must exist some ri of P˜n+1 which can be reachable only by the strict rubbling move ri−1,ri+1⟶ri. By Lemmas 3 and 8, we claim the following.Claim 1.
At most one pebble can be moved tori−1 (ri+1) under D∗ and at most one pebble can be moved to Ri−1 (Ri+1) under D.
LetQ1=r0,…,ri−1, Q2=ri+1,…,rn be two subpaths of P˜n+1 and W1 and W2 be the subgraphs of Pn×P2 which induce Q1 and Q2, respectively.
Now we will show thatD|Wj≥ρoptWj for j=1,2. Note that W1 is isomorphic to Hi−1 and W2 is isomorphic to Hn−i−1.
Notation. For simplicity, a rubbling move Ri−1,Ri+1⟶Ri in Pn×P2 means a rubbling move v,u⟶w for some v∈Ri−1,u∈Ri+1 and w∈Ri. And similarly, we can define a rubbling move Ri−1,u⟶Ri and so on.
IfD|Wj is Wj-solvable, then D|Wj≥ρoptWj, and we are done. Assume D|Wj is not Wj-solvable for some j; without loss of generality, assume D|W2 is not W2-solvable. If i=n−1, then W2=vny, and the strict rubbling move rn−2,rn⟶rn−1 means that D∗rn≥1, which means Dvny≥1, a contradiction to D|W2, is not W2-solvable. Thus, i<n−1.
SinceD|W2 is not W2-solvable, to solve some vertex of W2, we must use the pebbles on W1. Note that we can move at most one pebble on Ri−1 from D|W1, and we must use the strict rubbling move Ri−1,Ri+1⟶Ri under D.
Consider the vertexviy∈Ri, Nviy=Ri−1∪vi+1y. Since viy is reachable from D, we can move two pebbles to Nviy. From Claim 1, we can get that we can move one pebble to Ri−1 and one pebble to vi+1y at the same time. Thus, vi+1y is reachable under D|W2.Subcase 1.
Dvi+1y=0. Then, we can move two pebbles on vi+2y under D|W2(for vi+1y is just adjacent to one vertex vi+2y of W2). So, vi+2x is reachable under D|W2, too.
Note that the pebble moved onRi cost at least two pebbles on vi+2y and we can move at most one pebble to Ri+1 by using this pebble. We can use Ri+2,Ri+2⟶Ri+1 instead of the rubbling sequence which contains the strict rubbling move Ri−1,Ri+1⟶Ri and aim to move one pebble to Ri+1, so D|W2 is W2-solvable.Subcase 2.
Dvi+1y=1. Then, at most one pebble can be moved to Ri+2 under D|W2; otherwise, one more pebble can be moved from ri+2 to ri+1, and then there are two pebbles on ri+1, and one pebble can be moved to ri under D∗, a contradiction.
By a similar argument, we can show there exists some vertex inW2 so that we must use the strict rubbling move Ri−1,vi+1y⟶vi+1x to solve this vertex, and the next rubbling move must be Ri+2,vi+1x⟶vi+2x. Since at most one pebble can be moved to Ri+2 under D|W2, exactly one pebble can be moved to Ri+2 under D|W2.(a)
The vertex ofRi+2 used in Ri+2,vi+1x⟶vi+2x is vi+3x; then, if it continues, the rubbling move must be vi+3y,vi+2x⟶vi+2y, but then we can use vi+1y,vi+3y⟶vi+2y instead, and thus we must use the strict rubbling move Ri−1,Ri+1⟶Ri to solve at most one vertex vi+2x. Let Pleft=vi+3,…,vn; then, the vertices of Pleft×P2 are reachable without the strict rubbling moves and the pebble on vi+1y. So, D|W2−1≥ρoptPleft×P2, and by induction, ρoptPleft×P2+1=ρoptW2, over.(b)
The vertex ofRi+2 used in Ri+2,vi+1x⟶vi+2x is vi+2y; since at most one pebble can be moved to Ri+2, we may assume Dvi+2y=1 (if not, then we can move two pebbles to vi+3y, and then one pebble can be moved to vi+3x; this is just (a)). Thus, we use one pebble each on Ri−1, vi+1y, and vi+2y to move one pebble to vi+2x. Then, we rearrange the distribution on Pn×P2 as follows: remove the pebble on vi+1y, and add it on vi+2y; one can view that we can still solve Ri and Ri+1. Thus, in the new distribution, we do not need the strict rubbling move Ri−1,Ri+1⟶Ri to solve W2, so D|W2≥ρoptW2.
Thus,D=D|W1+D|W2≥ρoptW1+ρoptW2=ρoptHi−1+ρoptHn−i−1.
Assume thatn=3k+r and i=3j+s for 0≤r,s≤2; by induction, we can get Table 1, where the lower bound is given by ρoptHi−1+ρoptHn−i−1.
From Table1, we can find D≥foptLn+1, which is a contradiction to the assumption that ρoptPn×P2<foptLn+1, and we are done.Table 1
Bounds on optimal rubbling ofPn×P2.
r,s0,00,10,21,01,11,22,02,12,2ρoptHi−12j+12j+12j+22j+12j+12j+22j+12j+12j+2ρoptHn−i−12(k−j)+12(k−j)2(k−j)−12(k−j)+12(k−j)+12(k−j)2(k−j)+22(k−j)+12(k−j)+1Lower bound2k+22k+12k+12k+22k+22k+22k+32k+22k+3foptLn+12k+12k+12k+12k+22k+22k+22k+22k+22k+2Case 2.
Now we considerH3k+2. Note that the diameter of H3k+2 is 3k+3. Let Ri be the vertices set vix,viy for 1≤i≤3k+2, and R3k+3=v3k+3y. If we collapse Ri into one vertex ri for 1≤i≤3k+3, then we can get a path P˜3k+3=r1…r3k+3 (see Figure 2). By Lemma 10, the optimal pebbling number of P˜3k+3 is foptP˜3k+3=⌈23k+3/3⌉=2k+2. So, we only need to show that ρoptH3k+2>foptP˜3k+3.
LetD be a solvable distribution with ρoptH3k+2 pebbles on H3k+2 and D∗ be the quotient distribution on P˜3k+3. So, D∗ is solvable on P˜3k+3 by Lemma 8.Figure 2
H3k+2.Subcase 3.
IfρoptH3k+2<foptP˜3k+3, since D∗ is a solvable distribution on P˜3k+3, there must exist some vertex ri of P˜3k+3 which can be reachable Assume that W1 and W2 be two disjoint subgraphs of H3k+2 which induce Q1=r1,…,ri−1 and Q2=ri+1,…,r3k+3, respectively.
We will show thatD|Wj is Wj-solvable for j=1,2. Otherwise, we must use the strict rubbling move Ri−1,Ri+1⟶Ri under D to solve one vertex of Wi; this move must be one of vi−1x,vi+1x⟶vix and vi−1y,vi+1y⟶viy. Without loss of generality, assume the rubbling move is vi−1x,vi+1x⟶vix; then, by Lemma 2, the target vertex of the next rubbling move using the pebble on vix cannot be vi+1x or vi−1x; if the target vertex is viy, we need one more pebble on Ri−1 or Ri+1, a contradiction to the condition that ri can be reachable only by the strict rubbling move ri−1,ri+1⟶ri.
So,D|Wi is Wi-solvable, and thus D|Wi≥ρoptWi for i=1,2. Note that W1 is isomorphic to Pi−1×P2 and W2 is isomorphic to H3k+2−i. Thus, D≥ρoptPi−1×P2+ρoptH3k+2−i. Assume that i=3j+s for 0≤s≤2; by induction, we can get Table 2, where the lower bound is given by ρoptPi−1×P2+ρoptH3k+2−i.
From Table2, we can find ρoptH3k+2>foptL3k+3, a contradiction to the assumption ρoptH3k+2<foptL3k+3, over.Table 2
Bounds on optimal rubbling ofH3k+2.
s012ρoptPi−1×P22j+12j+22j+2ρoptH3k+2−i2(k−j)+22(k−j)+12(k−j)+1Lower bound2k+32k+32k+3foptL3k+32k+22k+22k+2Subcase 4.
IfρoptH3k+2=foptL3k+3=2k+2, then D∗ is solvable on P˜3k+3. If there exists a vertex ri which is reachable only by a strict rubbling move under D∗, then we can get a contradiction by a similar argument of Subcase 3.
So, we only need to consider the case that all vertices ofP˜3k+3 are reachable by only pebbling moves. By Lemma 11, we have D∗R3i+2=2 for 0≤i≤k, and D∗v=0 otherwise. Thus, at least one of v1x,v1y is not solvable under D, which completes the proof.Theorem 4.
(see [6]). The optimal rubbling number of prism Cn×P2 is(6)ρoptC3k+r×P2=2k,ifr=0,2k+1,ifr=12k+2,ifr=2,=2n3,except ρoptC3×P2=3.Proof.
It holds forn=3; we only need to show ρoptCn×P2=ρoptPn−1×P2 for n≥4.Upper Bound. Pn−1×P2 can be viewed as a subgraph of Cn×P2; it is clear that a solvable distribution with ρoptPn−1×P2 pebbles given in the proof of Theorem 3 is solvable on Cn×P2 for n≥4, and we are done.Lower Bound. Let Cn=v1,…,vn, P2=xy. Assume D is a solvable distribution with ρoptCn×P2 pebbles, and we collapse each set vix,viy into one vertex Ri (see Figure 3); then, we get a cycle Cn=R1,…,Rn and the quotient distribution D∗. By Lemma 8, D∗ is solvable on Cn. By Lemma 10, foptCn=⌈2n/3⌉, and we only need to show ρoptCn×P2=foptCn.
AssumeρoptCn×P2<foptCn; then, there must exist a vertex Ri which is reachable under D∗ only by the strict rubbling move Ri−1,Ri+1⟶Ri. By a similar argument of Case 3 in the proof of Theorem 3, if we remove vix,viy from Cn×P2 (which is just isomorphic to Pn−1×P2), then D is still solvable. So, D≥ρoptPn−1×P2=⌈2n/3⌉, which is a contradiction to the assumption ρoptCn×P2<foptCn, and we are done.Figure 3
Cn×P2.Theorem 5.
(see [6]). The optimal rubbling number of the Möbius ladder Mn is(7)ρoptMn=ρoptCn×P2.Proof.
The proof is similar to the proof of prisms.


## 4. Bounds on the Optimal Rubbling ofPm×Pn

In [12], the optimal pebbling number of P3×Pn is determined.Theorem 6.
(see [12]). The optimal pebbling number of P3×Pn is n+1.
In [13], the lower bound of the optimal pebbling number of Pm×Pn is given.Theorem 7.
(see [13]). The optimal pebbling number of Pm×Pn is no less than 2/13mn when m,n≥5.
Here we give an upper bound of the optimal rubbling number ofPm×Pn by giving a solvable distribution on Pm×Pn.Theorem 8.
ρoptP3×Pn≤⌈5n+1/6⌉+1.Proof.
We give a solvable distributionDn on P3×Pn with exactly ⌈5n+1/6⌉+1 pebbles. While n≤7, the solvable distribution Dn is given in Figure 4.
Whilen>7, assume n≡rmod6 for 0≤r≤5. Then, the solvable distribution Dn on P3×Pn can be obtained from Dn−6 on P3×Pn−6 while r≠1 by placing five more pebbles on P3×P6 which is added on the left side of P3×Pn−6 (see Figure 5(a)). So, Dn=Dn−6+5 for n≡rmod6 with r≠q1.
Assumen>7 and n≡1mod6. Then, the solvable distribution Dn on P3×Pn can be obtained from Dn−5 on P3×Pn−5 by placing four more pebbles on P3×P5 which is added on the left side of P3×Pn−5(see Figure 5(b)). So, Dn=Dn−5+4 for n≡1mod6.
By a simple calculation, we haveDn=⌈5n+1/6⌉+1, and we are done.
One can check that the equality holds forn≤7, and here we give a conjecture.Figure 4
A solvable distributionDn on P3×Pn for n≤7.
(a)(b)(c)(d)(e)(f)(g)Figure 5
A solvable distributionDn from Dn−6 or Dn−5. (a) Dn from Dn−6. (b) Dn from Dn−5.
(a)(b)Conjecture 1.
ρoptP3×Pn=⌈5n+1/6⌉+1.
Now we can get a bound of the optimal rubbling number ofPm×Pn. We give a partition of Pm, for example, m=x+1+y; then, we can get three disjoint subgraphs of Pm×Pn called H1=Px×Pn, H2=P1×Pn and H3=Py×Pn, and then we put some pebbles on H1 and H3, so that the pebbles on Hi can solve Hi for i=1,3. Clearly, this is a solvable distribution of Pm×Pn. Thus, we have the following.Theorem 9.
ρoptP4×Pn≤ρoptPn+ρoptP2×Pn, ρoptP5×Pn≤ρoptP2×Pn+ρoptP2×Pn.Theorem 10.
Ifm=4k+r≥6, ρoptP4k×Pn≤k−1ρoptP3×Pn+ρoptP2×Pn+ρoptPn, ρoptP4k+1×Pn≤k−1ρoptP3×Pn+2ρoptP2×Pn, ρoptP4k+2×Pn≤kρoptP3×Pn+ρoptP2×Pn, ρoptP4k+3×Pn≤k+1ρoptP3×Pn.Proof.
Ifm=4k, then m=3+1+3+1+⋯+3+1+2+1+1 which gives a partition of Pm=P3+P1+P3+P1+⋯+P3+P1+P2+P1+P1. We put the pebbles on Pi×Pn except the inner subpaths P1×Pn, so that the pebbles on each Pi×Pn can solve themselves, and thus we need k−1ρoptP3×Pn+ρoptP2×Pn+ρoptPn pebbles, which is a solvable distribution. Similarly, we can get the other inequalities, which completes the proof.Corollary 1.
If6≤m≤n, then ρoptPm×Pn≤5/24mn+1/3n+1/2m+1/2.Proof.
From Theorems2, 3, 8, and 10, we can get the result by a simple calculation.



---

*Source: 5545080-2021-07-05.xml*