Graph pebbling
One application of pebbling games is in the security analysis of memory-hard functions in cryptography.
[1] The game of pebbling was first suggested by Lagarias and Saks, as a tool for solving a particular problem in number theory.
Chung introduced the concept in the literature[2] and defined the pebbling number, π(G).
[5] A result called the stacking theorem finds the cover pebbling number for any graph.
Based on this observation, define for every vertex v in G, where d(u,v) denotes the distance from u to v. Then the cover pebbling number is the largest s(v) that results.
Left: A game with 3 pebbles which can be won in 2 moves.
Right: A game which cannot be won, despite having more pebbles than the left, because no moves can be made with singly pebbled vertices. This means that π( G ), the pebbling number of this graph, must be at least 6.