% Pebbling paper: revised.
%
% David Moews moews@zariski.harvard.edu
%
%----------------------------cut here------------------------------------
% Last revision Dec 21 1988 by DJM.
\documentstyle[12pt]{article}
\begin{document}
% Integers and reals
\newcommand{\Z}{\mbox{\sf Z\hspace{-5.5pt}Z}}
\newcommand{\z}{\mbox{\footnotesize \sf Z\hspace{-4.1pt}Z}}
\newcommand{\R}
{\mbox{\sf R\makebox[0pt][r]{\rule{.25pt}{8pt}\rule{4.5pt}{0pt}}}}
% Floor and ceiling
\def\floor#1{\left\lfloor#1\right\rfloor}
\def\ceil#1{\left\lceil#1\right\rceil}
% Environments.
\newtheorem{theorem}{Theorem}
\newtheorem{lemma}[theorem]{Lemma}
\newenvironment{proof}{\paragraph{Proof. }}{\qquad\rule{0.5em}{2ex}}
% Greek letters
\def\a{\alpha}
\def\b{\beta}
\def\g{\gamma}
\def\D{\Delta}
\def\kd{\delta}
\def\d{\theta}
\def\e{\epsilon}
% Number of pebbles on a vertex
\def\N{{\cal N}}
% Title
\title{Pebbling Graphs}
\author{David Moews\\Department of Mathematics\\Harvard University
\\Cambridge, MA 02138}
\maketitle
\section{Introduction.}
Consider an arbitrary digraph $G$, with pebbles placed on some of its
vertices. Suppose that, for any directed edge $(v,w)$ of $G$,
we are allowed to change the configuration of
pebbles by removing two pebbles from $v$ and placing one pebble on $w$.
Then for a vertex $v$ of $G$, if $n$ exists such that, however $n$
pebbles are placed on $G$, one pebble can always be moved to $v$,
we let $f(v,G)$ be the smallest such $n$.
The {\it pebbling number} of an
undirected graph
$G$,
$f(G)$, is $\max_{v \in V(G)} f(v,G)$. It is conjectured
by Ronald Graham (see [1])
that for all graphs
$G$ and $H$, $f(G \times H) \le f(G) f(H)$. We will prove this
when $G$ and
$H$ are trees, and compute $f(G)$ exactly for some graphs $G$.
\section{Pebbling products.}
Let $T$ be a tree and let
$v$ be a vertex of $T$. Let $T_v^*$ be the rooted
tree obtained from $T$ by directing all edges towards $v$. A
{\it path-partition} of a rooted tree $U$ is a partition of the edges of
$U$ such that each set of edges in the partition forms a directed path.
A {\it maximum path-partition} of a rooted tree $U$ with height $n$ is
a path-partition $P$ of $U$ such that every path in $P$ touches a leaf,
and, for all $0 \le m \le n$, if we consider the vertex-induced subtree
$U'$ of $U$ induced by the set of all leaves of level $m$ or greater
and ancestors of these leaves, then $\{P_0 \in P | P_0 \subseteq E(U')\}$
is a path-partition of $U'$. The {\it path-size sequence} of a
path-partition $\{P_1, \dots, P_n\}$ is an $n$-tuple $(a_1, \dots, a_n)$,
where $a_j$ is the number of edges in $P_j$ and the $P_j$'s are ordered
so that
$a_1 \ge a_2 \ge \dots \ge a_n$.
If we have a maximum path-partition $P$ of a rooted tree $U$
with height $h$, let $U'$ be the subtree of $U$ induced by all leaves
of level $h$ and their ancestors. Then some subset of $P$ is a
path-partition of $U'$, so some path in $P$ must run from a leaf
of level $h$ to the root. Hence if $(a_1, \dots, a_n)$ is the
path-size sequence of a maximum path-partition of $U$, we must have $a_1=h$.
If we have a digraph $G$ with some pebbles placed on it, we let $p$ be the total
number of pebbles on $G$ and $q$ be the number of vertices of $G$
with an odd number of pebbles. If $G$ is a digraph and
$v$ is a vertex of $G$,
we say that $(G,v)$ can be $(\a,\b,\g)$-pebbled if
\begin{enumerate}
\item For all $m\ge1$, if $p \ge \a+(m-1)\b$, then $m$ pebbles can be
moved to $v$.
\item For all $m\ge2$, if $p+q>2\g+(m-2)\b$, then $m$ pebbles can be
moved to $v$.
\end{enumerate}
\begin{theorem}
Let $U$ be a rooted tree with root $v$ and let $G$ be a digraph
with $w$ a vertex of $G$.
If $(G,w)$ can be $(\a,\b,\g)$-pebbled,
then $(U\times G,(v,w))$ can be $(X+\a,\b2^h,X+\max(\a,\g))$-pebbled, where
$$
X = \g\sum_{j=1}^p d_j + \b\sum_{j=1}^p (2^{d_j}-d_j-1),
$$
$h$ is the height of $U$, and $(d_1, \dots, d_p)$ is the path-size sequence
of any maximum path-partition of $U$.
\end{theorem}
\begin{proof}
We induct on $h$. If $h$ is zero,
the result follows trivially. Otherwise let $P$ be a maximum path-partition
of $U$, and let
$U'$ be the subtree of $U$
induced by the set of all vertices of level less than $h$. Then $\{
P_0 \cap E(U') \ne \emptyset|
P_0 \in P\} = P'$, say, is a path-partition of $U'$.
It can easily be seen that $P'$ is maximum.
Let $v_1, \dots, v_n$ be the vertices in $U$ which are parents of leaves
of level $h$. Then
in $P'$ there is a path to each $v_j$, $P_j$ say; let $a_j$ be the number of
edges in $P_j$. If $b_1, \dots, b_m$ are the lengths of the
remaining
paths in $P'$, then the induction hypothesis says that $((v,w),U'\times G)$
can be $(X'+\a,\b2^{h-1},X'+\max(\a,\g))$-pebbled, where
$$
X' = \g(\sum_{i=1}^n a_i + \sum_{j=1}^m b_j )
+ \b\sum_{i=1}^n (2^{a_i}-a_i-1) + \b\sum_{j=1}^m (2^{b_j}-b_j-1).
$$
Now $U$ can be obtained from $U'$ by adding leaves to $v_1, \dots, v_n$.
Suppose we add $L$ leaves in all. Then the path-partition $P$ must consist
of
the paths of lengths $b_1, \dots, b_m$, combined
with the paths $P_1, \dots, P_n$, each augmented by an edge from $v_j$ to
one of its leaves, and $L-n$ one-edge paths from the
$v_j$'s to their other leaves. Hence we have
\begin{eqnarray*}
X &=& \g(\sum_{i=1}^n a_i + \sum_{j=1}^m b_j + L)
+ \b\sum_{i=1}^n (2^{a_i+1}-a_i-2) + \b\sum_{j=1}^m (2^{b_j}-b_j-1) \\
&=& X' + \g L+\b\sum_{i=1}^n(2^{a_i}-1).
\end{eqnarray*}
Now since $P$ is maximum, the augmented
$P_j$'s together with these $L-n$ one-edge paths
must form a path-partition for the subtree $U_0$ of $U$ induced by the leaves
of degree $h$ and their ancestors. Hence if we let $U_0'$ be the subtree of
$U'$ induced by the $v_j$'s and their ancestors,
the $P_j$'s must form a path-partition of $U_0'$.
Then if we set $G$ equal to the trivial graph
and use the induction hypothesis,
since the trivial graph can be $(1,1,1)$-pebbled, we find
that $U_0'$ can be $(Q,2^{h-1},Q)$-pebbled, where
$$
Q = \sum_{i=1}^n 2^{a_i} -n+1.
$$
Now, first, let $m\ge1$. We will prove that if $p\ge X+\a+\b2^h(m-1)$, then
$m$ pebbles can be moved to $(v,w)$. Let $l_1,\dots,l_L$ be the level-$h$
leaves of $U$, and let $p'$ be the number of pebbles in $U'\times G$ and
$p_k$ be the number of pebbles in $\{l_k\}\times G$, where $1\le k\le L$.
Define $q'$ and $q_k$ similarly. Then if
$$
p' + \sum_{k=1}^L {{p_k-q_k}\over2} \ge X'+\a+\b2^{h-1}(m-1),
$$
we will be done, since for each vertex $x \in L_k$, $y \in G$, we can take two
pebbles off $(x,y)$ and put one pebble on some $(v_i,y)$. Hence for each $k$,
we can take $p_k-q_k$ pebbles from $\{l_k\} \times G$ and move $(p_k-q_k)/2$
pebbles into $U' \times G$. Then we will have a total of at least
$X'+\a+\b2^{h-1}(m-1)$ pebbles in $U'\times G$, and will be able to
move one pebble to
$(v,w)$, by the induction hypothesis.
Otherwise, since $p\ge X+\a+\b2^h(m-1)$, we will have
\begin{eqnarray*}
\sum_{k=1}^L {{p_k+q_k} \over 2} &=&
p - p' - \sum_{k=1}^L {{p_k-q_k} \over 2} \\
&>&
(X+\a+\b2^h(m-1))-(X'+\a+\b2^{h-1}(m-1)) \\
&=& (X-X')+\b2^{h-1}(m-1),
\end{eqnarray*}
so
$$
\sum_{k=1}^L (p_k+q_k) > 2(X-X')+\b2^h(m-1).
$$
Now for each $k$, if
$p_k+q_k > 2\g+(r-2)\b$, we can take pebbles from $\{l_k\} \times G$
and move $r$ pebbles to $(l_k, w)$, by hypothesis.
Hence if $(p_k+q_k-2\g)/2\b>r\ge0$, we can move $2r+2$ pebbles to $(l_k,w)$
and then $r+1$ pebbles from $(l_k,w)$
into $\{v_1, \dots, v_n\} \times \{w\}$, so we can move at least
$(p_k+q_k-2\g)/2\b$ pebbles into $U_0'\times \{w\}$.
But then, doing this for
all $k$, we can put at least
$$
\sum_{k=1}^L {{p_k+q_k-2\g}\over{2\b}}
$$
pebbles in $U_0' \times \{w\}$, and then
\begin{eqnarray*}
\sum_{k=1}^L {{p_k+q_k-2\g}\over{2\b}} &=&
{\sum_{k=1}^L (p_k+q_k)-2\g L}\over{2\b} \\
&>& {2(X-X')+\b2^h(m-1)-2\g L}\over{2\b}\\
&=& {2\b\sum_{i=1}^n(2^{a_i}-1)+\b2^h(m-1)}\over{2\b}\\
&=& \sum_{i=1}^n(2^{a_i}-1)+2^{h-1}(m-1)\\
&=& Q-1+2^{h-1}(m-1),
\end{eqnarray*}
so we can move $m$ pebbles to $(v,w)$, since $U_0'$ can be
$(Q,2^{h-1},Q)$-pebbled.
Now we will prove that for all $m \ge 2$, if $p+q>2\max(\a,\g)+2X+(m-2)\b2^h$,
then $m$ pebbles
can be moved to $(v,w)$. If $p'+q'>2\max(\a,\g)+2X'+(m-2)\b2^{h-1}$,
then we are done, by the induction hypothesis.
Otherwise, suppose that for some $l \in \{3, \dots, m\}$,
\begin{eqnarray*}
2\max(\a,\g)+2X'+(l-2)\b2^{h-1}-q'&\ge& p'\\
&>&2\max(\a,\g)+2X'+(l-3)\b2^{h-1}-q'.
\end{eqnarray*}
Then we can move $l-1$ pebbles to $(v,w)$ in $U'\times G$. Also, we have
\begin{eqnarray*}
p+q-p'-q' &>& 2(X-X') + (m-2)\b2^h-(l-2)\b2^{h-1} \\
&=& 2(X-X')+(2m-l-2)\b2^{h-1},
\end{eqnarray*}
so as in the first part, we can move $\floor{(2m-l-2)/2}+1$ pebbles to
$(v,w)$, giving a total of
$$
\floor{{2m-l-2}\over 2}+1+l-1=m-1+l-\ceil{l \over 2},
$$
but since $l\ge 2$, $1+l/2\le l$ and we are done.
If
$$
2\max(\a,\g)+2X'-q'\ge p'\ge X'+\a,
$$
then we can proceed as above with $l=2$.
Suppose finally
that $p' 2(X-X')+\b2^h(m-2).
\end{equation}
For (1) to hold, we need
\begin{equation}
\sum_{k=1}^L p_k -\sum_{k=1}^L q_k + 2p' \ge 2X'+2\a,
\end{equation}
but
\begin{eqnarray*}
\sum_{k=1}^L p_k-\sum_{k=1}^L q_k + 2p' &\ge&p'+q'+\sum_{k=1}^L p_k
-\sum_{k=1}^L q_k\\
&=& p+q-2\sum_{k=1}^L q_k\\
&\ge& p+q-2L|V(G)|.
\end{eqnarray*}
Now if we put one pebble on each vertex of $G$, no movement can be done,
so we cannot move 2 pebbles to any vertex. In this case $p+q=2|V(G)|$.
Hence $\g\ge|V(G)|$, and
\begin{eqnarray*}
\sum_{k=1}^L p_k-\sum_{k=1}^L q_k + 2p' &\ge&p+q-2L\g\\
&>&2\max(\a,\g)+2X+\b2^h(m-2)-2L\g.
\end{eqnarray*}
But $X-X'\ge\g L$, so (\theequation) holds.
For (2), we need
$$
\sum_{k=1}^L (p_k+q_k)+2p' > 2X+2\a+\b2^h(m-2),
$$
but this follows from
$$
\sum_{k=1}^L (p_k+q_k)+2p' \ge \sum_{k=1}^L (p_k+q_k)+p'+q'=p+q,
$$
so we are done.
\end{proof}
\begin{theorem}
If we have a graph $G$ with a certain configuration
of pebbles
and a vertex $v$ of $G$ and wish to move $m$ pebbles to $v$, then there always
exists an acyclic orientation $H$ for $G$ such that $m$ pebbles can still
be moved to $v$ in $H$.
Furthermore, if $G$ is a tree, we can take $H=G_v^*$;
hence for all trees $T$ and vertices $v$ of $T$, $f(v,T)=f(v,T_v^*)$.
\end{theorem}
\begin{proof}
Suppose we have a graph $G$ with pebbles on its vertices,
and suppose we wish to move $m$ pebbles to $v$. Take a sequence of directed
edges, $(e_1, \dots, e_p)$, where pebbling along each $e_j$ in sequence
moves $m$ pebbles to $v$. Now suppose we allow negative numbers of pebbles
to reside on vertices, so that pebbling along $(x,y)$ is always possible,
and subtracts 2 from the pebble count on $x$ and adds 1 to the pebble
count on $y$. Then if, in $(e_1, \dots, e_p)$, we find an edge $(x,y)$
followed by $(y,x)$, or a cycle of directed edges, delete the pair or cycle.
After pebbling along $(e_1,\dots,e_p)$ the counts are all nonnegative and
at least $m$ pebbles end up on $v$. Deleting pairs or cycles
only increases these counts, since a pair or cycle has the net effect
of removing 1 pebble from each of its vertices. After we have deleted
all pairs and cycles present, then, we are left with a sequence of edges
$(f_1, \dots, f_n)$ that puts $m$ pebbles on $v$ when pebbled along,
except that a
pebble count on some vertex may be temporarily negative. But since there
are no cycles present, if we order the vertices of $G$ by $v \prec w$ if
there is an edge $f_j$ from $v$ to $w$, and then take the transitive
closure,
we obtain a partial order.
Extend this to a linear order $\prec$ of $V(G)$.
Then if we reorder the $f_j$'s such that $(x,y)$ is placed before
$(z,w)$ if $x\prec z$, no edge $(y,z)$ can occur before an edge $(x,y)$,
since if it did we would have $y\prec x$ and $x\prec y$. Hence in this
reordering of the $f_j$'s, a vertex $y$ is only pebbled out of after
all pebbling into it has been done; then there are no problems with
intermediate counts being negative, and if we pick our orientation $H$
to have $E(H)=\{(x,y)|x\prec y,\{x,y\}\in E(G)\},$ we will be able to
move $m$ pebbles to $v$ in $H$.
If $G$ is a tree, we can always choose to direct all edges towards $v$,
for if not, let $(x,y)$ be an edge directed away from $v$. Then no
pebbles can ever pass from the subtree of $G$ rooted at $y$ into
the rest of $G$ (which contains $v$), so any pebbling steps along $(x,y)$
can be omitted without decreasing the number of pebbles arriving at $v$.
Then if $(x,y)$ is never pebbled, we might as well direct it the other
way. Repeating this, we can direct all edges in $G$ towards $v$.
\end{proof}
\bigskip % Set off definition
If we have a digraph $G$ with pebbles on its vertices, we denote the
number of pebbles on a vertex $v$ of $G$ by $\N(v)$.
\begin{theorem}
Let $G$ be a digraph and let $S\subseteq V(G)$. If $v\in S$ and
\begin{equation}
\sum_{d(w,v)<\infty, \ w\in S} \N(w) 2^{-d(w,v)} < m,
\end{equation}
then $m$ pebbles cannot be moved to $v$ by pebbling within $S$.
\end{theorem}
\begin{proof}
The left-hand side of (\theequation) cannot
increase when a pebbling move is made within $S$, since when we move
from vertex $w$ to vertex $w'$, $d(w',v)\ge d(w,v)-1$. But if $m$ pebbles
were on $v$, then the left-hand side of (\theequation) would be at least $m$,
so we must not be able to move $m$ pebbles to $v$.
\end{proof}
\begin{theorem}
Let $U$ be a rooted tree and let $v$ be the root of $U$.
If the path-size sequence of a maximum path-partition for $U$ is
$(a_1, \dots, a_n)$, then
$$
f(v,U)=\sum_{i=1}^n 2^{a_i} - n+1.
$$
Furthermore, $U$ can be
\begin{equation}
\left(
\sum_{i=1}^n 2^{a_i} - n+1, 2^{a_1}, 2^{a_1}+\sum_{i=2}^n 2^{a_i-1}
\right)-
\hbox{pebbled.}
\end{equation}
\end{theorem}
\begin{proof}
Let $\{P_1, \dots, P_n\}$ be a maximum path-partition for $U$.
The $a_j$ edges in $P_j$ will touch $a_j+1$
vertices. Let $Q_j\subseteq V(U)$ contain
the $a_j$ of these vertices furthest from $v$,
and let $v_j$ be the vertex in $Q_j$ furthest from $v$.
The $Q_j$'s are disjoint and do not contain $v$.
Put $2^{a_j}-1$ pebbles on $v_j$ for each $j$. With this initial
configuration of pebbles, we cannot move 2 pebbles from $Q_j$ to the
vertex of $Q_j$ nearest the root (by Theorem 3), so we cannot
move pebbles out of any $Q_j$, and in particular,
we cannot put a pebble on $v$, which is not in any $Q_j$.
Hence
$$
f(v,U) > \sum_{i=1}^n 2^{a_i} - n.
$$
Now in Theorem 1, set $G$ equal to the trivial graph. Then $G$
can be $(1,1,1)$-pebbled, so $(U,v)$ can be
\begin{equation}
\left(
\sum_{i=1}^n 2^{a_i}-n+1, 2^{a_1}, \sum_{i=1}^n 2^{a_i}-n+1
\right)-
\hbox{pebbled.}
\end{equation}
In particular, $f(v,U)$ is as desired. Now suppose we have
put some pebbles on $U$. Since for every $w \in V(U)$
there is only one pebbling move that can be made out of $w$,
the number of pebbles we will be able to move to $v$ will not
be increased
if we take a pebble of some vertex $w$ and put 2 pebbles
on one of $w$'s children (since we will just move them back to $w$),
and it clearly will not be decreased. Now if $q>n$, there are
at least $q-n$ nonleaf vertices containing at least one pebble; we
can take one pebble off each of these vertices and put 2 pebbles on
one of the children of each of these vertices without affecting the
number of pebbles we can move to $v$. But doing this increases $p$
by $q-n$, and by (\theequation), if
$$
p \ge \sum_{i=1}^n 2^{a_i}-n+1 + 2^{a_1}(m-1),
$$
we can move $m$ pebbles to $v$. Hence if
$$
p+q \ge \sum_{i=1}^n 2^{a_i}-n+1 + 2^{a_1}(m-1)+n,
$$
we can also move $m$ pebbles to $v$, so we can take
$$
2\g = \sum_{i=1}^n 2^{a_i}-n+1 + 2^{a_1}+n-1, \hbox{ or }
\g = 2^{a_1} + \sum_{i=2}^n 2^{a_i-1},
$$
as desired.
\end{proof}
\begin{theorem}
If $T_1, \dots, T_n$ are (undirected) trees, then
$$
f(T_1\times\dots\times T_n)\le f(T_1)\dots f(T_n).
$$
\end{theorem}
\begin{proof}
We will show that for all $v_j\in V(T_j)$,
\begin{equation}
f((v_1,\dots,v_n),T_{1v_1}^*\times\dots \times T_{nv_n}^*)
\le f(v_1,T_{1v_1}^*)\dots f(v_n,T_{nv_n}^*).
\end{equation}
This will imply the desired result, since by Theorem 2, $f(v,T_v^*)=f(v,T)$,
if $T$ is a tree and $v$ is a vertex of $T$.
Theorem 1 tells us that for a digraph $G$ and a vertex $w$ of $G$,
if $(G,w)$ can
be $(\a,\a,\a)$-pebbled, then for a rooted tree $U$ with root $v$,
$(U\times G,(v,w))$ can be $(X,2^{b_1}\a,X)$-pebbled, where
$$
X=\a(\sum_{j=1}^m 2^{b_j} -m +1),
$$
and $(b_1,\dots,b_m)$ is the path-size sequence of a maximum path-partition
for $U$. Then $X \ge 2^{b_1}\a$, so $(U\times G,(v,w))$ can be
$(X,X,X)$-pebbled, and by Theorem 4,
$X=\a f(v,U)$.
Then, since the trivial graph can be $(1,1,1)$-pebbled, we can induce
to find that for rooted trees $U_1,\dots,U_n$ with roots $v_1,\dots,v_n$,
$((v_1,\dots,v_n),U_1\times\dots\times U_n)$ can be $(Y,Y,Y)$-pebbled, where
$$
Y = f(v_1,U_1) \dots f(v_n,U_n).
$$
This implies (\theequation), so we are done.
\end{proof}
\section{Exact pebbling numbers.}
Let $P_n^*$ be the digraph with $V(P_n^*)=\{p_1,\dots,p_n\}$ and
$E(P_n^*)=\{(p_1,p_2),\dots,(p_{n-1},p_n)\}.$
\begin{theorem}
Let $U$ be a rooted tree and let $v$ be the root of $U$.
If the path-size sequence of a maximum path-partition for $U$ is
$(a_1, \dots, a_n)$, then
\begin{equation}
f((v,p_m), U\times P_m^*) = 2^{m-1+a_1} + (m-1)\sum_{j=2}^n 2^{a_j-1}
+ \sum_{j=2}^n 2^{a_j} - (n-1).
\end{equation}
\end{theorem}
\begin{proof}
Setting
$G=U$ and $U=P_n^*$ in Theorem 1, and using (5),
we find that the left-hand side of (\theequation) is
no bigger than the right-hand side. For the other direction, let
$Q_j$ and
$v_j$ be as in Theorem 4. Put $2^{a_j}-1$ pebbles on $(v_j,p_1)$
and
$2^{a_j-1}$ pebbles on $(v_j,p_k)$, where
$j=2,\dots,n$ and $k=2,\dots,m$.
Also,
put $2^{m-1+a_1}-1$ pebbles on $(v_1,p_1)$. Then we claim that no pebble
can be moved out of $Q_j\times P_m^*$, $j=2,\dots,n$, and that in
$(Q_1\cup\{v\})\times P_m^*$, no pebble can be moved to $(v,p_m)$.
This will imply that in (\theequation), the left-hand side is at least as
big as the right-hand side.
Suppose a pebble could be moved out of $Q_j\times P_m^*$ for some $j>1$.
Then we would
have to move two pebbles to some $(w_j,p_k)$, where $w_j$ is the vertex
of $Q_j$ nearest to $v$ and $k\in\{1,\dots,m\}$. But
\begin{eqnarray*}
& &\sum_{x\in Q_j\times P_m^*, \ d(x,(w_j,p_k))<\infty}
\N(x) 2^{-d(x,(w_j,p_k))} \\
&=& (2^{a_j}-1)2^{-(a_j-1)-(k-1)} + \sum_{l=0}^{k-2} 2^{a_j-1}2^{-(a_j-1)-l} \\
&<& 2^{-(k-2)} + \sum_{l=0}^{k-2} 2^{-l} = 2,
\end{eqnarray*}
so by Theorem 3, this movement cannot be made. Hence no pebbles can
be moved out of $Q_j\times P_m^*$. Similarly, in $(Q_1\cup\{v\})\times P_m^*$,
Theorem 3 prevents a pebble from being moved to $(v,p_n)$, so we cannot
move a pebble to $(v,p_n)$, and we are done.
\end{proof}
\begin{theorem}
Let $G$ be a graph of order $m$ with diameter $\D$. Then for $n>3(2^\D-1)m$,
$$
f(K_n\times G)=mn.
$$
\end{theorem}
\begin{proof}
Let $G$ be a graph of order $m$ with diameter $\D$,
and let $n>3(2^\D-1)m$.
For all graphs $H$, $f(H)\ge |V(H)|$, so it is
clear that $f(K_n\times G)\ge mn$. Suppose there are at least
$mn$ pebbles
on the vertices of $K_n\times G$. We will show that we can move
a pebble to any $(y,v)\in V(K_n\times G)$. If $w\in V(G)$ exists with
\begin{equation}
\sum_{x\in V(K_n)} \floor{\N(x,w) \over 2} \ge 2^{\D},
\end{equation}
we will be able to move $2^{\D}$ pebbles to $(y,w)$ and hence at least
$1$ pebble
to $(y,v)$. Hence we can assume that for all $w$,
$$
2^{\D}-1\ge \sum_{x\in V(K_n)} \floor{\N(x,w) \over 2}
\ge \sum_{x\in V(K_n), \ \N(x,w)\ge 2} {\N(x,w)-1 \over 2}.
$$
However, if (\theequation) does not hold, there can be at most $2^{\D}-1$
$x$'s with $\N(x,w)\ge 2$, so
$$
\sum_{x\in V(K_n), \ \N(x,w)\ge 2} \N(x,w)
\le 2(2^\D-1) + (2^\D-1) = 3(2^\D-1).
$$
Then
$$
\sum_{(x,w)\in V(K_n\times G), \ \N(x,w)\ge 2} \N(x,w) \le 3(2^\D-1)m,
$$
so at least $mn-3(2^\D-1)m$ vertices of $K_n\times G$ have exactly 1 pebble
on them, and at most $3(2^\D-1)m$ do not. But $n>3(2^\D-1)m$, so there must
be some $x\in V(K_n)$ such that every $\N(x,w)=1$. Then since there
are at least
$mn$ pebbles on $K_n\times G$, if there is not already a pebble
on $(y,v)$, there must be at least
$2$ pebbles on some vertex, $(\bar x,\bar w)$
say. Then we can move a pebble to $(x,\bar w)$, and
pebbling from $(x,w_1)$ to $(x,w_2)$, $\dots$, $(x,w_{q-1})$ to $(x,w_q)$,
where $(\bar w=w_1,\dots,w_q=v)$ is a path in $G$, we get 2 pebbles
on $(x,v)$, so we can move a pebble to $(y,v)$, as desired.
\end{proof}
\begin{lemma}
If we have put pebbles on the vertices of $P_n^*$
in such a way that
$$
\sum_{i=1}^n \N(p_i) 2^{-(n-i)} \ge 1,
$$
then we can pebble $p_n$.
\end{lemma}
\begin{proof}
By the same argument as in Theorem 4, whether or not
we can pebble $p_n$ will be unchanged if we take a pebble off $p_j$ and
put two pebbles on $p_{j-1}$. Doing this repeatedly, we get
$$
\sum_{i=1}^n \N(p_i) 2^{i-1}
$$
pebbles on $p_1$. But by hypothesis, this number is at least $2^{n-1}$,
so we can clearly pebble $p_n$; hence we are done.
\end{proof}
\bigskip % Put new definition with theorem. Is this enuf space?
Let $P_m$ be the graph with $V(P_m)=\{p_1,\dots,p_m\}$ and
$E(P_m)=\{\{p_1,p_2\},\dots,\{p_{m-1},p_m\}\}$.
\begin{lemma}
For all vertices $x$ of $K_m$, $m\ge 3$, we have
\begin{equation}
f((p_{\D+1},x),P^*_{\D+1}\times K_m) \le 2^{\D+1}+2m-5
\end{equation}
for all sufficiently large $\D$.
\end{lemma}
\begin{proof}
Let $V(K_m) = \{x=x_0,\dots,x_{m-1}\}$.
We induce on $\D$. Suppose $f((p_\D, x_0), P^*_\D\times K_m)\le 2^\D+r$.
Then we will prove that, if $\D$ is sufficiently large,
$f((p_{\D+1},x_0),P^*_{\D+1}\times K_m)\le 2^{\D+1}+\max(r-1,2m-5)$.
This will give (\theequation) for (even larger) sufficiently large
values of $\D$.
Let $f((p_\D,x_0), P^*_\D\times K_m)\le 2^\D+r$, and let there be
pebbles on the vertices of $P^*_{\D+1}\times K_m$. Let $S_b =
\{p_2,\dots,p_{\D+1}\}\times K_m$, $S_t = \{p_1\}\times K_m$.
Let $p_b$ be the total number of pebbles in $S_b$, $p_t$ be the total number
in $S_t$, and define $q_t$, $q_b$ similarly. Then if
$$
p_b+{p_t-q_t \over 2}\ge 2^\D+r,
$$
we can first move $(p_t-q_t)/2$ pebbles into $S_b$ and then pebble
$(p_{\D+1},x_0)$
in $S_b$. Hence we can assume that
\begin{eqnarray*}
{p_t+q_t \over 2}&>& 2^{\D+1}+\max(r-1,2m-5)-2^\D-r\\
&\ge& 2^\D-1,
\end{eqnarray*}
so $p_t+q_t>2^{\D+1}-2$ and hence $p_t+q_t\ge2^{\D+1}$. Let
$$
\a = q_t+q_b,\qquad\b = p_t-q_t, \qquad\g=p_b-q_b.
$$
Then $q_t\le m$ so $ \b=p_t-q_t\ge 2^{\D+1}-2m$.
Also,
\begin{equation}
\a+\b+\g=p_t+p_b\ge 2^{\D+1}+2m-5.
\end{equation}
Let
$$
Q = \sum_{k=1}^{\D+1} \N(p_k,x_0) 2^{k-1}.
$$
Then we will show that we can move pebbles until $Q\ge 2^\D$, at
which point we will be able to pebble $(p_{\D+1},x_0)$, by Lemma 8.
Let $T_j=P^*_{\D+1}\times\{x_j\}$. Then pebbling from $S_t$ into $T_0$,
we can get at least $\b/2$ pebbles in $T_0$. Pebbling from $S_b$, we
can get at least $\g/2$ pebbles in $T_0$, and since none of them are on
$(p_1,x_0)$, this increases $Q$ by at least $\g$.
For each $j=0,\dots,m-1$, let
$\a_j$ be the number of
vertices in $P_{\D+1}^*\times \{x_j\}$ with an odd number of pebbles,
and let $\b_j$ be $2 \floor{\N(p_1,x_j)/2}$.
Then $Q$ starts out with a value of at least $2^{\a_0}-1$.
Hence after this pebbling, we have
$$
Q \ge {\b\over 2}+\g+2^{\a_0}-1.
$$
Now
$\b$ is even, so let $\b=2^{\D+1}-2\d$, where $\d\le m$. Then
$2^\D-Q \le \d-\g-(2^{\a_0}-1)$, so
if we do not already have $Q\ge2^\D$, we must have $\d\in\{1,\dots,m\}$
and $\g\in\{0,\dots,\d-1\}$. From (\theequation), $\a\ge 2m-5+2\d-\g$.
Now we have $\a_j$ pebbles left in $T_j$ for $j=1,\dots,m-1$,
with at most one pebble on each vertex.
Our strategy for increasing $Q$ will be
to redirect some of the pebbles in $S_t$ that were counted in $\b$
to pebble other $T_j$'s instead of $T_0$, so that
if we spend $z$ pebbles from $\b$ in this manner, we can increase
$Q$ by more than the $z/2$ we would have originally.
Consider a $T_j$ that has $\a_j=k\ge 3$ and pebbles on
$(p_{R_1},x_j)$,$\dots$,$(p_{R_k},x_j)$, where $R_1< R_2<\dots< R_k$.
Now if we move $2^{R_k-1}-2^{R_{k-1}-1}-\dots-2^{R_1-1}$ pebbles
onto $(p_1,x_j)$ at the start, pebbling down $T_j$, we can move
one pebble to $(p_{R_k},x_j)$, and then one pebble to $(p_{R_k},x_0)$.
This increases $Q$ by $2^{R_k-1}$ and uses $2^{R_k}-2^{R_{k-1}}-\dots-2^{R_1}$
pebbles from $\b$. Hence it increases $Q$ from the original estimate
by $2^{R_{k-1}-1}+\dots+2^{R_1-1} = Y_j$, say, and uses $2^{R_k}-2Y_j$ pebbles
from $\b$. Now if $Y_j\ge m$, we have enough pebbles in $\b$
to do this, since $\b\ge 2^{\D+1}-2m$,
and furthermore, increasing $Q$ by $m$ raises it above $2^\D$,
so we are done. If $Y_jm-1$. Hence there must be some $\a_j\ge 2$.
Let $\a_j\ge 2$, and let there be pebbles at
$(p_k,x_j)$ and $(p_l,x_j)$, where
$k>l$. Now let us move $2^{k-1}-2^{l-1}$ pebbles onto $(p_1,x_j)$
at the start. Then pebbling down $T_j$, we can
move a pebble to $(p_k,x_0)$. This increases $Q$ by $2^{k-1}$
and uses $2^k-2^l$ pebbles from $\b$, and since $\b=2^{\D+1}-2$,
$\b$ is large enough to do this. Then we have increased
$Q$ by $2^{l-1}\ge 1$ from its original estimate, so we are done.
Suppose $\d=2$. Then if $\g=1$ and
$\a_0\ge 1$, we are done, and if $\a_0\ge 2$,
we are also done. Suppose either $\g=1$ and $\a_0=0$
or $\g=0$ and $\a_0=1$.
Then $\a-\a_0\ge 2m-2$. If there is some $\a_j\ge 3$, then the left-hand
side of (\theequation) will be at least
$1$, so we will be done. Otherwise,
we must have
$\a_j=2$ for all $j\ne0$. Then if $\b_0\ge 2^\D$, $Q$ will be at
least $2^\D$, so we will be done.
Otherwise $\b-\b_0>2^\D-4$, so there is $j\ne 0$
with $\b_j > (2^\D-4)/(m-1)$. In particular, if $\D$ is large
enough, $\b_j \ge 2$. Then if there are pebbles in $T_j$
at $(p_k,x_j)$ and $(p_l,x_j)$, where
$k>l$, moving $2^{k-1}-2^{l-1}$ pebbles
onto $(p_1,x_j)$ takes at most $2^k-2^l-2$ pebbles from $\b$, since
we save 2 pebbles due to the 2 pebbles already on $(p_1,x_j)$
(unless $2^k-2^l<4$, in which case $k=2$ and $l=1$, so that it takes
just 1 pebble from $\b_j$.)
In any case, $\b=2^{\D+1}-4$, so we have enough pebbles to proceed as in the
$\d=1$ case, and we can increase $Q$ by at least 1 from its original
estimate, so we are done.
Finally, suppose $\d=2$ and
$\g=\a_0=0$. Then $\a-\a_0\ge 2m-1$. If there
is some $j$ with $\a_j\ge 4$, or
$j$ and $k$ with $\a_j\ge 3$ and $\a_k\ge 3$,
then the left-hand side of (\theequation) will be at least 2 so we
will be done. Otherwise, we must have $\a_j=3$ for some $j$ and
$\a_i=2$ for all other $i\ne0$. Then if there are pebbles in $T_j$
at $(p_k,x_j)$, $(p_l,x_j)$, and $(p_r,x_j)$, where $k>l>r$, moving
$2^{k-1}-2^{l-1}-2^{r-1}$ pebbles onto $(p_1,x_j)$ will use
only $2^k-2^l-2^r$ pebbles from $\b$; but this is no larger than
$2^{\D+1}-6$,
so $\b$ is large enough to do this. Then this increases $Q$ by
$2^{l-1}+2^{r-1}\ge 3$ from its original estimate, so we are done.
\end{proof}
\begin{lemma}
Let $G$ be a connected graph and let $v$ be a vertex of $G$.
Then there is an integer $K(v,G)$ such that for all $\D$,
$$
f((p_{\D+1},v), P^*_{\D+1}\times G) \le 2^{\D+h} + (\D+1)K(v,G),
$$
where $h=\max_{w\in V(G)} d(w,v)$.
\end{lemma}
\begin{proof}
Let $T$ be a spanning tree of $G$ which preserves
distances from $v$. Then if $(a_1,\dots,a_n)$ is a path-size sequence
of a maximum path-partition for $T$, $a_1=h$, so applying Theorem 6 to
$T_v^*\times P^*_{\D+1}$, we can set $K(v,G)=\sum_{i=2}^n 2^{a_i}-n+1$.
\end{proof}
\begin{lemma}
Let $G$ be a connected graph with diameter $h$. Then for all
sufficiently large $\D$,
\begin{equation}
f(P_{\D+1}\times G) = \max_{w\in Q}( f((p_{\D+1},w),P_{\D+1}\times G) ),
\end{equation}
where $Q$ is the set of vertices $w$ of $G$ such that there exists
a vertex $v$ of $G$ with $d(v,w)=h$.
\end{lemma}
\begin{proof}
Choose vertices $v$ and $w$ of $G$ such that
$d(v,w)=h$. If we put $2^{\D+h}-1$ pebbles on $(p_1,v)$,
Theorem 3 shows that we cannot move a pebble to $(p_{\D+1},w)$. Hence
the right-hand side of (\theequation) is at least $2^{\D+h}$. Let
$K=\max_{w\in V(G)} K(w,G)$, and let $\D$ be big enough so that
$2^{\D-1+h}\ge 2^{h+1}+(\D+2)K$. Now let $j\in\{2,\dots,\D\}$, and fix
$v\in V(G)$. We will show that $f((p_j,v),P_{\D+1}\times G)\le 2^{\D+h}$.
If we set $S_1=\{p_1,\dots,p_j\}\times G$ and
$S_2=\{p_j,\dots,p_{\D+1}\}\times G$, Lemma 10 implies
that if there are at least $2^{j-1+h}+jK(v,G)$ pebbles on $S_1$, we can
pebble $(p_j,x)$, and if there are at least $2^{\D+1-j+h}+(\D+2-j)K(v,G)$
pebbles on $S_2$, we can also pebble $(p_j,x)$. Hence to pebble
$(p_j,x)$ it will do to have at least $2^{j-1+h}+2^{\D+1-j+h}+(\D+2)K(v,G)$
pebbles on $G$. But for $j\in \{2,\dots,\D\}$,
$$
2^{j-1+h} + 2^{\D+1-j+h}\le 2^{h+1} + 2^{\D-1+h},
$$
so we only need to have $2^{h+1}+2^{\D-1+h}+(\D+2)K(v,G)$ pebbles on $G$,
and this quantity is no larger than $2^{\D+h}$ by our assumption on $\D$.
Now $f((p_1,v),P_{\D+1}\times G)=f((p_{\D+1},v),P_{\D+1}\times G)$
for all $v\in V(G)$. Together with the above, this shows that
$$
f(P_{\D+1}\times G) = \max_{w\in V(G)} f((p_{\D+1},w),P_{\D+1}\times G).
$$
Now let $v\in V(G)$ have no $w\in V(G)$ such that
$d(w,v)=h$. Then we must have $d(w,v)\le h-1$ for all $w\in V(G)$, so
by Lemma 10,
$$
f((p_{\D+1},v),P_{\D+1}\times G) \le 2^{\D+h-1} + (\D+1)K(v,G),
$$
and this is also no larger than
$2^{\D+h}$. Hence we have (\theequation), as desired.
\end{proof}
\begin{theorem}
For all $m\ge 3$ and sufficiently large $\D$,
$$
f(P_{\D+1}\times K_m) = 2^{\D+1}+2m-5.
$$
\end{theorem}
\begin{proof}
\paragraph{$(\le)$: } This follows from Lemmas 9 and 11.
\paragraph{$(\ge)$: } We will show that $f(P_{\D+1}\times K_m)\ge
2^{\D+1}+2m-5$ for all $\D\ge 1$. Let $V(K_m)=\{x_0,\dots,x_{m-1}\}$.
Put $2^{\D+1}-3$ pebbles on $(p_1,x_0)$, 1 pebble on $(p_1,x_j)$ for
$j=1,\dots,m-1$, and 1 pebble on $(p_{\D+1},x_j)$ for
$j=2,\dots,m-1$. This
gives a total of $2^{\D+1}+2m-6$ pebbles. We will show that with
this starting configuration of pebbles, we cannot pebble
$(p_{\D+1},x_1)$. Suppose we did, in fact, have some sequence of moves
that pebbled $(p_{\D+1},x_1)$. Consider the first pebbling move we
make into $\{p_{\D+1}\}\times K_m$. If this move is onto $(p_{\D+1},x_j)$,
where $1\le j\le m-1$, then
2 pebbles were on $(p_\D,x_j)$ prior to this move.
Otherwise the move is to $(p_{\D+1},x_0)$, but putting a pebble on
$(p_{\D+1},x_0)$ does not enable us to do any pebbling from the bottom
row, so there must be some succeeding move into the bottom row. If
the next move into the bottom row is onto $(p_{\D+1},x_j)$, where
$1\le j\le m-1$, then 2 pebbles were on $(p_\D,x_j)$ just before
this move, and there would still have been at least
$2$ pebbles on $(p_\D,x_j)$
prior to this move if we did not make the move to $(p_{\D+1},x_0)$.
Otherwise the move must be to $(p_{\D+1},x_0)$, so if we omit the first
move to $(p_{\D+1},x_0)$, we must have at least
4 pebbles on $(p_\D,x_0)$ before
this move.
This shows that
by pebbling only in $\{p_1,\dots,p_\D\} \times K_m$, we can either move
2 pebbles to $(p_\D,x_j)$, for some $j\in\{1,\dots,m-1\}$, or move 4
pebbles to $(p_\D,x_0)$. But if we set
\begin{eqnarray*}
Q_i &=& \sum_{j=1}^\D 2^{j-1} \N(p_j,x_i), \qquad i=0,\dots,m-1, \hbox{ and}
\\
Q &=& \sum_{i=1}^{m-1} \max({Q_i-1\over 2},0) + {1\over2}
\ceil{Q_0-1\over2}
\end{eqnarray*}
we would then have $Q\ge 2^{\D-1}-{1\over2}$. Now since $Q_i$
does not increase when we pebble from some $(x_i,p_j)$ to $(x_i,p_{j-1})$
or $(x_i,p_{j+1})$, $Q$ does not increase either. But if we pebble from
$(x_i,p_j)$ to $(x_k,p_j)$, where
$i,k>0$, then for some $r>0$, $Q_i$ will
decrease by $2r$ and $Q_k$ will increase by $r$; then
$\max((Q_i-1)/2,0)$ will decrease by at least $(2r-1)/2$
and $\max((Q_k-1)/2,0)$
will increase by at most $r/2$, so the
net change in $Q$ is no larger than $(1-r)/2 \le 0$.
If we pebble from $(x_0,p_j)$ to $(x_i,p_j)$, $i>0$, and $Q_0$ decreases
by $2r$ while $Q_i$ increases by $r$, then $(1/2)\ceil{(Q_0-1)/2}$ will
decrease by $r/2$ and $\max((Q_i-1)/2,0)$ will increase by at
most $r/2$, so
$Q$ does not increase. Finally, if we pebble from $(x_i,p_j)$ to $(x_0,p_j)$,
$i>0$, and $Q_i$ decreases by $2r$ while $Q_0$ increases by $r$, then
$(1/2)\ceil{(Q_0-1)/2}$ will increase by at most
$r/2$ while $\max((Q_i-1)/2,0)$
will decrease by at least $(2r-1)/2$, so the net change in $Q$ is
no larger than $(1-r)/2 \le 0$.
So $Q$ never increases; but the initial value of $Q$
is only $2^{\D-1}-1$, so we have a contradiction, as desired.
\end{proof}
\begin{lemma}
Suppose there are pebbles on $P^*_{\D+1}\times
P_{r+1}$, and let $\N(p_1,p_j)=\e_j$ and $\sum_{i=1}^{\D+1} 2^{i-1}
\N(p_i,p_j)=w_j$ for $j=1,\dots,r+1$. Suppose
$\e_1+\dots+\e_r+\e_{r+1}/2\ge 2^{\D+r}-Q$, where
$Q\le 2^{\D-1}-2^{r-1}$.
As well
as the usual pebbling operations, suppose that we either have that
\begin{enumerate}
\item We can take $2^k-R$ pebbles off $(p_1,p_l)$ and put 1 pebble
on $(p_{k+1},p_l)$, for some fixed $l$ and $k$ with
$1\le l \le r$, $1\le k\le\D$,
where $R-Q\ge 2^r$, or
\item For each $j=1,\dots,r$, we can take $P_j\le S=2^{\D-r-1}$
pebbles off $(p_1,p_j)$ and distribute these pebbles on column $j$
into a configuration with $\sum_{i=1}^{\D+1} 2^{i-1} \N(p_i,p_j)=R_j$,
where $w_{r+1}+\sum_{j=1}^r (w_j+R_j-P_j) \ge 2^{\D+r}$.
\end{enumerate}
Then we can pebble $(p_{\D+1},p_{r+1})$, and furthermore, if in 1.
we have $\e_l\ge 2^k-R$, or if in 2. we have some $\e_j\ge P_j$,
then we can pebble $(p_{\D+1},p_{r+1})$ performing the special operation
in 1. at the beginning of our pebbling, or performing the special
operation in 2. on $P^*_{\D+1}\times \{p_j\}$
at the beginning of our pebbling.
\end{lemma}
\begin{proof}
First, move $\floor{\e_{r+1}/2}$ pebbles onto
$(p_1,p_r)$ from $(p_1,p_{r+1})$. Then we have $\e_1+\dots+\e_r\ge
2^{\D+r}-Q$. Now we have 2 cases corresponding to 1. and 2.
in the statement of the lemma.
\paragraph{Case 1.: } For each $j=1,\dots,r$, we do the following,
in order:
\begin{description}
\item[Step (1).]
If $j=l$, expend $2^k-R$ pebbles from $(p_1,p_l)$ to put a pebble
on $(p_{k+1},p_l)$.
\item[Step (2).]
If $j\ge l$, expend $2^k$ pebbles from $(p_1,p_l)$ to move
a pebble to $(p_{k+1},p_j)$. This gives 2 pebbles on $(p_{k+1},p_j)$,
so move a pebble to $(p_{k+1},p_{j+1})$.
\item[Step (3).]
Pebble everything possible from $(p_1,p_j)$ to $(p_1,p_{j+1})$.
\end{description}
Let $\g_j$ be the number of pebbles on $(p_1,p_j)$ before step (1).
Let
$$
v_j=\left\{ \begin{array}{ll}
0, & jl. \end{array} \right.
$$
Then for steps (1)-(3) to be possible, we need to have $\g_j\ge v_j$
for $j=l,\dots,r$, and we will have
$$
\g_{j+1}=\floor{\g_j-v_j\over 2}+\e_{j+1} \ge {\g_j-v_j-1\over2}+\e_{j+1},
$$
$j=1,\dots,r$. Then since $\g_1=\e_1$, we have
$$
\g_j \ge \sum_{i=1}^j \e_i 2^{-(j-i)} -
\sum_{i=1}^{j-1} (v_i+1) 2^{-(j-i)}.
$$
Now if $\e_{j+1}+\dots+\e_r \ge 2^{\D+1+r-(j+1)}$, there are
at least $2^{\D+1+r-(j+1)}$ pebbles
in $P_{\D+1}^*\times\{p_{j+1},\dots,p_{r+1}\}$,
so we can pebble $(p_{\D+1},p_{r+1})$ within $P_{\D+1}^*\times
\{p_{j+1},\dots,p_{r+1}\}$, by Theorem 6. Hence we can assume that
$$
\e_1+\dots+\e_j\ge 2^{\D+r}-Q-2^{\D+r-j}
$$
except that
$$
\e_1+\dots+\e_r\ge 2^{\D+r}-Q,
$$
so
$$
\sum_{i=1}^j \e_i 2^{-(j-i)} \ge 2^{-(j-1)} (2^{\D+r}-Q-2^{\D+r-j}
(1-\kd_{jr}))
$$
where $\kd$ is the Kronecker delta function. Then to satisfy
$\g_j\ge v_j$ for $j=l,\dots,r$, we need to have
$$
2^{-(j-1)} (2^{\D+r}-Q-2^{\D+r-j} (1-\kd_{jr})) \ge
\sum_{i=1}^{j-1} (v_i+1) 2^{-(j-i)} + v_j,
$$
but
\begin{eqnarray*}
\sum_{i=1}^{j-1} (v_i+1) 2^{-(j-i)} + v_j
&=& (2^{-1}+\dots+2^{-(j-1)}) + (2^{k+1}-R)2^{-(j-l)}\\
&& + 2^k (2^{-(j-l-1)}+\dots+1) \\
&\le& 1+2^{k+1}-R2^{-(j-l)}.
\end{eqnarray*}
Then
$$
R2^{-(j-l)}-Q2^{-(j-1)} \ge (R-Q) 2^{-(j-1)} \ge 2^r 2^{-(j-1)} \ge 1,
$$
so it will do to have
$$
2^{\D+r-(j-1)} \ge 2^{k+1} + 2^{\D+r-(2j-1)} (1-\kd_{jr}),
$$
or, since $k\le\D$, it will do to show that
\begin{equation}
2^{\D+r-(j-1)} \ge 2^{\D+1} + 2^{\D+r-(2j-1)} (1-\kd_{jr}).
\end{equation}
If $j=r$, this reduces to $2^{\D+1}\ge2^{\D+1}$. Otherwise,
$\D+1<\D+r-(j-1)$ and $\D+r-(2j-1)<\D+r-(j-1)$, so
(\theequation) holds, as desired. Hence we can always perform the
pebbling program outlined. After doing it, we will have $\g_{r+1}$
pebbles on $(p_1,p_{r+1})$, but
\begin{eqnarray*}
\g_{r+1} &\ge& \sum_{i=1}^{r+1} \e_i 2^{-(r+1-i)}
- \sum_{i=1}^r (v_i+1) 2^{-(r+1-i)} \\
&\ge&
2^{-r} (2^{\D+r}-Q) - (1+2^k-R2^{-(r+1-l)}) \\
&\ge& 2^\D+2^{-r}(R-Q)-1-2^k \\
&\ge& 2^\D-2^k.
\end{eqnarray*}
But we also have a pebble on $(p_{k+1},p_{r+1})$, so by Lemma 8, we
can pebble $(p_{\D+1},p_{k+1})$, as desired. Also, from above, it
is clear that if $\e_l\ge 2^k-R$, we can perform operation 1. first,
as desired.
\paragraph{Case 2.: } For each $j=1,\dots,r$, we do the following,
in order:
\begin{description}
\item[Step (1).]
Take $P_j$ pebbles off $(p_1,p_j)$ and redistribute them.
\item[Step (2).]
Pebble from $(p_2,p_j)$ to $(p_2,p_{j+1})$, $\dots$,
$(p_{\D+1},p_j)$ to $(p_{\D+1},p_{j+1})$ so that there is no more than
one pebble left on each of
$(p_2,p_j)$, $\dots$, $(p_{\D+1},p_j)$.
\item[Step (3).]
Suppose there are pebbles left
on $(p_{R_1},p_j)$,$\dots$,$(p_{R_k},p_j)$, where
$1\D-r-m-1$, we must have
$$
l \ge k-(\D+1-R_l) > {\D+2\over2}-(\D+1)+(\D-r-m-1) = {\D\over2}-r-m-1.
$$
Hence for big enough $\D$, $2^l-2\ge Q+2^r$, and since
\begin{eqnarray*}
2^{R_l}-2^{R_{l-1}}-\dots-2^{R_1} &\le& 2^{R_l} - (2^{l-1}+\dots+2)\\
&=& 2^{R_l} - (2^l-2),
\end{eqnarray*}
condition 1. of Lemma 13
is satisfied and we are done. Otherwise $R_l\le \D-r-m-1$. Then
we have to move at most $2^{\D-r-m-1}\le 2^{\D-r-1}/(m+1)$
pebbles from $\b_t$, and by doing this
we can increase $X$ by
$$
2^{R_{l-1}}+\dots+2^{R_1}\ge2^{l-1}+\dots+2^1=2^l-2.
$$
Let $y$ be maximal with $R_y+1=R_{y+1}$. Then there can be at most
$\floor{(\D+1-R_{y+1})/2}$ $l$'s with $R_l > R_{y+1}$, so
$$
(y+1) + \floor{\D+1-R_{y+1}\over 2} \ge k
$$
and since $R_y \ge y$,
$$
k \le y+1 + \floor{\D-y\over 2} \le 1+{\D+y\over 2},
$$
so $y\ge 2k-\D-2$, and we can increase $X$ by at least $\max(2^{2k-\D-2}-2,0)$,
under the assumption that $k \ge (\D+2)/2$. But if $k < (\D+2)/2$, then
this is vacuously true, so for all $j\in\{r+2,\dots,m+r+2\}$, we can
increase $X$ by at least
\begin{equation}
\max(2^{2\a_j-\D-2}-2,0).
\end{equation}
If there is $j\in\{r+2,\dots,m+r+2\}$ with $\a_j\le 1$, let $w$ be such a $j$.
Otherwise let $\a_j\ge 2$ for
$j=r+2,\dots,m+r+2$. We wish to show that for
some $w \in\{r+2,\dots,m+r+2\}$, we can increase $X$ by at least $\a_w-1$.
Fix $j\in\{r+2,\dots,m+r+2\}$, and suppose $x_j$ is adjacent to $x_q$ in $C$,
where $q\in\{1,\dots,r\}$. Let $\a_j=k$. Then if there are pebbles
at $(p_{R_1},x_j)$, $\dots$, $(p_{R_k},x_j)$, where
$R_1<\dots 2^{R_l-1} - (m+r+2+2^r),
$$
so
\begin{eqnarray*}
(m+r+2)+2^r &>& 2^{R_l-2}+\dots+2^{R_2-2}+2^{R_1-2}(1-\kd_{1R_1}) \\
&\ge& {1\over2}\left(2^{R_l-1}-\dots-2^{R_2-1}-2^{R_1-1}(1-\kd_{1R_1})\right)
\end{eqnarray*}
and if $\D$ is large enough, $2^{\D-r-1} \ge (m+r+2+2^r)(m+1)$, so the
cost to $\b_q$ will not exceed $2^{\D-r-1}/(m+1)$.
Now we show that we can increase $X$ by a total of
$$
(\a_w-1)
+ 2\left( \sum_{j=r+2,\ j\ne w}^{m+r+2} \a_j \right) - 2m\ceil{\D+2\over2}.
$$
If $\D$ is odd, $\ceil{(\D+2)/2} = (\D+3)/2$, and
\begin{eqnarray*}
\sum_{j=r+2,\ j\ne w}^{m+r+2} \max(2^{2\a_j-\D-2}-2,0) &\ge&
\sum_{j=r+2,\ j\ne w}^{m+r+2} (2^{2\a_j-\D-2}-2) \\
&\ge& \sum_{j=r+2,\ j\ne w}^{m+r+2}
(2\a_j-\D-3) \\
&=& 2\left( \sum_{j=r+2,\ j\ne w}^{m+r+2} \a_j \right) - 2m{\D+3\over2},
\end{eqnarray*}
as desired. If $\D$ is even, $\ceil{(\D+2)/2} = (\D+2)/2$. For even $x$,
$\max(2^x-2,0)\ge x$, so
\begin{eqnarray*}
\sum_{j=r+2,\ j\ne w}^{m+r+2} \max(2^{2\a_j-\D-2}-2,0) &\ge&
\sum_{j=r+2,\ j\ne w}^{m+r+2} (2\a_j-\D-2) \\
&=& 2\left( \sum_{j=r+2,\ j\ne w}^{m+r+2} \a_j \right) - 2m{\D+2\over2},
\end{eqnarray*}
as desired.
Now
$$
\sum_{j=r+2,\ j\ne w}^{m+r+2} \a_j \ge \ceil{\D+2\over2}m+2(2^{\D+r}-X)-\a_w
$$
so we can increase $X$ by at least
$$
4(2^{\D+r}-X)-\a_w-1.
$$
But if $2^{\D+r}-X \le \a_w-1$, we can increase $X$ by $\a_w-1$, making
$X\ge 2^{\D+r}$,
so we are done. Otherwise we can assume $\a_w-1 < 2^{\D+r}-X$ so
$\a_w+1 \le 3(2^{\D+r}-X)$, and we can increase $X$ by at least $2^{\D+r}-X$.
Furthermore, if we do not satisfy
condition 1. of Lemma 13, we can do so at a cost
of $Y_1$ pebbles from $\b_{a_1}$, $\dots$,
$Y_{m+1}$ pebbles from $\b_{a_{m+1}}$,
where each $a_j$ is in $\{1,\dots,r\}$ and all
$Y_j\le 2^{\D-r-1}/(m+1)$.
Hence condition 2. of Lemma 13 is then satisfied, so we are done.
\end{proof}
\begin{theorem}
Let $C$ be a caterpillar with $m$ legs and a backbone with $r+2$
vertices. Then for all sufficiently large $\D$,
$$
f(P_{\D+1}\times C)=2^{\D+r+1}+\ceil{\D+2\over2}m.
$$
\end{theorem}
\begin{proof}
\paragraph{$(\le)$: } $C$ has diameter $r+1$, and vertices $v$ and $w$
of $C$
have $d(v,w)=r+1$ iff $v$ and $w$ are distinct end-vertices of some backbone.
Hence Lemma 14 tells us that for every vertex $v$ of $C$ such that a
vertex $w$ of $C$ exists with $d(w,v)=r+1$,
$$
f((p_{\D+1},v),P_{\D+1}\times C) \le 2^{\D+r+1} + \ceil{\D+2\over2}m.
$$
We can then apply Lemma 11 to get the desired result.
\paragraph{$(\ge)$: } We will show that $f(P_{\D+1}\times C)\ge
2^{\D+r+1}+\ceil{\D+2\over2}m$ for all $\D\ge0$. Let $B$ be a backbone
of $C$,
$V(B)=\{x_1,\dots,x_{r+1},x_{r+2}\}$, and $E(B)=\{\{x_1,x_2\},
\dots,\{x_{r+1},x_{r+2}\}\}$. Let the legs of $C$ be
$x_{r+3}$,$\dots$,$x_{m+r+2}$.
Put $2^{\D+r+1}-1$ pebbles on $(p_1,x_1)$, and
1 pebble on $(p_j,x_i)$ for
$i=r+3,\dots,m+r+2$ and
$j=1,2,4,\dots,2\floor{(\D+1)/2}$. Then there are
$$
2^{\D+r+1}-1+m\left(\floor{\D+1\over2}+1\right)
=2^{\D+r+1}-1+\ceil{\D+2\over2}m
$$
pebbles on $P_{\D+1}\times C$. We will show that we cannot pebble
$(p_{\D+1},x_{r+2})$. Let
\begin{eqnarray*}
Q_i&=&\sum_{j=1}^{\D+1} 2^{j-1} \N(p_j,x_i), \qquad i\in\{1,\dots,m+r+2\},\\
Q&=&\sum_{i=1}^{r+2} 2^{i-1} Q_i.
\end{eqnarray*}
Then $Q$ starts out equal to
$2^{\D+r+1}-1$, and if there was a pebble on
$(p_{\D+1},x_{r+2})$, $Q$ would be at least $2^{\D+r+1}$. But $Q$
does not increase when we pebble within $P_{\D+1}\times B$. We need
to show that it does not increase at other times either. Fix
$i\in\{r+3,\dots,m+r+2\}$, and let $x_i$ be adjacent to $x_q$,
where $q\in\{1,\dots,r+2\}$.
Now if we consider all the pebbling moves
from $P_{\D+1}\times\{x_q\}$ into $P_{\D+1}\times\{x_i\}$, they must
decrease $Q_q$ by $2r$ and increase $Q_i$ by $r$, for some $r\ge0$.
But if we increase $Q_i$ by $r$, where
$$
r < 2^{2j+1}-(1+2+8+\dots+2^{2j-1}), \qquad j\ge0,
$$
we will not be able to move a pebble to $(p_{2j+2},x_i)$ afterwards.
This is because $(p_{2j+2},x_i)$, $\dots$, $(p_{\D+1},x_i)$ each start
with at most $1$ pebble,
and hence we can make no pebbling moves out of $(p_{2j+2},
x_i)$,$\dots$,$(p_{\D+1},x_i)$ until we pebble $(p_{2j+2},x_i)$, which will
put 2 pebbles on $(p_{2j+2},x_i)$. Hence if we could pebble $(p_{2j+2},x_i)$,
by Theorem 3, we would have
$$
\sum_{k=1}^{2j+2} \N(p_k,x_i)\ge 2\cdot2^{2j+1},
$$
but
$$
\sum_{k=1}^{2j+2} \N(p_k,x_i)\le r+1+2+8+\dots+2^{2j+1} < 2\cdot2^{2j+1},
$$
so this is impossible. But if we cannot pebble $(p_{2j+2},x_i)$, then
in moving pebbles out of $P_{\D+1}\times\{x_i\}$, we can only move out of
$(p_1,x_i)$,$\dots$,$(p_{2j+1},x_i)$, so we can decrease $Q_i$ by at most
$r+1+2+8+\dots+2^{2j-1}$ and increase $Q_q$ by at most $(r+1+2+8+\dots+
2^{2j-1})/2$. Then the net change in $Q_q$ is no bigger than
\begin{eqnarray*}
-2r + {r+1+2+8+\dots+2^{2j-1}\over2} &=&
-{3r\over2} + {1+2+8+\dots+2^{2j-1}\over2}.
\end{eqnarray*}
Now let $j\ge0$ be minimal with $r<2^{2j+1}-(1+2+8+\dots+2^{2j-1})$. Then
if $j=0$, we have
$r<1$, so $r=0$ and we clearly do not increase $Q_q$, since we
can move no pebbles out of $P_{\D+1}\times \{x_i\}$. Otherwise,
$$
r\ge 2^{2j-1}-(1+2+8+\dots+2^{2j-3}),
$$
so
\begin{eqnarray*}
&& -{3r\over2}+{1\over2}(1+2+8+\dots+2^{2j-1}) \\
&\le&
-{3\over2}(2^{2j-1}-(1+2+8+\dots+2^{2j-3}))+{1\over2}(1+2+8+\dots+2^{2j-1}) \\
&=&
2(1+2+8+\dots+2^{2j-3})-2^{2j-1} \\
&=&
2+4+16+\dots+2^{2j-2}-2^{2j-1} \le 0,
\end{eqnarray*}
so $Q_q$ cannot suffer a net increase after all pebbling out of
$P_{\D+1}\times \{x_i\}$ is done.
Considering all $i$ and $q$,
this means that the total value of $Q$ can never increase,
so we are done.
\end{proof}
\section{Acknowledgement.}
This work was done at the University of Minnesota at Duluth under the
supervision of Joseph A. Gallian and sponsorship of the National
Science Foundation (NSF DMS-8709428).
\section{Reference.}
[1] Fan~R.~K.~Chung, Pebbling in Hypercubes, preprint.
% \begin{thebibliography}{9}
% ibitem{chung} Fan~R.~K.~Chung. ``Pebbling in Hypercubes.'' To appear.
% \end{thebibliography}
\end{document}