Pebbling Number
Define a pebbling move as a transfer 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 pi(G) of a graph G is the smallest t such that every supply of t 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).
The pebbling number satisfies a number of bounds. Let n=|G| be the vertex count, d(G) the graph diameter, and gamma(G) the domination number of a graph G.
Breadth lower bounds:
| pi(G)>=n |
(1)
|
Cut lower bound (which G_x contained a cut vertex x):
| pi(G_x)>n |
(2)
|
Depth lower bound:
| pi(G)>=2^d |
(3)
|
Pigeonhole upper bound:
| pi(G)<=(n-1)(2^d-1)+1 |
(4)
|
Sharper bounds:
(Hurlbert).
For a graph with d(G)=2,
| pi(G)<=n+1, |
(8)
|
where n=|G| is the vertex count of G (Hurlbert 2011).
See also
2-Pebbling Property, Graph Pebbling, Pebble Game, Pebbling Move, Scramble NumberExplore with Wolfram|Alpha
More things to try:
References
Chung, F. R. K. "Pebbling in Hypercubes." SIAM J. Disc. Math. 2, 467-472, 1989.Hurlbert, G. "A Linear Optimization Technique for Graph Pebbling." 28 Jan 2011. https://arxiv.org/abs/1101.5641.Hurlbert, G. "General Graph Pebbling." Disc. Appl. Math. 161, 1221-1231, 2013.Hurlbert, G. "Graph Pebbling Numbers Page." http://www.people.vcu.edu/~ghurlbert/pebbling/pnummain.html.Milans, K. and Clark, B. "The Complexity of Graph Pebbling." SIAM J. Disc. Math. 20, 769-798, 2006.Referenced on Wolfram|Alpha
Pebbling NumberCite this as:
Weisstein, Eric W. "Pebbling Number." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/PebblingNumber.html