# The 2-Pebbling Property of the Middle Graph of Fan Graphs

Authors: Yongsheng Ye; Fang Liu; Caixia Shi
Journal: Journal of Applied Mathematics
 (2014)

---

## Abstract

A pebbling move on a graphG consists of taking two pebbles off one vertex and placing one pebble on an adjacent vertex. The pebbling number of a connected graph G, denoted by f(G), is the least n such that any distribution of n pebbles on G allows one pebble to be moved to any specified but arbitrary vertex by a sequence of pebbling moves. This paper determines the pebbling numbers and the 2-pebbling property of the middle graph of fan graphs.


---

## Body

## 1. Introduction

Pebbling on graphs was first introduced by Chung [1]. Consider a connected graph with a fixed number of pebbles distributed on its vertices. A pebbling move consists of the removal of two pebbles from a vertex and the placement of one of those pebbles on an adjacent vertex. The pebbling number of a vertex v in a graph G is the smallest number f(G,v) with the property that from every placement of f(G,v) pebbles on G, it is possible to move a pebble to v by a sequence of pebbling moves. The pebbling number of a graph G, denoted by f(G), is the maximum of f(G,v) over all the vertices of G.In a graphG, if each vertex (except v) has at most one pebble, then no pebble can be moved to v. Also, if u is of distance d from v and at most 2d-1 pebbles are placed on u (and none elsewhere), then no pebble can be moved from u to v. So it is clear that f(G)≥max⁡{|V(G)|,2D}, where |V(G)| is the number of vertices of G and D is the diameter of G.Throughout this paper, letG be a simple connected graph with vertex set V(G) and edge set E(G). For a distribution of pebbles on G, denote by p(H) and p(v) the number of pebbles on a subgraph H of G and the number of pebbles on a vertex v of G, respectively. In addition, denote by p~(H) and p~(v) the number of pebbles on H and the number of pebbles on v after a specified sequence of pebbling moves, respectively. For uv∈E(G), u→mv refers to taking 2m pebbles off u and placing m pebbles on v. Denote by 〈v1,v2,…,vn〉 the path with vertices v1,v2,…,vn in order.We now introduce some definitions and give some lemmas, which will be used in subsequent proofs.Definition 1.
A fan graph, denoted byFn, is a path Pn-1 plus an extra vertex v0 connected to all vertices of the path Pn-1, where Pn-1=〈v1,v2,…,vn-1〉.Definition 2.
The middle graphM(G) of a graph G is the graph obtained from G by inserting a new vertex into every edge of G and by joining by edges those pairs of these new vertices which lie on adjacent edges of G.Now one creates the middle graph ofFn. Edges v1v2,v2v3,…,v(n-2)(n-1) of Fn are the inserted new vertices u12,u23,…,u(n-2)(n-1) in the sequence, and edges v0v1,v0v2,…,v0vn-1 of Fn are the inserted new vertices u01,u02,…,u0(n-1), respectively. By joining by edges those pairs of these inserted vertices which lie on adjacent edges of Fn, this obtains the middle graph of Fn (see Figure 1).Figure 1
M
(
F
4
).Definition 3.
A transmitting subgraph is a path〈v0,v1,…,vk〉 such that there are at least two pebbles on v0, and after a sequence of pebbling moves, one can transmit a pebble from v0 to vk.Lemma 4 (see [2]).
LetPk+1=〈v0,v1,…,vk〉. If
(1)p(v0)+2p(v1)+⋯+2ip(vi)+⋯+2k-1p(vk-1)≥2k,
then Pk+1 is a transmitting subgraph.Definition 5.
Thet-pebbling number, ft(G), of a connected graph, G, is the smallest positive integer such that from every placement of ft(G) pebbles, t pebbles can be moved to a specified target vertex by a sequence of pebbling moves.Lemma 6 (see [3]).
IfKn is the complete graph with n  (n≥2) vertices, then ft(Kn)=2t+n-2.Lemma 7 (see [4]).
Considerf(M(Pn))=2n+n-2.Chung found the pebbling numbers of then-cube Qn, the complete graph Kn, and the path Pn (see [1]). The pebbling number of Cn was determined in [5]. In [6, 7], Ye et al. gave the number of squares of cycles. Feng and Kim proved that f(Fn)=n and f(Wn)=n (see [8]). Liu et al. determined the pebbling numbers of middle graphs of Pn, Kn, and K1,n-1 (see [4]). In [9], Ye et al. proved that f(M(C2n))=2n+1+2n-2(n≥2) and f(M(C2n+1))=⌊2n+3/3⌋+2n, where M(Cn) denotes the middle graph of Cn. Motivated by these works, we will determine the value of the pebbling number and the 2-property of middle graphs of Fn.


## 2. Pebbling Numbers ofM(Fn)

In this section, we study the pebbling number ofM(Fn). Let S={v0,u01,u02,…,u0(n-1)}, and let A={v1,u12,v2,u23,…,vn-1}. Obviously, the subgraph induced by S is a complete graph with n vertices. For n=3, M(F3)≅M(C3). Hence we have the following theorem.Theorem 8 (see [9]).
Considerf(M(F3))=7.Lemma 9.
Letf(M(Fn-1))=p. If p+3 pebbles are placed on M(Fn), then one pebble can be moved to any specified vertex of S by a sequence of pebbling moves.Proof.
Letv be our target vertex, and let p(v)=0, where v∈S. We may assume that v≠u01 (after relabeling if necessary). Let B={v1,u12,u01}. If p(B)≥5, then p~(u01)≥2 by Lemma 6, and we can move one pebble to v. If p(B)=4, then B→1u02. We delete v1,u01,andu12 to obtain the subgraph M(Fn-1) with p pebbles, thus we can move one pebble to v. If p(B)≤3, then we delete v1,u01,andu12 to obtain the subgraph M(Fn-1) with at least p pebbles and we are done.Theorem 10.
Considerf(M(F4))=11.Proof.
We place 7 pebbles onv3 and one pebble on each vertex of the set {v0,u02,v2}, other vertices have no pebble, then no pebble can be moved to v1. So p(M(F4))≥11. We now place 11 pebbles on M(F4). We assume that v is our target vertex and p(v)=0. Recall S={v0,u01,u02,u03} and A={v1,u12,v2,u23,v3}.(1)
Considerv∈S. By Theorem 8 and Lemma 9, we can move one pebble to v.(2)
Considerv=v1 (or v=v3). Let A1=A-{v1}, let A2={u12,v2}, and let A3=A1-A2. If p(S)=t, then p(A1)=11-t. Thus we can move at least ⌊(8-t)/2⌋ pebbles from A1 to S so that p~(S)=⌊(8+t)/2⌋≥6 for t≥4. By Lemma 6, p~(u01)=2 and we can move one pebble to v1. If t≤2, then p(A)≥9. By Lemma 7, we can move one pebble to v1. If t=3, then at least one of u01 and u03 can obtain one pebble from every placement of 3 pebbles on S by a sequence of pebbling moves. If p(A3)≥7, then A3→3u03. So 〈u03,u01,v1〉 is a transmitting subgraph. If 4≤p(A3)≤6, then 2≤p(A2)≤4. By Lemma 6, p~(u23)≥2 and p~(u12)≥1. So 〈u23,u12,v1〉 is a transmitting subgraph. If p(A3)≤3, then p(A2)≥5. So 〈v2,u12,v1〉 is a transmitting subgraph.(3)
Considerv=v2. If p(S)≥4 or p(S)≤2, then we are done with (2). If p(S)=3, then p(v1)+p(u12)≥4 or p(u23)+p(v3)≥4. So 〈v1,u12,v2〉 or 〈v3,u23,v2〉 is a transmitting subgraph.(4)
Considerv=u12 (or v=u23). If p(S)≥4 or p(S)≤2, then we are done with (2). If p(S)=3, then p(v1)+p(v2)+p(u23)+p(v3)=8. Obviously, we are done if p(v1)≥2 or p(v2)≥2. Next suppose that p(v1)≤1 and p(v2)≤1. Thus p(u23)+p(v3)≥6. So 〈v3,u23,u12〉 is a transmitting subgraph.Theorem 11.
Considerf(M(Fn))=3n-1(n≥4).Proof.
We place 7 pebbles onvn-1 and one pebble on each vertex of M(Fn) except v1,u01,u12,u(n-2)(n-1),u0(n-1), and vn-1. In this configuration of pebbles, we cannot move one pebble to v1. So f(M(Fn))≥3n-1. Next, let us use induction on n to show that f(M(Fn))=3n-1. For n=4, our theorem is true by Theorem 10. Suppose that f(M(Fk))=3k-1 if k<n. Now 3n-1 pebbles are placed arbitrarily on the vertices of M(Fn). Suppose that v is our target vertex and p(v)=0.
(1) Considerv∈S. By induction and Theorem 8, we can move one pebble to v.
(2) Considerv=v1 (or v=vn-1). Obviously, p(u01)≤1. Otherwise, p(u01)>1. v1 can obtain one pebble. Let Bi={ui(i+1),u0(i+1),vi+1}  (1≤i≤n-2).
Ifp(Bn-2)≤3, then we delete Bn-2 to obtain the subgraph M(Fn-1) with at least 3(n-1)-1 pebbles. By induction, we can move one pebble to v1. If p(Bn-2)=4, then Bn-2→1u0(n-2). Thus we delete Bn-2 to obtain the subgraph M(Fn-1) with 3(n-1)-1 pebbles. By induction, we are done.
Next, suppose thatp(Bn-2)≥5. By Lemma 6, p~(u0(n-1))≥2. If p(u01)=1, then 〈u0(n-1),u01,v1〉 is a transmitting subgraph. If p(v0)≥2, then v0→1u01, and we are done. If there exists some Bi with p(Bi)≥5  (i≠n-2), then Bi→1u01, and we are done. Thus we assume that p(u01)=0, p(v0)≤1, and p(Bi)≤4 for 1≤i≤n-3.
Now, we considerBi (1≤i≤n-3). Clearly, if p(B1)=4, then we are done. Suppose that there exists some Bj with p(Bj)=4 (j≠1). It is clear that if one of the three cases ((i) p(u0j)≥1 (u0j∈Bj-1), (ii) p(Bj-1)≥3, and (iii) p(vj)≥2 (vj∈Bj-1)) happens, then we can move one pebble to v. Thus we assume that p(Bi)=4 (2≤i≤n-3), p(Bi-1)≤2, p(u0i)=0, and p(vi)≤1. If there are r sets Bi1,Bi2,…,Bir such that p(Bik)=4 for 1≤k≤r, then p(Bik-1)≤2 for 1≤k≤r. Let N1={i1,i2,…,ir}, let N2={i1-1,i2-1,…,ir-1}, and let N3={1,2,…,n-3}-N1-N2. If p(Bj)=2 for all j∈N2 and p(Bk)=3 for all k∈N3, then p~(uj(j+1))=1 and p~(uk(k+1))=1. Recall that p(Bi)=4 for all i∈N1 and p(Bn-2)≥5. Then p~(ui(i+1))=1 and p~(u(n-2)(n-1))=2. Thus 〈u(n-2)(n-1),u(n-3)(n-2),…,u12,v1〉 is a transmitting subgraph. So there is at least some j in N2 such that p(Bj)≤1 or at least some k in N3 such that p(Bk)≤2. If there are two j′ and j′′ in N2 such that p(Bj′)≤1 and p(Bj′′)≤1 or two k′ and k′′ in N3 such that p(Bk′)≤2 and p(Bk′′)≤2 or some j in N2 such that p(Bj)≤1 and some k in N3 such that p(Bk)≤2, then p(Bn-2)≥9. By Lemma 6, p~(u0(n-1))=4. Hence 〈u0(n-1),u01,v1〉 is a transmitting subgraph.
Finally, there are two remaining cases, (i) there is only somej in N2 such that p(Bj)≤1, and (ii) there is only some k in N3 such that p(Bk)≤2. So p(Bn-2)≥8. If p(u(n-2)(n-1))=0, then 〈vn-1,u0(n-1),u01,v1〉 is a transmitting subgraph. If p(u(n-2)(n-1))≠0, then, in Bn-2, p~(u(n-2)(n-1))≥2 and p~(u0(n-1))≥2. For (i), we have p~(ui(i+1))≥1 for j+2≤i≤n-3. By the transmitting subgraph 〈u(n-2)(n-1),u(n-3)(n-2),…,u(j+1)(j+2)〉, p~(Bj+1)=5 and we are done. Suppose that (ii) holds. If p(Bk)=2, then we can move one pebble from u0(n-1) to u0(k+1) so that p(Bk)=3, and we are done. If p(Bk)≤1, then p(Bn-2)≥9 and we are done.
(3) Considerv=u12 (or v=u(n-2)(n-1)). Obviously, p(u01)≤1 and p(vi)≤1  (i=1,2). Otherwise, one pebble can be moved to u12. The proof is similar to (2).
(4) Considerv=vi(2≤i≤n-2) (or v=uj(j+1)(2≤j≤n-3)) and p(vi)=0. Let B={v1,u12,u01}, and let B′={vn-1,u(n-2)(n-1),u0(n-1)}. If p(B)≤3, then delete B to obtain the subgraph M(Fn-1) with at least 3(n-1)-1 pebbles. By induction, we can move one pebble to v. If p(B)=4, then we can move one pebble from B to u02, after deleting B to obtain the subgraph M(Fn-1) with 3(n-1)-1 pebbles. Hence we assume that p(B)≥5. According to symmetry, p(B′)≥5. Therefore we are done.


## 3. The 2-Pebbling Property ofM(Fn)

For a distribution of pebbles onG, let q be the number of vertices with at least one pebble. We say a graph G satisfies the 2-pebbling property if two pebbles can be moved to any specified vertex when the total starting number of pebbles is 2f(G)-q+1. Next we will discuss the 2-pebbling property of M(Fn). For the convenience of statement, let S={x1,x2,…,xn}, and let A={y1,y2,…,y2n-3}, where x1=v0, x2=u01,…,xn=u0(n-1), y1=v1, and y2=u12,…,y2n-3=vn-1. In this section let q=qs+qa, where qs and qa are the number of vertices with at least one pebble in S and A, respectively.Lemma 12.
Suppose thatp(M(Fn))≥2(3n-1)-q and qa=2n-4. If p(S)=qs+t  (t=0,1,2) and p(yr)=0  (1≤r≤2n-3), then one can move 2 pebbles to yr.Proof.
Letr=2k-1 (or r=2k). Since qa=2n-4 and p(S)=qs+t, so p(A)≥4n+2-2qs-t. Without loss of generality, there exists a positive integer j  (j>r) such that the corresponding vertex yj with p(yj)≥2 and p(yi)=1 for r+1≤i≤j-1. Thus yj→1yj-1→1⋯→1yr. Using the remaining 4n+2-t-2qs-(j-r+1) pebbles on vertices y1,y2,…,yr-1,yj,yj+1,…,y2n-3, we can move at least n+⌊(5-t)/2⌋-qs pebbles to S so that p~(S)≥n+⌊(5+t)/2⌋. By Lemma 6, p~(xk+1)=2. So we can move one additional pebble from xk+1 to yr so that p~(yr)=2.Lemma 13.
Suppose thatp(M(Fn))=2(3n-1)-q+1 and qa=2n-5. If p(S)=qs+t  (t=0,1) and p(yr)=0  (1≤r≤2n-3), then one can move 2 pebbles to yr.Proof.
Letr=2k-1  (or r=2k). Since qa=2n-5, we see that there is only some vertex yi0  (i0≠r) with p(yi0)=0. Without loss of generality, there exists a positive integer j  (j>r) such that the corresponding vertex yj with p(yj)≥2 and p(yi)≤1 for r<i<j. If i0=2k0-1  (k0≠k) or i0∉{r+1,r+2,…,j-1}, then we can move one pebble to yr by the transmitting subgraph 〈yj,yj-2,…,yr+1,yr〉 or 〈yj,yj-1,yj-3,…,yr+1,yr〉. Now using the remaining at least 4n+4-t-2qs-(j-r+1) pebbles on the set A1={y1,y2,…,yr-1,yj,yj,…,y2n-3}, we can move n+⌊(7-t)/2⌋-qs pebbles from the A1 to S so that p~(S)=n+⌊(7+t)/2⌋. By Lemma 6, p~(xk+1)=2 and we can move one additional pebble from xk+1 to yr so that p~(yr)=2.
Suppose thati0=2k0  (k0≥k) and i0∈{r+1,r+2,…,j-1}. If j=i0+1, then yj→1yi0. Thus there must exist one vertex yj′  (j′≥j) with p(yj′)≥2 and p(yi)≤1 for r<i<j′. Using the transmitting subgraph 〈yj′,yj′-2,…,yr+1,yr〉 or 〈yj′,yj′-1,yj′-3,…,yr+1,yr〉, we can move one pebble to yr. Now, using the remaining 4n+4-t-2qs-(j′-r+2) pebbles on the set {y1,y2,…,yr-1,yj′,yj′+1,…,y2n-3}, we can move n+⌊(6-t)/2⌋-qs pebbles from the set {y1,y2,…,yr-1,yj′,yj′+1,…,y2n-3} to S so that p~(S)≥n+⌊(6+t)/2⌋. By Lemma 6, p~(xk+1)=2 and we are done. Next, suppose that j≥i0+2.
(1) Considerp(y2k)=1. We divide into three subcases.
(1.1) Considerp(xk+2)=0. We delete vertices yr,yr+1,…,y2k0,xk+2 to obtain the subgraph with two sets A2=A-{yr,yr+1,…,y2k0} and S1=S-{xk+2}, and p(A2)=4n+4-2qs-t-(2k0-r-1) and p(S1)=qs+t. Thus we can move n+⌊(10-t)/2⌋-qs pebbles from A2 to S1 so that p~(S1)=n+⌊(10+t)/2⌋. By Lemma 6, p~(xk+1)=4 and we can move two pebbles from xk+1 to yr.
(1.2) Considerp(xk+2)=1. Suppose that j=2k′ or j=2k′+1 (k′>k). Let A3={y2k′,y2k′+1}. Obviously, p(A3)≥3. If p(A3)≥5, then
(2)A3⟶2xk′+2⟶1xk+2⟶1yr+1⟶1yr.
We delete yr,yr+1,…,y2k0,xk+2 to obtain the subgraph with two sets A2 and S1. So p(A2)=4n-2qs-t-(2k0-r-1) and p~(S1)=qs-1+t. We can move n+⌊(6-t)/2⌋-qs pebbles from A2 to S1 so that p~(S1)=n+⌊(4+t)/2⌋. By Lemma 6, p~(xk+1)=2 and we are done. If p(A3)=3,4 and p(xk′+2)≠0, then
(3)A3⟶1xk′+2⟶1xk+2⟶1yr+1⟶1yr.
We delete yr,yr+1,…,y2k0,xk+2 to obtain the subgraph with two sets A2 and S1. So p(A2)=4n+2-2qs-t-(2k0-r-1) and p~(S1)=qs-2+t. We can move n+⌊(8-t)/2⌋-qs pebbles from A2 to S1 so that p~(S1)=n+⌊(4+t)/2⌋. By Lemma 6, p~(xk+1)=2 and we are done. If p(A3)=3,4 and p(xk′+2)=0, then A3→1xk′+1. We delete yr,yr+1,…,y2k0,y2k′,y2k′+1,xk′+2 to obtain the subgraph with two sets A4=A2-A3 and S2=S-{x2k′+2}. So p(A4)≥4n-2qs-t-(2k0-r-1) and p~(S2)=qs+1+t. We can move n+⌊(8-t)/2⌋-qs pebbles from A4 to S2 so that p~(S2)=n+⌊(10+t)/2⌋. By Lemma 6, p~(xk+1)=4.
(1.3) Considerp(xk+2)=2 for t=1. Thus xk+2→1y2k→1yr. We delete yr,yr+1,…,y2k0,xk+2 to obtain the subgraph with two sets A2 and S1. So p(A2)=4n+3-2qs-(2k0-r-1) and p~(S1)=qs-1. n+4-qs pebbles can be moved from A2 to S1 so that p~(S1)=n+3. By Lemma 6, p~(xk+1)=3. So we can move one additional pebble from xk+1 to yr.
(2) Considerp(y2k)=0; that is, k=k0. We divide into three subcases.
(2.1) Considerp(x2k+2)=0. We delete yr,yr+1,yr+2,x2k+2 to obtain the subgraph with two sets A5=A-{yr,yr+1,yr+2} and S1. One has p(A5)=4n+3-2qs-t and p(S1)=qs+t. We can move n+⌊(10-t)/2⌋-qs pebbles from A5 to S1 so that p~(S1)=n+⌊(10+t)/2⌋. By Lemma 6, p~(xk+1)=4 and we can move two pebbles from xk+1 to yr.
(2.2) Considerp(xk+2)=1. We have
(4)yj⟶1yj-1⟶1⋯⟶1yr+2⟶1xk+2⟶1xk+1.
We delete vertices yr,yr+1,…,yj-1,xk+2 to obtain the subgraph with two sets A1 and S1. So p(A1)=4n+4-2qs-t-(j-r) and p~(S1)=qs+t-1 (except one moved pebble on xk+1). We can move n+⌊(8-t)/2⌋-qs pebbles from A5 to S1 so that p~(S1)=n+⌊(6+t)/2⌋ (except one moved pebble on xk+1). By Lemma 6, we can move 3 additional pebbles to xk+1 so that p~(xk+1)=4.
(2.3)p(xk+2)=2 for t=1. Thus xk+2→1xk+1. Deleting yr,yr+1,yr+2,xk+2 to obtain the subgraph with two sets A5 and S1. One has p(A5)=4n+2-2qs and p~(S1)=qs-1 (except one moved pebble on xk+1). We can move n+4-qs pebbles from A4 to S1 so that p~(S1)=n+3 (except one moved pebble on xk+1). By Lemma 6, we can move 3 additional pebbles to xk+1 so that p~(xk+1)=4.Theorem 14.
M
(
F
n
) has the 2-pebbling property.Proof.
Suppose thatv is our target vertex. If p(v)=1, then the number of pebbles on M(Fn) except one pebble on v is 2(3n-1)+1-q-1  (>3n-1). By Theorem 11, we can move one additional pebble to v so that p~(v)=2. Next we assume that p(v)=0.
(1) Considerv=xr (1≤r≤n). If there exists some vertex xi with p(xi)≥2  (i≠r), then xi→1xr. Using the remaining 2(3n-1)+1-q-2>3n-1 pebbles, we can move one additional pebble to xr so that p~(xr)=2. If p(xi)≤1 for 1≤i≤n, then p(A)=2(3n-1)-q+1-qs=6n-1-qa-2qs≥4n+2-2qs. Thus we can move at least n+2-qs pebbles from A to S so that p~(S)=n+2. By Lemma 6, we can move two pebbles to xr.
(2) Considerv=yr (1≤r≤2n-3). Let r=2k-1 (or r=2k). If p(xk+1)≥2, then we can put one pebble on yr. After that, the remaining 2(3n-1)-q+1-2  (>3n-1) pebbles on M(Fn) suffice to put one additional pebble on yr by Theorem 11. Next we assume p(xk+1)≤1.
(2.1) Suppose thatp(xk+1)=1. If there is some vertex xi with p(xi)≥2  (i≠k+1), then xi→1xk+1→1yr. The remaining 2(3n-1)-q+1-3  (>3n-1) pebbles on M(Fn) will suffice to put one additional pebble on yr so that p~(yr)=2. Next we assume that p(xi)≤1 for 1≤i≤n. Obviously, p(S)=qs and p(A)=2(3n-1)-q+1-qs=6n-1-qa-2qs. If qa≤2n-5, then p(A)≥4n+4-2qs. Thus we can move at least n+5-qs pebbles from A to S so that p~(S)=n+5. By Lemma 6, we can move 3 additional pebbles to xk+1 so that p~(xk+1)=4 and we are done. If qa=2n-4, then, by Lemma 12, we are done.
(2.2) Suppose thatp(xk+1)=0. If we can find some vertex xi with p(xi)≥4 or find two vertices xj with p(vj)≥2 and xj′ with p(xj′)≥2, then using 4 pebbles on xi or two pebbles on xj and two pebbles on xj′ we can move one pebble to yr. Then the remaining 2(3n-1)-q+1-4  (>3n-1) pebbles on M(Fn) will suffice to put one additional pebble to yr so that p~(yr)=2.
Consider only some vertexxi with 2≤p(xi)≤3. If p(xi)=3, then xi→1xk+1, p~(S)=qs, and p(A)=2(3n-1)-qs-qa+1-(qs+2)=6n-3-2qs-qa. When qa≤2n-5 and p(A)≥4n+2-2qs, we can move at least n+4-qs pebbles from A to S so that p~(S)≥n+4 except for one pebble on xk+1. By Lemma 6, we can put 3 additional pebbles on xk+1 so that p~(xk+1)=4. When qa=2n-4, we are done with Lemma 12. If p(xi)=2, then xi→1xk+1, p~(S)=qs-1, and p(A)=2(3n-1)-qs-qa+1-(qs+1)=6n-2-2qs-qa. When qa≤2n-6 and p(A)≥4n+4-2qs, we can move at least n+5-qs pebbles from A to S so that p~(S)≥n+4 except for one pebble on xk+1. By Lemma 6, we can put 3 additional pebbles on xk+1 so that p~(xk+1)=4. When qa=2n-4 and qa=2n-5, we are done with Lemmas 12 and 13.
Considerp(xi)≤1 for 1≤i≤n. Obviously, p(S)=qs and p(A)=6n-1-qa-2qs. When qa≤2n-6 and p(A)≥4n+5-2qs, we can move at least n+6-qs pebbles from A to S so that p~(S)≥n+6. By Lemma 6, p~(xk+1)=4 and we are done. When qa=2n-4 and qa=2n-5, we are done with Lemmas 12 and 13.



---

*Source: 304514-2014-07-22.xml*