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}$.
A simple puzzle is to prove that the pebbling number of the
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
(logo above) for some 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
,
, or
|