Added to Favorites

Related Searches

Definitions

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. π(G), the pebbling number of a graph G is the lowest natural number that fulfills the following property:
## π(G) — the pebbling number of a graph

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 and defined the pebbling number, π(G).### π(G) for families of graphs

$scriptstylepi(K\_n),\; =,\; n$ where $K\_n$ is a complete graph on n vertices.## γ(G) — the cover pebbling number of a graph

Crull et al. 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 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.
### The stacking theorem

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:### γ(G) for families of graphs

## References

## External links

Given any target or 'root' vertex in the graph and any initial configuration of π(G) pebbles 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.

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.

$scriptstylepi(P\_n),\; =,\; 2^\{n-1\}$ where $P\_n$ is a path graph on n vertices.

$scriptstylepi(W\_n),\; =,\; n$ where $W\_n$ is a wheel graph on n vertices.

- $s(v)\; =\; sum\_\{u\; in\; V(G)\}\; 2^\{d(u,v)\}$

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.

$scriptstyle\; gamma(K\_n),\; =,\; 2n\; -\; 1$ where $scriptstyle\; K\_n$ is a complete graph on n vertices.

$scriptstylegamma(P\_n),\; =,\; 2^\{n\}-1$ where $scriptstyle\; P\_n$ is a path on n vertices.

$scriptstyle\; gamma\; (W\_n),\; =,\; 4n\; -\; 5$ where $scriptstyle\; W\_n$ is a wheel graph on n vertices.

- Glenn Hurlbert "A survey of graph pebbling".
*Congressus Numerantium*139 41--64. - Lior Pachter; Hunter Snevily and Bill Voxman "On Pebbling Graphs".
*Congressus Numerantium*107 65--80.

Wikipedia, the free encyclopedia © 2001-2006 Wikipedia contributors (Disclaimer)

This article is licensed under the GNU Free Documentation License.

Last updated on Monday September 01, 2008 at 15:41:36 PDT (GMT -0700)

View this article at Wikipedia.org - Edit this article at Wikipedia.org - Donate to the Wikimedia Foundation

This article is licensed under the GNU Free Documentation License.

Last updated on Monday September 01, 2008 at 15:41:36 PDT (GMT -0700)

View this article at Wikipedia.org - Edit this article at Wikipedia.org - Donate to the Wikimedia Foundation

Copyright © 2014 Dictionary.com, LLC. All rights reserved.