Pebbling of graphs was first introduced by Chung [2]. 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$. 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$, where $q$ is the number of vertices with at least one pebble.

There were some known results on the pebbling number (see [2-10]). If one pebble is placed on each vertex other than the vertex $v$, then no pebble can be moved to $v$. Also, if $u$ is at a distance $d$ from $v$, and $2^d-1$ pebbles are placed on $u$, then no pebble can be moved to $v$. So it is clear that $f(G)\geq {\rm max}\{|V(G)|, 2^D\}$, where $D$ is the diameter of graph $G$. Meanwhile, we also know that $f(K_n)=n$ and $f(P_n)=2^{n-1}$ (see [2]), where $K_n$ and $P_n$ denote the complete graph and the path of order $n$ respectively.

Throughout this paper, $G$ will denote a simple connected graph with vertex set $V(G)$ and edge set $E(G)$. Given a distribution of pebbles on the vertices of $G$, denote by $p(H)$, $p(v), $ $\tilde{p}(H)$ and $\tilde{p}(v)$ the number of pebbles on a subgraph $H$ of $G$, the number of pebbles on a vertex $v$ of $G$, the number of pebbles on $H$ and $v$ after some sequence of pebbling moves, respectively. We then say that a vertex $v$ is occupied if $p(v)\geq 1, $ otherwise, we call $v$ to be unoccupied if $p(v)=0$. Denote by $\langle v_1, v_{2}, \cdots, v_n \rangle$ (respectively, $[v_1, v_{2}, \cdots, v_n]$) the path (respectively, cycle) with vertices $v_1, v_{2}, \cdots, v_n $ in this order.

Next, we introduce a definition and give some useful lemmas.

Definition 1.1[1]  The middle graph of a graph $G$, denoted by $M(G)$, is obtained from $G$ by inserting a new vertex into each edge of $G$, and by joining those pairs of these new vertices by edges, which Lie on adjacent edges of $G$.

Lemma 1.2(see [5])   $f(M(P_n))=2^n+n-2.$

Lemma 1.3(see [5])  For a path $\langle v_0, v_1, \cdots, v_n \rangle$, if

$ p(v_0)+2p(v_1)+\cdots+2^ip(v_i)+\cdots+2^{n-1}p(v_{n-1})\geq 2^n, $

then one pebble can be moved to $v_n$.

Corollary 1.4  For a path $\langle v_0, v_1, \cdots, v_n \rangle$, suppose that $p(v_0)\geq 2^{n+1}-(2+2^2+\cdots+2^r)$ and there are $r$ occupied vertices in the set $\{v_1, v_2, \cdots, v_n\}$, say $v_{i_1}, v_{i_2}, \cdots, v_{i_r}$, then at least two pebbles can be moved to $v_k(1\leq k\leq n)$ using one pebble each from $v_{i_j}$ with $1\leq j\leq r$ and $2^{n+1}-(2+2^2+\cdots+2^r)$ pebbles from $v_0$.

Proof  Obviously, we can move at least two pebbles to $v_k (1\leq k\leq n-1)$ or one pebble to $v_n$ using $2^n$ pebbles from $v_0$. Using one pebble each from $v_{i_j}$ and $2^n-(2+2^2+\cdots+2^r)$ pebbles from $v_0$, we can move one additional pebble to $v_n$ by Lemma 1.3.

Lemma 1.5(see [10])  Let $P_n=\langle v_1, v_2, \cdots, v_n\rangle$. Then $f(M(P_n)-v_n)=2^{n-1}+n-2$.

Lemma 1.6(see [10])   $f(M(C_{2n}))=2^{n+1}+2n-2$.

Lemma 1.7(see [10])   $f(M(C_{2n+1}))=\left\lfloor\displaystyle\frac{2^{n+3}}{3}\right\rfloor+2n.$

Liu et al. [5] gave the pebbling number of middle graphs of paths (see Lemma 1.2). Recently, Ye [10] determined the pebbling number of middle graphs of cycles, and showed that Graham's conjecture holds for middle graphs of odd cycles. Motivated by these results, we show that paths and cycles have the 2-pebbling property, and also prove that Graham's conjecture holds for middle graphs of paths in this paper.

In the section, we first shall show that the middle graphs of paths have the 2-pebbling property, and then prove that the middle graphs of cycles have the 2-pebbling property.

Theorem 2.1  The middle graphs of paths have the 2-pebbling property.

Proof  Let $P_{n}=\langle v_1, v_2, \cdots, v_{n}\rangle$. $M(P_{n})$ is obtained from $P_{n}$ by inserting $u_i$ into $v_iv_{i+1}$, and joining $u_iu_{i+1}$ for $1\leq i\leq n-1$. Let $q$ be the number of occupied vertices of $M(P_{n})$. Now suppose that $2(2^{n}+n-2)-q+1$ pebbles are placed arbitrarily at the vertices of $M(P_{n})$. Let $v$ be our target vertex. If $p(v)=1$, then $M(P_{n})$ has $2(2^{n}+n-2)-q$ pebbles other than one pebble on $v$. Since $2(2^{n}+2n-2)-q\geq 2^{n}+n-2$, using Lemma 1.2 we can move one additional pebble to $v$ so that $\widetilde{p}(v)=2$. Hence we assume $p(v)=0$.

Without loss of generality, we may assume that our target vertex $v$ is not $v_n$ (otherwise, relabeling). If $p(v_n)\leq 2^n+2^{n-1}+n-q-1$, then

$ p(M(P_n)-v_n)\geq 2(2^n+n-2)-q+1-(2^n+2^{n-1}+n-q-1)=2^{n-1}+n-2. $

By Lemma 1.5, we can move one pebble to $v$. This leaves

$ 2(2^n+n-2)-q+1-(2^{n-1}+n-2)> 2^n+n-2 $

pebbles on $M(P_n)$. By Lemma 1.2, we can move one additional pebble to $v$ so that $\widetilde{p}(v)=2$. Next suppose that $p(v_n)\geq 2^n+2^{n-1}+n-q$. If $q\leq n-1$, then we can move one pebble to $v$ using $2^n$ pebbles on $v_n$, and using the remaining $2(2^n+n-2)-q+1-2^n\geq 2^n+n-2$ pebbles, we can move one additional pebble to $v$ so that $\widetilde{p}(v)=2$. If $q\geq n$, and write $q$ as $q=n+r(r\geq 0)$, then there are at least $r+1$ occupied vertices in the set $\{u_1, u_2, \cdots, u_{n-1}\}$, say $u_{i_1}, u_{i_2}, \cdots, u_{i_{r+1}}$. We now use $2^n-(2+2^2+\cdots+2^{r+1})$ pebbles from $v_n$ and one pebble each from $u_{i_j}(j=1, 2, \cdots, r+1)$ to move two pebbles to $u_i(1\leq i\leq n-1)$ by Corollary 1.4. This implies that we can move one pebble from some $u_i(1\leq i\leq n-1)$ to $v$. This leaves

$ 2(2^n+n-2)-q+1-[2^n-(2+2^2+\cdots+2^{r+1})+(r+1)]\geq 2^n+n-2 $

pebbles on $M(P_n)$. By Lemma 1.2, we can move one additional pebble to $v$ so that $\widetilde{p}(v)=2$.

Theorem 2.2  The middle graphs of even cycles have 2-pebbling property.

Proof  Let $C_{2n}=[v_0, v_1, \cdots, v_{2n-1}]$. $M(C_{2n})$ is obtained from $C_{2n}$ by inserting $u_i$ into $v_iv_{j}$, and joining $u_iu_{j}$ where $j:=(i+1) \ \mod \ (2n)$ for $0\leq i\leq 2n-1$. Let $q$ be the number of occupied vertices of $M(C_{2n})$. Now suppose that $2(2^{n+1}+2n-2)-q+1$ pebbles are placed arbitrarily at the vertices of $M(C_{2n})$. Suppose our target vertex is $v$. If $p(v)=1$, then $C_{2n}$ has $2(2^{n+1}+2n-2)-q$ pebbles other than one pebble on $v$. Using Lemma 1.6 we can move one additional pebble to $v$ so that $\widetilde{p}(v)=2$, since $2(2^{n+1}+2n-2)-q\geq 2^{n+1}+2n-2$. Hence we assume $p(v)=0$. By symmetry, suppose $v$ is either $v_0$ or $u_0$. Obviously, for $q=4n-1$, we are done. Next, we consider the left case $q\leq 4n-2$. We divide into two cases by $v$.

Case 1   $v=u_0$.

Let $A=\{u_0, v_1, u_1, \cdots, u_{n-1}, v_{n}\}$ and let $B=\{ v_{n+1}, u_{n+1}, v_{n+2}, \cdots, v_{2n-1}, u_{2n-1}, v_0, u_0\}$. By Lemma 1.5,

$ f(G[A])=f(G[B])=2^n+n-1. $

If $p(u_n)\leq 2^{n+1}+2n-1-q$, then

$ p(G[A])+p(G[B])\geq 2(2^{n+1}+2n-2)-q+1-(2^{n+1}+2n-1-q)=2^{n+1}+2n-2. $

So

$ p(G[A])\geq 2^n+n-1~~\textrm{or}~~ p(G[B])\geq 2^n+n-1. $

Using $2^n+n-1$ pebbles, we can move one pebble to $u_0$. This leaves $ 2(2^{n+1}+2n-2)-q+1-(2^{n}+n-1)\geq 2^{n+1}+2n-2$ pebbles on $M(C_{2n})$. By Lemma 1.6, we can move one additional pebble to $u_0$ so that $\widetilde{p}(u_0)=2$. Now suppose $p(u_n)\geq 2^{n+1}+2n-q$. Note that $q\leq 4n-2< 2^n+2n$. So $p(u_n)> 2^n$. By Lemma 1.3, using $2^n$ pebbles on $u_n$, we can move one pebble to $u_0$ by the path $\langle u_n, u_{n-1}, \cdots, u_1, u_0\rangle$. This leaves $2(2^{n+1}+2n-2)-q+1-2^{n}\geq 2^{n+1}+2n-2$ pebbles on $M(C_{2n})$. By Lemma 1.6, we can move one additional pebble to $u_0$ so that $\widetilde{p}(u_0)=2$.

Case 2   $v=v_0$.

Let $A'=\{v_0, u_0, v_1, \cdots, v_{n-1}, u_{n-1}\}$ and let $B'=\{v_{0}, u_{2n-1}, v_{2n-1}, \cdots, v_{n+1}, u_{n}\}$. By Lemma 1.5,

$ f(G[A'])=f(G[B'])=2^n+n-1. $

If $p(v_n)\leq 2^{n+1}+2n-1-q$, then

$ p(G[A'])+p(G[B'])\geq 2(2^{n+1}+2n-2)-q+1-(2^{n+1}+2n-1-q)=2^{n+1}+2n-2. $

So

$ p(G[A'])\geq 2^n+n-1~~\textrm{or}~~p(G[B'])\geq 2^n+n-1. $

Using $2^n+n-1$ pebbles, we can move one pebble to $v_0$. This leaves $ 2(2^{n+1}+2n-2)-q+1-(2^{n}+n-1)\geq 2^{n+1}+2n-2$ pebbles on $M(C_{2n})$. By Lemma 1.6, we can move one additional pebble to $v_0$ so that $\widetilde{p}(v_0)=2$. Now suppose $p(v_n)\geq 2^{n+1}+2n-q$.

Subcase 2.1   $q\leq 2n-1$. We have $p(v_n)> 2^{n+1}$. Using $2^{n+1}$ pebbles on $v_n$, we can move one pebble to $v_0$ by the path $\langle v_n, u_{n-1}, \cdots, u_1, v_0\rangle$. Then this leaves $2^{n+1}+2n-2+2n-1-q\geq 2^{n+1}+2n-2$ pebbles on $M(C_{2n})$. By Lemma 1.6, we can move one additional pebble to $v_0$ so that $\widetilde{p}(v_0)=2$.

Subcase 2.2   $q\geq 2n$. And write $q$ as $q=2n+2r$ if $q$ is even and as $q=2n+2r+1$ if $q$ is odd, where $r\geq 0$. Let $q_1$ be the number of occupied vertices in $A'$ and let $q_2$ be the number of occupied vertices in $B'$. Without loss of generality, we may assume $q_1\geq q_2$. For $q=2n+2r$, we have $q_1\geq n+r$, and there are at least $r+1$ occupied vertices in the set $\{u_0, u_1, \cdots, u_{n-1}\}$, say $u_{i_1}, u_{i_2}, \cdots, u_{i_{r+1}}$. Using one pebble each from $u_{i_j}(1\leq j\leq r+1)$ and $2^{n+1}-(2^1+2^2+\cdots+2^{r+1})$ pebbles from $v_n$, we see that one pebble can be moved to $v_0$ at a cost of $2^{n+1}-(2^1+2^2+\cdots+2^{r+1})+(r+1)$ pebbles by Lemma 1.3. This leaves

$ \begin{array}{ll} &2(2^{n+1}+2n-2)-q+1-[2^{n+1}-(2^1+2^2+\cdots+2^{r+1})+(r+1)]\\ \geq& (2^{n+1}+2n-2)+[(2+2^2+2^3+\cdots+2^{r+1})-(3r+2)]\\ \geq& 2^{n+1}+2n-2 \end{array} $

pebbles on $M(C_{2n})$. By Lemma 1.6, we are done. The proof of the odd case $: \ q=2n+2r+1$ is similar.

Theorem 2.3  The middle graphs of odd cycles have 2-pebbling property.

Proof  Let $C_{2n+1}=[v_0, v_1, \cdots, v_{2n}]$. $M(C_{2n+1})$ is obtained from $C_{2n+1}$ by inserting $u_i$ into $v_iv_{j}$, and joining $u_iu_{j}$ where $j:=(i+1) \ \mod \ (2n+1)$ for $0\leq i\leq 2n$. Let $q$ be the number of occupied vertices of $M(C_{2n+1})$. Now suppose that $2\left(\left\lfloor\displaystyle\frac{2^{n+3}}{3}\right\rfloor+2n\right)-q+1$ pebbles are placed arbitrarily at the vertices of $M(C_{2n+1})$.

Let $v$ be our target vertex. If $p(v)=1$, then $C_{2n+1}$ has $2\left(\left\lfloor\displaystyle\frac{2^{n+3}}{3}\right\rfloor+2n\right)-q$ pebbles other than one pebble on $v$. Since $2\left(\left\lfloor\displaystyle\frac{2^{n+3}}{3}\right\rfloor+2n\right)-q\geq \left\lfloor\displaystyle\frac{2^{n+3}}{3}\right\rfloor+2n$, by Lemma 1.7, we can move one additional pebble to $v$ so that $\widetilde{p}(v)=2$. Hence we assume $p(v)=0$. By symmetry, suppose $v$ is either $v_0$ or $u_0$.

Case 1   $v=u_0$.

Let $A=\{u_0, v_1, u_1, v_2, \cdots, v_{n}, u_{n}\}$ and let $B=\{u_0, v_0, u_{2n}, v_{2n}, \cdots, v_{n+2}, u_{n+1}\}$. If

$ p(v_{n+1}) \leq \left\lfloor\displaystyle\frac{2^{n+3}}{3}\right\rfloor+\left\lfloor\displaystyle\frac{2^{n+1}}{3}\right\rfloor+2n-q+1, $

then

$ p(G[A])+p(G[B])\geq 2(\left\lfloor\displaystyle\frac{2^{n+3}}{3}\right\rfloor+2n)-q+1-(\left\lfloor\displaystyle\frac{2^{n+3}}{3}\right\rfloor\\ +2n+\left\lfloor\displaystyle\frac{2^{n+1}}{3}\right\rfloor-q+1)=2^{n+1}+2n. $

So

$ p(G[A])\geq 2^n+n \ \textrm{ or} \ p(G[B])\geq 2^n+n. $

Without loss of generality, we assume that $p(G[A])\geq 2^n+n$. Since $p(u_n)+\sum\limits_{i=1}^{n-1}2^{n-i}p(u_i)\geq p(u_n)+2\lfloor\frac{1}{2}(2^n+1-p(u_n))\rfloor\geq p(u_n)$ $+(2^n-p(u_n))=2^n, $ by Lemma 1.3 we can move one pebble to $u_0$. This leaves $2\left(\left\lfloor\displaystyle\frac{2^{n+3}}{3}\right\rfloor+2n\right)-q+1-(2^{n}+n)\geq \left\lfloor\displaystyle\frac{2^{n+3}}{3}\right\rfloor+2n$ pebbles on $M(C_{2n+1})$. By Lemma 1.7, we can move one additional pebble to $u_0$ so that $\widetilde{p}(u_0)=2$.

Now suppose $p(v_{n+1})\geq \left\lfloor\displaystyle\frac{2^{n+3}}{3}\right\rfloor+\left\lfloor\displaystyle\frac{2^{n+1}}{3}\right\rfloor+2n-q+2$. Note that $q\leq 4n+1$. So $p(v_{n+1})\geq 2^{n+1}$. By Lemma 1.3, using $2^{n+1}$ pebbles on $v_{n+1}$, we can move one pebble to $u_0$ by the path $\langle v_{n+1}, u_n, u_{n-1}, \cdots, u_1, u_0\rangle.$ If $q\leq 4n-2$, then this leaves

$ 2\left(\left\lfloor\displaystyle\frac{2^{n+3}}{3}\right\rfloor+2n\right)-q+1-2^{n+1}\geq \left\lfloor\displaystyle\frac{2^{n+3}}{3}\right\rfloor+2n $

pebbles on $M(C_{2n+1})$. By Lemma 1.7, we can move one additional pebble to $u_0$ so that $\widetilde{p}(u_0)=2$. If $q=4n-1$, then there are at least $2n-2$ occupied vertices in the set $\{u_1, u_2, \cdots, u_{2n}\}$. We may assume that there are $n-1$ occupied vertices in $\{u_1, u_2, \cdots, u_n\}$. Using one pebble each from the occupied vertices, $2^{n+1}-(2^1+2^2+\cdots+2^{n-1})$ pebbles from $v_{n+1}$, it is sufficient to move one pebble to $u_0$ by the path $\langle v_{n+1}, u_n, u_{n-1}, \cdots, u_1, u_0\rangle$. This leaves

$ \begin{array}{ll} &2\left(\left\lfloor\displaystyle\frac{2^{n+3}}{3}\right\rfloor+2n\right)-q+1-[2^{n+1}-(2^1+2^2+\cdots+2^{n-1})+(n-1)]\\ =&\left\lfloor\displaystyle\frac{2^{n+3}}{3}\right\rfloor+2n+\left\lfloor\displaystyle\frac{2^{n+1}}{3}\right\rfloor+(2+2^2+2^3+\cdots+2^{n-1})-3n+3)]\\ \geq& \left\lfloor\displaystyle\frac{2^{n+3}}{3}\right\rfloor+2n \end{array} $

pebbles on $M(C_{2n+1})$ and by Lemma 1.7, we are done. When $q=4n, 4n+1$, the proof is similar.

Case 2   $v=v_0$

Let $A'=\{v_0, u_0, v_1, \cdots, v_{n-1}, u_{n-1}\}$ and let $B'=\{v_{0}, u_{2n}, v_{2n}, \cdots, v_{n+2}, u_{n+1}\}$. By Lemma 1.2, $f(G[A'])=f(G[B'])=2^{n}+n-1$. If

$ p(v_n)+p(u_n)+p(v_{n+1})\leq \left\lfloor\displaystyle\frac{2^{n+3}}{3}\right\rfloor+2n+ \left\lfloor\displaystyle\frac{2^{n+1}}{3}\right\rfloor-q+3, $

then

$ p(G[A'])+p(G[B'])\geq 2\left(\left\lfloor\displaystyle\frac{2^{n+3}}{3}\right\rfloor+2n\right)-q+1-(\left\lfloor\displaystyle\frac{2^{n+3}}{3}\right\rfloor+2n+\\ \left\lfloor\displaystyle\frac{2^{n+1}}{3}\right\rfloor-q+3)=2^{n+1}+2n-2. $

So

$ p(G[A'])\geq 2^n+n-1~~\textrm{or}~~p(G[B'])\geq 2^n+n-1. $

Using $2^n+n-1$ pebbles, we can move one pebble to $v_0$. This leaves

$ 2\left(\left\lfloor\displaystyle\frac{2^{n+3}}{3}\right\rfloor+2n\right)-q+1-(2^{n}+n-1) \geq \left\lfloor\displaystyle\frac{2^{n+3}}{3}\right\rfloor+2n $

pebbles on $M(C_{2n+1})$. By Lemma 1.7, we can move one additional pebble to $v_0$ so that $\widetilde{p}(v_0)=2$. Now suppose $p(v_n)+p(u_n)+p(v_{n+1})\geq \left\lfloor\displaystyle\frac{2^{n+3}}{3}\right\rfloor+2n+\left\lfloor\displaystyle\frac{2^{n+1}}{3}\right\rfloor-q+4$.

If $p(u_n)\geq 2^{n+1}$, then we can move one pebble to $v_0$ by the path $\langle u_n, u_{n-1}, \cdots, u_0, v_0\rangle$ using $2^{n+1}$ pebbles on $u_n$. This leaves $p=2\left(\left\lfloor\displaystyle\frac{2^{n+3}}{3}\right\rfloor+2n\right)-q+1-2^{n+1}$ pebbles on $C_{2n+1}$. If $q\leq 2n$, then $p\geq \left\lfloor\displaystyle\frac{2^{n+3}}{3}\right\rfloor+2n$. By Lemma 1.7, we may move one additional pebble to $v_0$ so that $\widetilde{p}(v_0)=2$. When $q\geq 2n+1$, write $q$ as $q=2n+2r+2$ if $q$ is even and as $q=2n+2r+1$ if $q$ is odd, where $r\geq 0$. Let $q_1$ be the number of occupied vertices in $A'$ and let $q_2$ be the number of occupied vertices in $B'$. Without loss of generality, we may assume $q_1\geq q_2$. We have $q_1\geq n+r+1$, and there are at least $r+1$ occupied vertices in the set $\{u_0, u_1, \cdots, u_{n-1}\}$, say $u_{i_1}, u_{i_2}, \cdots, u_{i_{r+1}}$. Using one pebble each from $u_{i_j} (1\leq j\leq r+1)$ and $2^{n+1}-(2^1+2^2+\cdots+2^{r+1})$ pebbles from $u_n$. By Lemma 1.3, we see that one pebble can be moved to $v_0$ at a cost of $2^{n+1}-(2^1+2^2+\cdots+2^{r+1})+(r+1)$ pebbles. This leaves

$ \begin{array}{ll} &2\left(\left\lfloor\displaystyle\frac{2^{n+3}}{3}\right\rfloor+2n\right)-q+1-[2^{n+1}-(2^1+2^2+\cdots+2^{r+1})+(r+1)]\\ \geq& \left\lfloor\displaystyle\frac{2^{n+3}}{3}\right\rfloor+2n+\left[\left\lfloor\displaystyle\frac{2^{n+1}}{3}\right\rfloor+(2+2^2+2^3+\cdots+2^{r+1})-3r-2\right]\\ \geq& \left\lfloor\displaystyle\frac{2^{n+3}}{3}\right\rfloor+2n \end{array} $

pebbles on $M(C_{2n+1})$ and by Lemma 1.7, we are done. If $p(u_n)=2^{n+1}-s(1\leq s\leq 2^{n+1})$, then

$ p(v_n)+p(v_{n+1})\geq \left\lfloor\displaystyle\frac{2^{n+3}}{3}\right\rfloor+2n+\left\lfloor\displaystyle\frac{2^{n+1}}{3}\right\rfloor-q+4-2^{n+1}+s=\\ 2\left\lfloor\displaystyle\frac{2^{n+1}}{3}\right\rfloor+2n-q+4+s. $

Without loss of generality, we assume $p(v_n)\geq p(v_{n+1})$. Thus

$ p(v_n)\geq \left\lfloor\displaystyle\frac{2^{n+1}}{3}\right\rfloor+n+2-\left\lfloor\frac{q}{2}\right\rfloor+\left\lceil\frac{s}{2}\right\rceil. $

For $\left\lceil \frac{s}{2}\right\rceil$ is odd, we use $2^{n+1}-2\left\lceil \frac{s}{2}\right\rceil-2$ pebbles on $u_n$ and move $\frac{1}{2}\left(\left\lceil\frac{s}{2}\right\rceil+1\right)$ pebbles from $v_n$ to $u_{n-1}$. By Lemma 1.3, we can move one pebble to $v_0$ by the path $\langle u_n, u_{n-1}, \cdots, u_0, v_0\rangle$. This leaves at least

$ \begin{array}{ll} &2\left(\left\lfloor\displaystyle\frac{2^{n+3}}{3}\right\rfloor+2n\right)-q+1-\left(2^{n+1}-\left\lceil \frac{s}{2}\right\rceil-1\right)\\ \geq& \left\lfloor\displaystyle\frac{2^{n+3}}{3}\right\rfloor+2n+\left\lfloor\displaystyle\frac{2^{n+1}}{3}\right\rfloor-2n+2 \geq \left\lfloor\displaystyle\frac{2^{n+3}}{3}\right\rfloor+2n \end{array} $

pebbles on $M(C_{2n+1})$. By Lemma 1.7, we can move one additional pebble to $v_0$ so that $\widetilde{p}(v_0)=2$. For $\left\lceil \frac{s}{2}\right\rceil$ is even, we use $2^{n+1}-2\left\lceil \frac{s}{2}\right\rceil$ pebbles on $u_n$ and move $\frac{1}{2}\left(\left\lceil\frac{s}{2}\right\rceil\right)$ pebbles from $v_n$ to $u_{n-1}$. By Lemma 1.3, we can move one pebble to $v_0$ by the path $\langle u_n, u_{n-1}, \cdots, u_0, v_0\rangle$. This leaves at least

$ \begin{array}{ll} &2\left(\left\lfloor\displaystyle\frac{2^{n+3}}{3}\right\rfloor+2n\right)-q+1-(2^{n+1}-\left\lceil \frac{s}{2}\right\rceil)\\ \geq& \left\lfloor\displaystyle\frac{2^{n+3}}{3}\right\rfloor+2n+\left\lfloor\displaystyle\frac{2^{n+1}}{3}\right\rfloor-2n+2 \geq \left\lfloor\displaystyle\frac{2^{n+3}}{3}\right\rfloor+2n\end{array} $

pebbles on $M(C_{2n+1})$. By Lemma 1.7, we can move one additional pebble to $v_0$ so that $\widetilde{p}(v_0)=2$.

Remark  Combining Theorems 2.2 and 2.3, we prove that the middle graphs of cycles have 2-pebbling property.

Given two graphs $G$ and $H$, the Cartesian product of them is denoted by $G\times H$. Its vertex set

$ V(G\times H)=\{(u, v)|u\in V(G), v\in V(H)\}, $

and $(u, v)$ is adjacent to $(u', v')$ if only if $u=u'$and $vv'\in E(H)$ or $v=v'$ and $uu'\in E(G)$.

We can depict $G\times H$ pictorially by drawing a copy of $H$ at every vertex of $G$ and joining each vertex in one copy of $H$ to the corresponding vertex in an adjacent copy of $H$. We write $u(H)$ (respectively, $v(G)$) for the subgraph of vertices whose projection onto $V(G)$ is the vertex $u$, (respectively, whose projection onto $V(H)$ is the vertex $v$). Obviously, $u(H)\cong H$, $v(G)\cong G$.

Conjecture 3.1  (Graham) For any two graphs $G$ and $H$, $f(G\times H)\leq f(G)f(H)$.

Lemma 3.2(see [7])  Let $P_n$ be a path with $n$ vertices and let $G$ be a graph with the 2-pebbling property. Then $f(P_n\times G)\leq 2^{n-1}f(G)$.

Theorem 3.3  Let $P_n$ be a path with $n$ vertices and let $G$ be a graph with the 2-pebbling property. Then $f(M(P_n)\times G)\leq (2^n+n-2)f(G)$.

Proof  Let $P_{n}=\langle v_1, v_2, \cdots, v_{n}\rangle$. $M(P_{n})$ is obtained from $P_{n}$ by inserting $u_i$ into $v_iv_{i+1}$, and joining $u_iu_{i+1}$ for $1\leq i\leq n-1$. Now we assume that $(2^n+n-2)f(G)$ pebbles have been distributed arbitrarily on the vertices of $M(P_n)\times G$. Let $p_i=p(v_i(G))$, where $1\leq i\leq n$. Let $q_i$ be the number of occupied vertices in $v_i(G)(1\leq i\leq n)$. Suppose that $v$ is our target vertex in $M(P_n)\times G$.

Case 1   $v=(v_n, x)\in v_n(G)$ (or $v=(v_1, x)\in v_1(G)$) for $x\in V(G)$. For simplicity, let $A=\langle u_1, u_2, \cdots, u_{n-1}, v_{n}\rangle$. By Lemma 3.2, $f(A\times G)\leq 2^{n-1} f(G)$. If $\sum\limits_{i=1}^{n-1}p_i\leq (2^n+n-3)f(G)$, then the $A\times G$ can obtain at least

$ \displaystyle\frac{1}{2}\left [(2^n+n-3)f(G)-(n-1)f(G)\right]+f(G)=2^{n-1}f(G) $

pebbles by a sequence of pebbling moves and we are done. Next we assume that $\sum\limits_{i=1}^{n-1}p_i\geq (2^n+n-3)f(G)+1$. Thus $p(A\times G)<f(G)$. Let $p(A\times G)=\alpha_0f(G)$ where $0\leq \alpha_0<1$ and let $p(v_i(G))=(j_i+\alpha_i)f(G)(1\leq i\leq n-1)$ where $j_i\geq 0$ and $0\leq \alpha_i<1$.

Now we claim that $\sum\limits_{i=1}^{n-1}q_i>(n-2+\alpha_0)f(G)$. Otherwise, we have $\sum\limits_{i=1}^{n-1}q_i\leq (n-2+\alpha_0)f(G)$. Hence

$ \widetilde{p}(A\times G)\geq \frac{1}{2}\left[(2^n+n-2)f(G)-\alpha_0f(G)-(n-2+\alpha_0)f(G)\right]+\alpha_0f(G)\geq 2^{n-1}f(G) $

and we are done. Let $\sum\limits_{i=0}^{n-1}\alpha_i=s\leq n-1$. Then $\sum\limits_{i=1}^{n-1}j_i=2^n+n-2-s$. Note that $\alpha_if(G)+q_i<2f(G)$ for $1\leq i\leq n-1$. We claim that there exist $i_1, i_2, \cdots, i_s$ such that $i_k\geq 1$ and $\alpha_{i_k}f(G)+q_{i_k}>f(G)$, where $k=1, 2, \cdots, s$. Otherwise, we have

$ \begin{array}{ll} \sum\limits_{i=1}^{n-1}(\alpha_if(G)+q_i)&\leq 2(s-1)f(G)+[n-1-(s-1)]f(G)\\&=(n-2)f(G)+sf(G). \end{array} $

But

$ \begin{array}{ll} \sum\limits_{i=1}^{n-1}(\alpha_if(G)+q_i)&=\sum\limits_{i=1}^{n-1}\alpha_if(G)+\sum\limits_{i=1}^{n-1}q_i\\ &> (s-\alpha_0)f(G)+ (n-2+\alpha_0)f(G)\\ &=(n-2)f(G)+sf(G). \end{array} $

It is a contradiction.

Let $B=\langle(v_1, x), (v_2, x), \cdots, (v_n, x)\rangle$. Note that $\sum\limits_{i=1}^{n-1}j_i=2^n+n-2-s\geq n-1$. Without loss of generality, we may assume that $j_i\geq 1$ for $1\leq i\leq n-1$. And we may assume (after relabeling if necessary) that $\alpha_if(G)+q_i>f(G)$ for $1\leq i\leq s$. Hence by the 2-pebbling property we can move at least $j_{i}+1$ pebbles to the vertex $(v_{i}, x)$ in $v_{i}(G) (1\leq i\leq s)$. In $v_{i}(G) (s\leq i\leq n-1)$, we can move at least $j_i$ pebbles to the vertex $(v_i, x)$. Then

$ \widetilde{p}(M(B))\geq \sum\limits_{i=1}^s(j_i+1)+\sum\limits_{i=s+1}^{n-1}j_i =\sum\limits_{i=1}^{n-1}j_i+s\geq 2^n+n-2 $

and we are done by Lemma 1.2.

Case 2   $v=(v_k, x)\in v_k(G)$ ( $k\neq 1, n$) for $x\in V(G)$. Obviously, $n\geq 2$ and $p_k<f(G)$. For simplicity, let $A'=\langle u_1, u_2, \cdots, u_{n-1}\rangle$. By Lemma 3.2, $f(A'\times G)\leq 2^{n-2}f(G)$. If $\sum\limits_{i\neq k}p_i\leq (2^n+n-3)f(G)-2p_k$, then $A'\times G$ and $v_k(G)$ can obtain at least

$ \displaystyle\frac{1}{2}\left [(2^n+n-3)f(G)-2p_k-(n-1)f(G)\right]+f(G)+2p_k=2^{n-1}f(G)+p_k $

pebbles by a sequence of pebbling moves, i.e., $\widetilde{p}(A'\times G)\geq 2^{n-1}f(G)$. Thus we can move at least two pebbles to the vertex $(u_{k-1}, x)$ of $u_{k-1}(G)$ and one pebble can be moved to $v$ from $(u_{k-1}, x)$. Next we assume that $\sum\limits_{i\neq k}p_i>(2^n+n-3)f(G)-2p_k$. Thus $p(A'\times G)+p_k<f(G)+2p_k$, i.e., $p(A'\times G)<f(G)+p_k$. Let $p(A'\times G)=\alpha_0f(G)$ and let $p(v_i(G))=(j_i+\alpha_i)f(G)(1\leq i\leq n)$, where $j_i\geq 0$ and $0\leq \alpha_i<1$. Obviously, $0\leq \alpha_0<2$ and $j_k=0$.

Now we claim that $\sum\limits_{i=1}^n q_i>(n-2+\alpha_0)f(G)$. Otherwise, we have $\sum\limits_{i=1}^nq_i\leq (n-2+\alpha_0)f(G)$. Hence

$ \begin{array}{ll} \widetilde{p}(A'\times G)&\geq \displaystyle\frac{1}{2}\left[(2^n+n-2)f(G)-\alpha_0f(G)-(n-2+\alpha_0)f(G)\right]+\alpha_0f(G)\\&=2^{n-1}f(G) \end{array} $

and we are done. Let $\sum\limits_{i=0}^n\alpha_i=s\leq n+1$. Then $\sum\limits_{i=1}^n j_i=2^n+n-2-s$. Note that $\alpha_if(G)+q_i<2f(G)$ for $1\leq i\leq n$. We claim that there exist $i_1, i_2, \cdots, i_{s-1}$ such that $i_k\geq 1$ and $\alpha_{i_k}f(G)+q_{i_k}>f(G)$, where $k=1, 2, \cdots, s-1$. Otherwise, we have

$ \begin{array}{ll} \sum\limits_{i=1}^n(\alpha_if(G)+q_i)&\leq 2(s-2)f(G)+[n-(s-2)]f(G)\\&=(n-2)f(G)+sf(G). \end{array} $

But

$ \begin{array}{ll} \sum\limits_{i=1}^n(\alpha_if(G)+q_i)&=\sum\limits_{i=1}^n\alpha_if(G)+\sum\limits_{i=1}^nq_i\\ &> (s-\alpha_0)f(G)+ (n-2+\alpha_0)f(G)\\ &=(n-2)f(G)+sf(G). \end{array} $

It is a contradiction.

Let $B'=\langle(v_1, x), (v_2, x), \cdots, (v_n, x)\rangle$. Note that $\sum\limits_{i\neq k}j_i=2^n+n-2-s\geq n-1$. Without loss of generality, we may assume that $j_i\geq 1$ for $ i\neq k$. And we may assume (after relabeling if necessary) that $\alpha_if(G)+q_i>f(G)$ for $1\leq i\leq s$. Hence by the 2-pebbling property we can move at least $j_{i}+1$ pebbles to the vertex $(v_{i}, x)$ of $v_{i}(G) (1\leq i\leq s-1)$. And we can move at least $j_i$ pebbles to the vertex $(v_i, x)$ of $v_{i}(G)$, where $i=s, \cdots, k-1, k+1, \cdots, n$. Then

$ \widetilde{p}(M(B'))\geq \sum\limits_{i=1}^{s-1}(j_i+1)+\sum\limits_{i=s}^{k-1}j_i+\sum\limits_{i=k+1}^nj_i =\sum\limits_{i\neq k}j_i+s-1\geq 2^n+n-3. $

Let $C'=\langle(v_1, x), (u_1, x), \cdots, (u_{k-1}, x), (v_k, x)\rangle$. If $\widetilde{p}((v_1, x))\geq 2^{n-1}$ and $d((v_1, x), (v_k, x))\leq n-1$, then one pebble can be moved to $(v_k, x)$ by the path $C'$.

On the other hand, if $\widetilde{p}((v_1, x))\leq 2^{n-1}-1$, then

$ \widetilde{p}(M(B')-(v_1, x))\geq 2^{n-1}+n-2. $

By Lemma 1.5, we are done.

Case 3   $v=(u_k, x)\in u_k(G)$ for $x\in V(G)$. The proof is similar to the proof of Case 1.

By Theorem 2.1 and Theorem 3.3, we can have the following result.

Corollary 3.4  Let $P_n$ and $P_m$ be two paths. Then

$ f(M(P_n)\times M(P_m))\leq f(M(P_n))f(M(P_m)). $