# Graph pebbling

**Graph pebbling** is a mathematical game and area of interest played on a graph with pebbles on the vertices. 'Game play' is composed of a series of pebbling moves. A pebbling move on a graph consists of taking two pebbles off one vertex and placing one on an adjacent vertex (the second removed pebble is discarded from play). π(*G*), the pebbling number of a graph *G* is the lowest natural number *n* that satisfies the following condition:

Given any target or 'root' vertex in the graph and any initial configuration of

npebbles on the graph, it is possible, after a series of pebbling moves, to reach a new configuration in which the designated root vertex has one or more pebbles.

For example, on a graph with 2 vertices and 1 edge connecting them the pebbling number is 2. No matter how the two pebbles are placed on the vertices of the graph it is always possible to move a pebble to any vertex in the graph. One of the central questions of graph pebbling is the value of π(*G*) for a given graph *G*.

Other topics in pebbling include cover pebbling, optimal pebbling, domination cover pebbling, bounds, and thresholds for pebbling numbers, deep graphs, and others.

## Contents

## π(*G*) — the pebbling number of a graph[edit]

The game of pebbling was first suggested by Lagarias and Saks, as a tool for solving a particular problem in number theory. In 1989 F.R.K. Chung introduced the concept in the literature^{[1]} and defined the pebbling number, π(*G*).

The pebbling number for a complete graph on *n* vertices is easily verified to be *n*: If we had (*n* − 1) pebbles to put on the graph, then we could put 1 pebble on each vertex except one; this would make it impossible to place a pebble on the last vertex. Since this last vertex could have been the designated target vertex, the pebbling number must be greater than *n* − 1. If we were to add 1 more pebble to the graph there are 2 possible cases. First, we could add it to the empty vertex, which would put a pebble on every vertex. Or secondly, we could add it to one of the vertices with only 1 pebble on them. Once any vertex has 2 pebbles on it, it becomes possible to make a pebbling move to any other vertex in the complete graph.

### π(*G*) for families of graphs[edit]

where is a complete graph on *n* vertices.

where is a path graph on *n* vertices.

where is a wheel graph on *n* vertices.

## γ(*G*) — the cover pebbling number of a graph[edit]

Crull *et al.*^{[2]} introduced the concept of cover pebbling. γ(*G*), the cover pebbling number of a graph is the minimum number of pebbles needed so that from any initial arrangement of the pebbles, after a series of pebbling moves, it is possible to have at least 1 pebble on every vertex of a graph. Vuong and Wyckoff^{[3]} proved a theorem known as the stacking theorem which essentially finds the cover pebbling number for any graph: this theorem was proved at about the same time by Jonas Sjostrand.^{[4]}

### The stacking theorem[edit]

The stacking theorem states the initial configuration of pebbles that requires the most pebbles to be cover solved happens when all pebbles are placed on a single vertex. From there they state:

Do this for every vertex *v* in *G*. *d*(*u*, *v*) denotes the distance from *u* to *v*. Then the cover pebbling number is the largest *s*(*v*) that results.

### γ(*G*) for families of graphs[edit]

where is a complete graph on *n* vertices.

where is a path on *n* vertices.

where is a wheel graph on *n* vertices.^{[5]}

## See also[edit]

## References[edit]

**^**F.R.K. Chung (1989). "Pebbling in Hypercubes".*SIAM Journal on Discrete Mathematics*.**2**(4): 467–472. doi:10.1137/0402041.**^**Betsy Crull; Tammy Cundiff; Paul Feltman; Glenn Hurlbert; Lara Pudwell; Zsuzsanna Szaniszlo; Zsolt Tuza (2005). "The cover pebbling number of graphs" (pdf).*Discrete Math*.**296**: 15–23. doi:10.1016/j.disc.2005.03.009.**^**Annalies Vuong; M. Ian Wyckoff (18 October 2004). "Conditions for Weighted Cover Pebbling of Graphs". arXiv:math/0410410.**^**Sjöstrand, Jonas (2005). "The Cover Pebbling Theorem".*Electronic Journal of Combinatorics*.**12**(1): N12. Retrieved 2008-08-02.**^**Vuong, Annalies; Ian Wyckoff, M (2004). "Cover pebbling numbers and bounds for certain families of graphs". arXiv:math/0409321.

- Hurlbert, Glenn (1999). "A survey of graph pebbling" (pdf).
*Congressus Numerantium*.**139**: 41–64. - Pachter, Lior; Snevily, Hunter; Voxman, Bill (1994). "On Pebbling Graphs" (pdf).
*Congressus Numerantium*.**107**: 65–80.