(ProQuest: ... denotes non-US-ASCII text omitted.)
Academic Editor:Ying Tan
1, School of Mathematical Sciences, Huaibei Normal University, Huaibei, Anhui 235000, China
Received 29 April 2014; Accepted 7 July 2014; 22 July 2014
This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.
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 graph G , 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)...5;max...{|V(G)|,2D } , where |V(G)| is the number of vertices of G and D is the diameter of G .
Throughout this paper, let G 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[arrow right]mv refers to taking 2m pebbles off u and placing m pebbles on v . Denote by Y9;v1 ,v2 ,...,vn YA; 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 by Fn , is a path Pn-1 plus an extra vertex v0 connected to all vertices of the path Pn-1 , where Pn-1 =Y9;v1 ,v2 ,...,vn-1 YA; .
Definition 2.
The middle graph M(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 of Fn . 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 ) .
[figure omitted; refer to PDF]
Definition 3.
A transmitting subgraph is a path Y9;v0 ,v1 ,...,vk YA; 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]).
Let Pk+1 =Y9;v0 ,v1 ,...,vk YA; . If [figure omitted; refer to PDF] then Pk+1 is a transmitting subgraph.
Definition 5.
The t -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]).
If Kn is the complete graph with n (n...5;2) vertices, then ft (Kn )=2t+n-2 .
Lemma 7 (see [4]).
Consider f(M(Pn ))=2n +n-2 .
Chung found the pebbling numbers of the n -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...5;2) and f(M(C2n+1 ))=[left floor]2n+3 /3[right floor]+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 of M(Fn )
In this section, we study the pebbling number of M(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 )[congruent with]M(C3 ) . Hence we have the following theorem.
Theorem 8 (see [9]).
Consider f(M(F3 ))=7 .
Lemma 9.
Let f(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.
Let v be our target vertex, and let p(v)=0 , where v∈S . We may assume that v...0;u01 (after relabeling if necessary). Let B={v1 ,u12 ,u01 } . If p(B)...5;5 , then p~(u01 )...5;2 by Lemma 6, and we can move one pebble to v . If p(B)=4 , then B[arrow right]1u02 . We delete v1 ,u01 , and u12 to obtain the subgraph M(Fn-1 ) with p pebbles, thus we can move one pebble to v . If p(B)...4;3 , then we delete v1 ,u01 , and u12 to obtain the subgraph M(Fn-1 ) with at least p pebbles and we are done.
Theorem 10.
Consider f(M(F4 ))=11 .
Proof.
We place 7 pebbles on v3 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 ))...5;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) Consider v∈S . By Theorem 8 and Lemma 9, we can move one pebble to v .
(2) Consider v=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 [left floor](8-t)/2[right floor] pebbles from A1 to S so that p~(S)=[left floor](8+t)/2[right floor]...5;6 for t...5;4 . By Lemma 6, p~(u01 )=2 and we can move one pebble to v1 . If t...4;2 , then p(A)...5;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 )...5;7 , then A3 [arrow right]3u03 . So Y9;u03 ,u01 ,v1 YA; is a transmitting subgraph. If 4...4;p(A3 )...4;6 , then 2...4;p(A2 )...4;4 . By Lemma 6, p~(u23 )...5;2 and p~(u12 )...5;1 . So Y9;u23 ,u12 ,v1 YA; is a transmitting subgraph. If p(A3 )...4;3 , then p(A2 )...5;5 . So Y9;v2 ,u12 ,v1 YA; is a transmitting subgraph.
(3) Consider v=v2 . If p(S)...5;4 or p(S)...4;2 , then we are done with (2). If p(S)=3 , then p(v1 )+p(u12 )...5;4 or p(u23 )+p(v3 )...5;4 . So Y9;v1 ,u12 ,v2 YA; or Y9;v3 ,u23 ,v2 YA; is a transmitting subgraph.
(4) Consider v=u12 (or v=u23 ). If p(S)...5;4 or p(S)...4;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 )...5;2 or p(v2 )...5;2 . Next suppose that p(v1 )...4;1 and p(v2 )...4;1 . Thus p(u23 )+p(v3 )...5;6 . So Y9;v3 ,u23 ,u12 YA; is a transmitting subgraph.
Theorem 11.
Consider f(M(Fn ))=3n-1 (n...5;4) .
Proof.
We place 7 pebbles on vn-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 ))...5;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) Consider v∈S . By induction and Theorem 8, we can move one pebble to v .
(2) Consider v=v1 (or v=vn-1 ). Obviously, p(u01 )...4;1 . Otherwise, p(u01 )>1 . v1 can obtain one pebble. Let Bi ={ui(i+1) ,u0(i+1) ,vi+1 } (1...4;i...4;n-2) .
If p(Bn-2 )...4;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 [arrow right]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 that p(Bn-2 )...5;5 . By Lemma 6, p~(u0(n-1) )...5;2 . If p(u01 )=1 , then Y9;u0(n-1) ,u01 ,v1 YA; is a transmitting subgraph. If p(v0 )...5;2 , then v0 [arrow right]1u01 , and we are done. If there exists some Bi with p(Bi )...5;5 (i...0;n-2) , then Bi [arrow right]1u01 , and we are done. Thus we assume that p(u01 )=0 , p(v0 )...4;1 , and p(Bi )...4;4 for 1...4;i...4;n-3 .
Now, we consider Bi (1...4;i...4;n-3 ). Clearly, if p(B1 )=4 , then we are done. Suppose that there exists some Bj with p(Bj )=4 (j...0;1 ). It is clear that if one of the three cases ((i) p(u0j )...5;1 (u0j ∈Bj-1 ), (ii) p(Bj-1 )...5;3 , and (iii) p(vj )...5;2 (vj ∈Bj-1 )) happens, then we can move one pebble to v . Thus we assume that p(Bi )=4 (2...4;i...4;n-3 ), p(Bi-1 )...4;2 , p(u0i )=0 , and p(vi )...4;1 . If there are r sets Bi1 ,Bi2 ,...,Bir such that p(Bik )=4 for 1...4;k...4;r , then p(Bik -1 )...4;2 for 1...4;k...4;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;5 . Then p~(ui(i+1) )=1 and p~(u(n-2)(n-1) )=2 . Thus Y9;u(n-2)(n-1) ,u(n-3)(n-2) ,...,u12 ,v1 YA; is a transmitting subgraph. So there is at least some j in N2 such that p(Bj )...4;1 or at least some k in N3 such that p(Bk )...4;2 . If there are two j[variant prime] and j[variant prime][variant prime] in N2 such that p(Bj[variant prime] )...4;1 and p(Bj[variant prime][variant prime] )...4;1 or two k[variant prime] and k[variant prime][variant prime] in N3 such that p(Bk[variant prime] )...4;2 and p(Bk[variant prime][variant prime] )...4;2 or some j in N2 such that p(Bj )...4;1 and some k in N3 such that p(Bk )...4;2 , then p(Bn-2 )...5;9 . By Lemma 6, p~(u0(n-1) )=4 . Hence Y9;u0(n-1) ,u01 ,v1 YA; is a transmitting subgraph.
Finally, there are two remaining cases, (i) there is only some j in N2 such that p(Bj )...4;1 , and (ii) there is only some k in N3 such that p(Bk )...4;2 . So p(Bn-2 )...5;8 . If p(u(n-2)(n-1) )=0 , then Y9;vn-1 ,u0(n-1) ,u01 ,v1 YA; is a transmitting subgraph. If p(u(n-2)(n-1) )...0;0 , then, in Bn-2 , p~(u(n-2)(n-1) )...5;2 and p~(u0(n-1) )...5;2 . For (i), we have p~(ui(i+1) )...5;1 for j+2...4;i...4;n-3 . By the transmitting subgraph Y9;u(n-2)(n-1) ,u(n-3)(n-2) ,...,u(j+1)(j+2) YA; , 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 )...4;1 , then p(Bn-2 )...5;9 and we are done.
(3) Consider v=u12 (or v=u(n-2)(n-1) ). Obviously, p(u01 )...4;1 and p(vi )...4;1 (i=1,2) . Otherwise, one pebble can be moved to u12 . The proof is similar to (2).
(4) Consider v=vi (2...4;i...4;n-2) (or v=uj(j+1) (2...4;j...4;n-3) ) and p(vi )=0 . Let B={v1 ,u12 ,u01 } , and let B[variant prime] ={vn-1 ,u(n-2)(n-1) ,u0(n-1) } . If p(B)...4;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;5 . According to symmetry, p(B[variant prime] )...5;5 . Therefore we are done.
3. The 2-Pebbling Property of M(Fn )
For a distribution of pebbles on G , 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 that p(M(Fn ))...5;2(3n-1)-q and qa =2n-4 . If p(S)=qs +t (t=0,1,2) and p(yr )=0 (1...4;r...4;2n-3) , then one can move 2 pebbles to yr .
Proof.
Let r=2k-1 (or r=2k ). Since qa =2n-4 and p(S)=qs +t , so p(A)...5;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 )...5;2 and p(yi )=1 for r+1...4;i...4;j-1 . Thus yj [arrow right]1yj-1 [arrow right]1...[arrow right]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+[left floor](5-t)/2[right floor]-qs pebbles to S so that p~(S)...5;n+[left floor](5+t)/2[right floor] . 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 that p(M(Fn ))=2(3n-1)-q+1 and qa =2n-5 . If p(S)=qs +t (t=0,1) and p(yr )=0 (1...4;r...4;2n-3) , then one can move 2 pebbles to yr .
Proof.
Let r=2k-1 (or r=2k ). Since qa =2n-5 , we see that there is only some vertex yi0 (i0 ...0;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 )...5;2 and p(yi )...4;1 for r<i<j . If i0 =2k0 -1 (k0 ...0;k) or i0 ∉{r+1,r+2,...,j-1} , then we can move one pebble to yr by the transmitting subgraph Y9;yj ,yj-2 ,...,yr+1 ,yr YA; or Y9;yj ,yj-1 ,yj-3 ,...,yr+1 ,yr YA; . 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+[left floor](7-t)/2[right floor]-qs pebbles from the A1 to S so that p~(S)=n+[left floor](7+t)/2[right floor] . 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 that i0 =2k0 (k0 ...5;k) and i0 ∈{r+1,r+2,...,j-1} . If j=i0 +1 , then yj [arrow right]1yi0 . Thus there must exist one vertex yj[variant prime] (j[variant prime] ...5;j) with p(yj[variant prime] )...5;2 and p(yi )...4;1 for r<i<j[variant prime] . Using the transmitting subgraph Y9;yj[variant prime] ,yj[variant prime] -2 ,...,yr+1 ,yr YA; or Y9;yj[variant prime] ,yj[variant prime] -1 ,yj[variant prime] -3 ,...,yr+1 ,yr YA; , we can move one pebble to yr . Now, using the remaining 4n+4-t-2qs -(j[variant prime] -r+2) pebbles on the set {y1 ,y2 ,...,yr-1 ,yj[variant prime] ,yj[variant prime] +1 ,...,y2n-3 } , we can move n+[left floor](6-t)/2[right floor]-qs pebbles from the set {y1 ,y2 ,...,yr-1 ,yj[variant prime] ,yj[variant prime] +1 ,...,y2n-3 } to S so that p~(S)...5;n+[left floor](6+t)/2[right floor] . By Lemma 6, p~(xk+1 )=2 and we are done. Next, suppose that j...5;i0 +2 .
(1) Consider p(y2k )=1 . We divide into three subcases.
(1.1) Consider p(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+[left floor](10-t)/2[right floor]-qs pebbles from A2 to S1 so that p~(S1 )=n+[left floor](10+t)/2[right floor] . By Lemma 6, p~(xk+1 )=4 and we can move two pebbles from xk+1 to yr .
(1.2) Consider p(xk+2 )=1 . Suppose that j=2k[variant prime] or j=2k[variant prime] +1 (k[variant prime] >k ). Let A3 ={y2k[variant prime] ,y2k[variant prime] +1 } . Obviously, p(A3 )...5;3 . If p(A3 )...5;5 , then [figure omitted; refer to PDF] 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+[left floor](6-t)/2[right floor]-qs pebbles from A2 to S1 so that p~(S1 )=n+[left floor](4+t)/2[right floor] . By Lemma 6, p~(xk+1 )=2 and we are done. If p(A3 )=3,4 and p(xk[variant prime] +2 )...0;0 , then [figure omitted; refer to PDF] 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+[left floor](8-t)/2[right floor]-qs pebbles from A2 to S1 so that p~(S1 )=n+[left floor](4+t)/2[right floor] . By Lemma 6, p~(xk+1 )=2 and we are done. If p(A3 )=3,4 and p(xk[variant prime] +2 )=0 , then A3 [arrow right]1xk[variant prime] +1 . We delete yr ,yr+1 ,...,y2k0 ,y2k[variant prime] ,y2k[variant prime] +1 ,xk[variant prime] +2 to obtain the subgraph with two sets A4 =A2 -A3 and S2 =S-{x2k[variant prime] +2 } . So p(A4 )...5;4n-2qs -t-(2k0 -r-1) and p~(S2 )=qs +1+t . We can move n+[left floor](8-t)/2[right floor]-qs pebbles from A4 to S2 so that p~(S2 )=n+[left floor](10+t)/2[right floor] . By Lemma 6, p~(xk+1 )=4 .
(1.3) Consider p(xk+2 )=2 for t=1 . Thus xk+2 [arrow right]1y2k [arrow right]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) Consider p(y2k )=0 ; that is, k=k0 . We divide into three subcases.
(2.1) Consider p(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+[left floor](10-t)/2[right floor]-qs pebbles from A5 to S1 so that p~(S1 )=n+[left floor](10+t)/2[right floor] . By Lemma 6, p~(xk+1 )=4 and we can move two pebbles from xk+1 to yr .
(2.2) Consider p(xk+2 )=1 . We have [figure omitted; refer to PDF] 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+[left floor](8-t)/2[right floor]-qs pebbles from A5 to S1 so that p~(S1 )=n+[left floor](6+t)/2[right floor] (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 [arrow right]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 that v 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) Consider v=xr (1...4;r...4;n ). If there exists some vertex xi with p(xi )...5;2 (i...0;r) , then xi [arrow right]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 )...4;1 for 1...4;i...4;n , then p(A)=2(3n-1)-q+1-qs =6n-1-qa -2qs ...5;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) Consider v=yr (1...4;r...4;2n-3 ). Let r=2k-1 (or r=2k ). If p(xk+1 )...5;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 )...4;1 .
(2.1) Suppose that p(xk+1 )=1 . If there is some vertex xi with p(xi )...5;2 (i...0;k+1) , then xi [arrow right]1xk+1 [arrow right]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 )...4;1 for 1...4;i...4;n . Obviously, p(S)=qs and p(A)=2(3n-1)-q+1-qs =6n-1-qa -2qs . If qa ...4;2n-5 , then p(A)...5;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 that p(xk+1 )=0 . If we can find some vertex xi with p(xi )...5;4 or find two vertices xj with p(vj )...5;2 and xj[variant prime] with p(xj[variant prime] )...5;2 , then using 4 pebbles on xi or two pebbles on xj and two pebbles on xj[variant prime] 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 vertex xi with 2...4;p(xi )...4;3 . If p(xi )=3 , then xi [arrow right]1xk+1 , p~(S)=qs , and p(A)=2(3n-1)-qs -qa +1-(qs +2)=6n-3-2qs -qa . When qa ...4;2n-5 and p(A)...5;4n+2-2qs , we can move at least n+4-qs pebbles from A to S so that p~(S)...5;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 [arrow right]1xk+1 , p~(S)=qs -1 , and p(A)=2(3n-1)-qs -qa +1-(qs +1)=6n-2-2qs -qa . When qa ...4;2n-6 and p(A)...5;4n+4-2qs , we can move at least n+5-qs pebbles from A to S so that p~(S)...5;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.
Consider p(xi )...4;1 for 1...4;i...4;n . Obviously, p(S)=qs and p(A)=6n-1-qa -2qs . When qa ...4;2n-6 and p(A)...5;4n+5-2qs , we can move at least n+6-qs pebbles from A to S so that p~(S)...5;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.
Acknowledgments
This work is supported by National Natural Science Foundation of China (no. 10971248) and Anhui Provincial Natural Science Foundation (nos. 1408085MA08 and KJ2013Z279).
Conflict of Interests
The authors declare that there is no conflict of interests regarding the publication of this paper.
[1] F. R. K. Chung, "Pebbling in hypercubes," SIAM Journal on Discrete Mathematics , vol. 2, no. 4, pp. 467-472, 1989.
[2] H. S. Snevily, J. A. Foster, "The 2-pebbling property and a conjecture of Graham's," Graphs and Combinatorics , vol. 16, no. 2, pp. 231-244, 2000.
[3] A. Lourdusamy, S. Somasundaram, "The t -pebbling number of graphs," Southeast Asian Bulletin of Mathematics , vol. 30, no. 5, pp. 907-914, 2006.
[4] H. Y. Liu, Q. Qin, Z. P. Wang, Y. G. Ma, "Pebbling number, of middle graphs," Journal of Dalian Maritime University , vol. 32, no. 4, pp. 125-128, 2006.
[5] L. Pachter, H. S. Snevily, B. Voxman, "On pebbling graphs," Congressus Numerantium , vol. 107, pp. 65-80, 1995.
[6] Y. S. Ye, M. Q. Zhai, Y. Zhang, "Pebbling number of squares of odd cycles," Discrete Mathematics , vol. 312, no. 21, pp. 3174-3178, 2012.
[7] Y. Ye, P. Zhang, Y. Zhang, "The pebbling number of squares of even cycles," Discrete Mathematics , vol. 312, no. 21, pp. 3203-3211, 2012.
[8] R. Feng, J. Y. Kim, "Pebbling numbers of some graphs," Science in China A , vol. 45, no. 4, pp. 470-478, 2002.
[9] Y. S. Ye, F. Liu, M. Q. Zhai, "Pebbling numbers of middle graphs of cycles and Graham's conjecture," Operations Research Transactions , vol. 17, no. 3, pp. 35-44, 2013.
You have requested "on-the-fly" machine translation of selected content from our databases. This functionality is provided solely for your convenience and is in no way intended to replace human translation. Show full disclaimer
Neither ProQuest nor its licensors make any representations or warranties with respect to the translations. The translations are automatically generated "AS IS" and "AS AVAILABLE" and are not retained in our systems. PROQUEST AND ITS LICENSORS SPECIFICALLY DISCLAIM ANY AND ALL EXPRESS OR IMPLIED WARRANTIES, INCLUDING WITHOUT LIMITATION, ANY WARRANTIES FOR AVAILABILITY, ACCURACY, TIMELINESS, COMPLETENESS, NON-INFRINGMENT, MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE. Your use of the translations is subject to all use restrictions contained in your Electronic Products License Agreement and by using the translation functionality you agree to forgo any and all claims against ProQuest or its licensors for your use of the translation functionality and any output derived there from. Hide full disclaimer
Copyright © 2014 Yongsheng Ye et al. Yongsheng Ye et al. This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.
Abstract
A pebbling move on a graph G 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.
You have requested "on-the-fly" machine translation of selected content from our databases. This functionality is provided solely for your convenience and is in no way intended to replace human translation. Show full disclaimer
Neither ProQuest nor its licensors make any representations or warranties with respect to the translations. The translations are automatically generated "AS IS" and "AS AVAILABLE" and are not retained in our systems. PROQUEST AND ITS LICENSORS SPECIFICALLY DISCLAIM ANY AND ALL EXPRESS OR IMPLIED WARRANTIES, INCLUDING WITHOUT LIMITATION, ANY WARRANTIES FOR AVAILABILITY, ACCURACY, TIMELINESS, COMPLETENESS, NON-INFRINGMENT, MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE. Your use of the translations is subject to all use restrictions contained in your Electronic Products License Agreement and by using the translation functionality you agree to forgo any and all claims against ProQuest or its licensors for your use of the translation functionality and any output derived there from. Hide full disclaimer