If your browser supports JavaScript, be sure it is enabled.

Optimal Pebbling NumberInstead 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 CyclesThe following general upper bound for graphs on n vertices was proved in [BCCMW].Cubes and ProductsOptimal 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].It is surprising that, while $\pi(Q^d)$ is known exactly (see the Cube Theorem), only the following bounds are known at present [Moe].Min. DegreeOptimal 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)$.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].GirthUpper 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)$.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.LaddersOptimal 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$.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.