Define a pebbling move as a transer of two pebbles from one vertex of a graph edge to an adjacent vertex with one of the pebbles being removed in transit as a toll.
The pebbling number 
of a graph 
is the smallest 
such that every supply of 
pebbles can satisfy every demand of one pebble (Hurlbert 2011).
Computing the pebbling number is NP-complete
(Hurlbert 2011).
The values of the pebbling number for various classes of graphs are given in the table below (Hurlbert).
| graph | pebbling number |
complete bipartite
graph  |  |
complete graph  |  |
cycle
graph  |  |
hypercube graph  |  |
path
graph  |  |
The pebbling number satisfies a number of bounds. Let 
be the vertex count, 
the graph
diameter, and 
the domination number of a graph 
.
Breadth lower bounds:
 |
(1)
|
Cut lower bound (which 
contained a cut vertex 
):
 |
(2)
|
Depth lower bound:
 |
(3)
|
Pigeonhole upper bound:
 |
(4)
|
Sharper bounds:
 |  |  |
(5)
|
 |  |  |
(6)
|
 |  |  |
(7)
|
(Hurlbert).
For a graph with 
,
 |
(8)
|
where 
is the vertex count of 
(Hurlbert 2011).
