Warning: jsMath requires JavaScript to process the mathematics on this page.
If your browser supports JavaScript, be sure it is enabled.

G. Hurlbert Pebbling

This is an area of graph theory invented by Lagarias and Saks in order to solve a number-theoretic question of Erdos and Lemke. Chung popularized the theory by successfully carrying out their plan. A pebbling step from a vertex $u$ to a vertex $v$ in a graph consists of removing two pebbles from $u$ and adding one pebble to $v$ (think of the lost pebble as a toll). The pebbling number of a graph $G$ is the smallest $t$ so that, from any initial distributions of $t$ pebbles to the vertices of $G$, one can place a pebble on any specified vertex after an appropriate sequence of pebbling steps. It is not hard to see that the pebbling number of a complete graph on $n$ vertices equals $n$, and the pebbling number of a path on $n$ vertices equals $2^{n-1}$. Slightly more challenging is to prove that the pebbling number of the Petersen graph is $10$. The holy grail of the field is a conjecture of Graham, bounding the pebbling number of a cartesian product of graphs by the product of their pebbling numbers. See the Pebbling Pages (logo above) for the history, results, applications, and variations of the subject, including optimal pebbling, fractional pebbling, cover pebbling, pebbling thresholds, and so on, or just read the most recent survey chapter or research article.