Graph pebbling

From Wikipedia, the free encyclopedia

The introduction to this article provides insufficient context for those unfamiliar with the subject matter.
Please help improve the introduction to meet Wikipedia's layout standards. You can discuss the issue on the talk page.

There are very few or no other articles that link to this one.
Please help introduce links in articles on related topics. After links have been created, remove this message.
This article has been tagged since February 2007.

Graph Pebbling is a game played on a graph with pebbles on the vertices. It consists 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 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 move a pebble to any vertex in the graph.

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.

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

1 π(G) - The Pebbling Number of a Graph
- 1.1 π(G) for families of graphs
2 γ(G) - The Cover Pebbling Number of a Graph
- 2.1 The Stacking Theorem
- 2.2 γ(G) for families of graphs
3 References
4 External links

[edit] π(G) - The Pebbling Number of a Graph

The game of pebbling was first suggested by Lagarias and Saks. In 1989 F.R.K. Chung introduced the concept in literature and defined the pebbling number, π(G). π(G), the 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 move a pebble to any vertex in the graph.

The pebbling number for complete graphs are easy to see. It's simply n pebbles. If we had (n-1) pebbles to put on the graph, then we could put 1 pebble on each vertex except one. Which would make it impossible to place a pebble on the last vertex. If we were to add 1 more pebble to the graph there are 2 general 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.

[edit] π(G) for families of graphs

π( $K n$ ) = n Where $K n$ is a complete graph on n vertices.

π( $P n$ ) = $2 n - 1$ Where $P n$ is a path graph on n vertices.

π( $W n$ ) = n Where $W n$ is a wheel graph on n vertices.

[edit] γ(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.

[edit] 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:

$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.

[edit] γ(G) for families of graphs

γ( $K n$ ) = 2n - 1 Where $K n$ is a complete graph on n vertices.

γ( $P n$ ) = $2 n - 1$ Where $P n$ is a path graph on n vertices.

γ( $W n$ ) = 4n – 5 Where $W n$ is a wheel graph on n vertices.

[edit] References

Glenn Hurlbert, A survey of graph pebbling, Congressus Numerantium 139 (1999), 41--64. Available via pdf at [1]

Lior Pachter, Hunter Snevily and Bill Voxman, "On Pebbling Graphs", Congressus Numerantium 107 (1994), 65--80. Available via pdf at [2]

Betsy Crull, Tammy Cundiff, Paul Feltman, Glenn Hurlbert, Lara Pudwell, Zsuzsanna Szaniszlo, Zsolt Tuza, The cover pebbling number of graphs, Discrete Math. 296 (2005), 15--23. vailable via pdf at [3]