Graph Pebbling is a network optimization model for the transportation of resources that are consumed in transit. Electricity, heat, or other energy may dissipate as it moves from one location to another, oil tankers may use up some of the oil it transports, information may be lost as it travels through its medium, or military troops may be lost while moving through a region. The central problem in this model asks whether discrete pebbles from one set of vertices can be moved to another while pebbles are lost in the process.

A typical question asks how many pebbles are necessary to guarantee that, from any configuration of that many pebbles, one can move a pebble to (“solve”) any particular vertex. A fractional version asks for the limiting behavior of the average number of pebbles used per “solution”. Instead of placing the initial pebbles cleverly, if the original configuration is chosen at random then we can wonder what the probability is that every vertex can be solved, which gives rise to the notion of a threshold, which divides almost sure success and almost sure failure. One may also ask: how few pebbles can be used so that, from some configuration of that many pebbles, one can move a pebble to any particular vertex; how many pebbles are required to guarantee that, from any configuration of that many pebbles, some pebble can travel at least some fixed distance; and other questions.

Various rules for pebbling steps have been studied for years and have found applications in a wide array of areas. One version, dubbed black and white pebbling, was applied to computational complexity theory in studying time-space tradeoffs, as well as to optimal register allocation for compilers. Connections have been made also to pursuit and evasion games and graph searching. Another (black pebbling) is used to reorder large sparse matrices to minimize in-core storage during an out-of-core Cholesky factorization scheme. A third version yields results in computational geometry in the rigidity of graphs, matroids, and other structures. The rule we study here originally produced results in combinatorial number theory and combinatorial group theory (the existence of zero sum subsequences and have recently been applied to finding solutions in p-adic diophantine equations. Most of these rules give rise to computationally difficult problems.

Finally, graph pebbling investigations on directed graphs have begun as well.

Because of the superficial similarity of graph pebbling to other positional games on graphs, like “Cops-and-Robbers” and “Chip-Firing” for instance, and the high degree of applicability of many of these games to structural graph theory and theoretical computer science, one shouldn’t neglect the possibility that graph pebbling will have similar impact. For example, one can think of the loss of a pebble during a pebbling step as a toll or as a loss of information, fuel or electrical charge. q-pebbling is one generalization of this rate of loss; another is simply to choose any fixed rate α of loss. In any case, instead of restricting the initial configuration to integer values, let C range among all nonnegative reals. A pebbling step removes weight x from one vertex and places weight αx at an adjacent vertex, for some fixed 0 < α < 1. Still the objective is to place weight 1 at any prescribed root r so that there is enough money, fuel, information, or energy at that location in the network. Of course, all of the questions raised herein may be asked about this more general α-pebbling. It is conceivable that chip-firing may even come into play as a useful model. For a given graph G, one might be able to build an auxiliary graph H, so that chip-firing results on H can be brought to bear on π(G). This opens up the theory to questions of the eigenvalues of the Laplacian of G, and so on.

The following articles are some of its application related:

1. F. R. K. Chung, Pebbling in hypercubes, SIAM J. Discrete Math. 2, 467–472 (1989).
2. S. Elledge and G. Hurlbert, An application of graph pebbling to zero-sum sequences in abelian groups, Integers: Elec. J. Combin. Number Theory 5(1):#A17, 10pp. (2005).
3. J. Gilbert, T. Lengauer and R. Tarjan, The pebbling problem is complete in polynomial space, SIAM J. Comput. 9, 513–525 (1980).
4. Y. Gurevich and S. Shelah, On finite rigid structures, J. Symbolic Logic 61, 549–562 (1996).
5. J. Hopcroft, W. Paul and L. Valiant, On time versus space, J. Assoc. Comput. Mach. 24, 332–337 (1977).
6. L. M. Kirousis and C. H. Papadimitriou, Searching and pebbling, Theoret. Comput. Sci. 47, 205–218 (1986).
7. Klawe, MariaM., The complexity of pebbling for two classes of graphs. In Y. Alavi, G. Chartrand and L. Lesniak, editors, Graph theory with applications to algorithms and computer science, 475–487, Wiley, New York (1985).
8. M. P. Knapp, 2-adic zeros of diagonal forms and distance pebbling of graphs, preprint (2012).
9. J. W. H. Liu, An application of generalized tree pebbling to sparse matrix factorization, SIAM J. Algebraic Discrete Methods 8, 375–395 (1987).
10. T.D. Parsons, Pursuit-evasion in a graph. In Y. Alani and D. R. Lick, editors, Theory and Applications of Graphs, 426–441, Springer, Berlin (1976).
11. M. S. Paterson and C. E. Hewitt, Comparative schematology. In J. Dennis, editor, Proj. MAC Conf. on Concurrent Systems and Parallel Computation, 119–127, Assoc. Computing Machinery, New York (1970).
12. R. Sethi, Complete register allocation problems, SIAM J. Comput. 4, 226–248 (1975).
13. I. Streinu, L. Theran, Sparse hypergraphs and pebble game algorithms, European J. Combin. 30, 1944–1964 (2009).

Thanks to G. H. Hurlbert, we get all these things regarding graph pebbling's application from the following papers of his:

1. G. H. Hurlbert, Recent progress in graph pebbling, Graph Theory Notes of New York XLIX, 25–37 (2005).
2. G. H. Hurlbert, General graph pebbling, Discrete Appl. Math. 161, 1221–1231 (2013).
3. G. Hurlbert, The Graph Pebbling Page, mingus.la.asu.edu/∼hurlbert/pebbling/pebb.html.