Pebbling Number

Define a pebbling move as a transer 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  of a graph  is the smallest  such that every supply of  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).

graph	pebbling number
complete bipartite graph
complete graph
cycle graph
hypercube graph
path graph

The pebbling number satisfies a number of bounds. Let  be the vertex count,  the graph diameter, and  the domination number of a graph .

Breadth lower bounds:

(1)

Cut lower bound (which  contained a cut vertex ):

(2)

Depth lower bound:

(3)

Pigeonhole upper bound:

(4)

Sharper bounds:

			(5)
			(6)
			(7)

(Hurlbert).

For a graph with ,

(8)

where  is the vertex count of  (Hurlbert 2011).

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.