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.

Two graphs with target vertices shown in red.

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.