Optimal Pebbling Number

Instead of looking for the size of the largest unsolvable configuration in a graph, which is essentially the task in finding the pebbling number of the graph (minus one), one could look for the size of the smallest solvable configuration, which is the task in finding what is called the optimal pebbling number, $\pi^*(G)$. This model may be useful for a company finding the best distribution of their resources, for example.

Paths and Cycles

The following general upper bound for graphs on n vertices was proved in [BCCMW].

Optimal Pebbling Upper Bound.  $\pi^*(G_n) \leq \lceil 2n/3 \rceil$.

The upper bound has been shown to be tight for paths [PSV] and for cycles [BCCMW]. Caterpillars, cycles and other graphs have been considered in [FrWy, FuSh2, FuSh1].

Cubes and Products

It is surprising that, while $\pi(Q^d)$ is known exactly (see the Cube Theorem), only the following bounds are known at present [Moe].

Optimal Pebbling Cube Theorem.  $(4/3)^d\le \pi^*(Q^d)=(4/3)^{d+O(\log d)}$.

The following interesting analog of Graham's Conjecture was proven in [FuSh2, FuSh1].

Optimal Pebbling Product Theorem.   For all graphs $G$ and $H$ we have $\pi^*(G \times H) \leq \pi^*(G)\pi^*(H)$.

Min. Degree

Two results place the optimal pebbling numbers of graphs with minimum degree $\delta(G)=k$ near $cn/(k+1)$, roughly with $2.4\sim\le c\le 4$. The following result of Czygrinow appears in [BCCMW].

Upper Bound.   If $G$ is a connected graph with $n$ vertices and $\delta(G)=k$, then $\pi^*(G) \leq 4\left(\frac{n}{k+1}\right)$.

The upper bound is not known to be sharp. Two lower bounds are given in [BCCMW]. The first is that, for all $n>k\ge 2$, there is a graph $G$ with $\delta(G)=k$ and $\pi^*(G)>2\left(\frac{n}{k+1}\right)-2$. The second is as follows, which is stronger for large $n$ and $k$.

Lower Bound.   For all $n \geq (k+3)\ge 6$, there is a graph $G$ with $\delta(G)=k$ and $\pi^*(G) \geq \left(2.4-\frac{24}{5k+15}-o(1)\right)\left(\frac{n}{k+1}\right)$.

Girth

If girth is also considered then one can say more. Let $c_k(t) = 1 + k\sum_{i=0}^{t-1}(k-i)^i$ and $c'(t)= (2^{2t}-2^{t+1})t/(t-1)$. The following theorem of [BCCMW] displays an upper bound in terms of girth.

Optimal Pebbling Girth Upper Bound.   Let $k \geq 3$, $t \geq 2$, and $(k,t) \neq (3,2)$. Then every $n$-vertex graph $G$ with $\delta(G)=k$ and ${\rm girth}(G) \geq 2t+1$ satisfies $\pi^*(G) \leq 2^{2t}n/(c_k(t)+c'(t))$.

A slightly weaker version of the bound is $\pi^*(G)\le 4^tn\Big/\left((k-1)^t+4^t\right)$, while corollaries of it include $\pi^*(G)/n\le 3/8$ as $t\rightarrow\infty$ for $k=5$, and $\pi^*(G)/n\rightarrow 0$ as $t\rightarrow\infty$ for $k\ge 6$.

Ladders

The optimal pebbling numbers of linear $(P_m \times K_2)$, circular $(C_m \times K_2)$, and Mobius (circular with a twist) ladders are also determined in [BCCMW]: $\pi^*=m$ unless $m \in \{2,5\}$, with $m$ as a lower bound always.