Graph Pebbling
Graph pebbling is a one-player graph game in which a configuration assigns a nonnegative integer number of pebbles to each graph vertex. A pebbling move removes two pebbles from one vertex and places one pebble on an adjacent vertex, with the other pebble discarded in transit.
A configuration is said to be root-solvable for a vertex r if a sequence of pebbling moves can place at least one pebble on r. The least number of pebbles such that every configuration of that size is root-solvable for every choice of r is the pebbling number.
Graph pebbling should not be confused with the pebble game used in sparse-graph and rigidity algorithms, which uses pebbles as markers for certifying sparsity rather than as consumable resources.
See also
2-Pebbling Property, Pebble Game, Pebbling Move, Pebbling Number, 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. "Graph Pebbling." In Handbook of Graph Theory (Ed. J. L. Gross, J. Yellen, and P. Zhang). Kalamazoo, MI: Chapman and Hall/CRC, pp. 1428-1449, 2013.Milans, K. and Clark, B. "The Complexity of Graph Pebbling." SIAM J. Disc. Math. 20, 769-798, 2006.Cite this as:
Weisstein, Eric W. "Graph Pebbling." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/GraphPebbling.html