Pebbling in Graphs


Glenn H. Hurlbert, Math. Dept.
Arizona State University and
The Johns Hopkins University



Suppose $p$ pebbles are distributed to the vertices of a graph $G$. A pebbling step consists of removing two pebbles from one vertex and then placing one pebble at an adjacent vertex. We say a pebble can be {\it moved} to a vertex $r$, the {\it root} vertex, if we can repeatedly apply pebbling steps so that in the resulting distribution $r$ has one pebble. For a graph $G$, we define the {\it pebbling number}, $f(G)$, to be the smallest integer $m$ such that for any distribution of $m$ pebbles to the vertices of $G$, one pebble can be moved to any specified root vertex $r$. Trivially, $f(G)$ is at least the number of vertices $n(G)$.

The concept of graph pebbling was introduced by Lagarias and Saks as a way to prove a number-theoretic conjecture of Erdos and Lemke. Chung successfully carried out their method by proving that the pebbling number of the $n$-cube is equal to the number of its vertices. Then Graham conjectured that $f(G\Box H)\le f(G)f(H)$, which would generalize her result. We will survey partial results on this question as well as introduce new results and conjectures about the behavior of $f$.

For example, by characterizing which diameter two graphs $G$ have $f(G)=n(G)$, we prove that every 3-connected diameter two graph $G$ has $f(G)=n(G)$, extending results of Pachter, Snevily and Voxman. We also use this characterization to show the same holds for almost all graphs. We conjecture that there is a function $k(d)$ such that if $G$ is a graph with $diam(G)=d$ and $\kappa (G)\ge k(d)$ then $f(G)=n(G)$. We prove that if $k$ exists then $k(d)\ge 2^d/d$. We believe that $k(d)\le 2^d$.

If time permits we will discuss some of the many open problems involving topics like greedy pebbling, tree-solvability, $p$-pebbling, threshold functions and the 2-pebbling property. Much of this is joint work with Tom Clarke and Rob Hochberg.