Definitions

In terms of possible applications it may be relevant to consider having to move a pebble to every vertex simultaneously, rather than to just one root. More generally, given a weight function $w$ on the vertices of a graph $G$, We define the weighted cover pebbling number $\gamma_w(G)$ to be the minimum number of pebbles needed to place, after a sequence of pebbling steps, $w(v)$ pebbles on vertex $v$, for all v, regardless of the initial configuration. The cover pebbling number $\gamma(G)$ regards the case $w(v)=1$ for all $v$. We say that $w$ is positive if $w(v) > 0$ for every vertex $v$.

Results

In [CCFHPST], for positive weight functions the weighted cover pebbling number for cliques and trees is found, and it is shown that the cover pebbling ratio between this parameter and the pebbling number can be arbtrarily large, even within the class of trees.

Cliques

Given $w$ define $|w| = \sum_v w(v)$ and $\min$ $w = \min_v$ $w(v)$.

For every positive weight function $w$ we have $\gamma_w(K_n)=2|w|-\min w$.

Trees

Given a graph $G$ define $s_w(G)=\max_v$ $\sum_u w(u)2^{{\rm dist}(u,v)}$, where ${\rm dist}(u,v)$ denotes the distance between $u$ and $v$.

For every positive weight function $w$ we have $\gamma_w(T)=s_w(T)$ for every tree $T$.

Cubes

Hurlbert's Stacking Conjecture (see Stacking Theorem), that $\gamma_w(G)=s_w(G)$ for every graph $G$, is verified for each of the above graphs, and also for cubes, below [HuMu]. In the case of $d$-dimensional cubes the resulting formula is quite nice.

$\gamma(Q^d)=3^d$.

Cycles and certain graph products were considered in [ToWy], and wheels and complete multipartite graphs were considered in [WaYe].

Stacking Theorem

It would be interesting to find the weighted pebbling numbers of other graph classes and also random graphs. The main technique in proving the Cover Pebbling Tree Theorem involves showing that the largest $w$-unsolvable configuration is simple; that is, concentrated ("stacked") on a single vertex. The same cannot be said in general for weight functions that are not positive. An important question to investigate along these lines is whether, for arbitrary graphs and positive weight functions, the largest $w$-unsolvable configuration is always simple. A positive answer is found in the following theorem, proved independently in [Sjo, VuWy].

Stacking Theorem.   For every graph $G$ and positive weight function $w$ we have $\gamma_w(G)=s_w(G)$.

Cover Pebbling Ratio

We define the cover pebbling ratio of $G$ to be $\rho(G)=\gamma(G)/\pi(G)$. For a class ${\cal F}$ of graphs we define $\rho({\cal F})={\rm sup}_{G \in {\cal F}}\rho(G)$ if it exists, and $\rho({\cal F})=\infty$ otherwise. Thus, for the families ${\cal K}$ of complete graphs, ${\cal S}$ of stars, and ${\cal P}$ of paths, we have $\rho({\cal K})=\rho({\cal S})=\rho({\cal P})=2$.

The fuse $F_l(n)$ is the graph on $n$ vertices composed of a path (or wick) on $l$ vertices with $n-l$ independent vertices (sparks) incident to one of its endpoints. (These are also called brooms, with handle and bristles, in [EFS].) As a special case of the Cover Pebbling Tree Theorem we know that the cover pebbling number of fuses is $\gamma(F_l(n))=(n-l+1)2^l-1$. Likewise, as a special case of the Pebbling Tree Theorem we also know that the pebbling number of fuses is $\pi(F_l(n))=2^l+n-l+1$. As a result, we obtain the cover pebbling ratio for fuses. In particular, for $n=2^l+l$, we have $\rho(F_l(n)) > (n-\log n)/2$. This implies that the cover pebbling ratio for the class of trees is unbounded

Cover Pebbling Ratio Tree Theorem.   Let ${\cal T}$ be the family of all trees. Then $\rho({\cal T})=\infty$.

It would be of interest to find other classes of graphs (like cliques and stars and paths) which have bounded cover pebbling ratio.

Weighted Pebbling Number

Finally, we define the weighted pebbling number $\pi_{\mathbf{w}}(G)$ to be the minimum number $t$ so that, for every weight function $w$ with $|w|=\mathbf{w}$, every configuration of $t$ pebbles is $w$-solvable. Note that the target weight function $w$ is fixed in the definition of weighted cover pebbling number, while for weighted pebbling number every target weight function $w$ of size $|w| = \mathbf{w}$ must be solvable. If one is concerned only with positive $w$, then such an evaluation on any tree $T$ is trivial. One would compute $\max_w \max_v \sum_u 2^{d(u,v)} = \max_v \max_w \sum_u 2^{d(u,v)} = \max_v |w|2^{\max_u d(u,v)} = \mathbf{w} 2^{{\rm diam}(T)}$. However, nonpositive $w$ must be considered, and thus finding weighted cover pebbling numbers for such $w$ is critical.

References

P. Erdos, R.J. Faudree and R.H. Schelp Ramsey numbers for brooms Congr. Numer. 35 (1982), 283--293