Graph pebbling


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

Contents

π(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[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

\scriptstyle\pi(K_n)\, =\, n where Kn is a complete graph on n vertices.

\scriptstyle\pi(P_n)\, =\, 2^{n-1} where Pn is a path graph on n vertices.

\scriptstyle\pi(W_n)\, =\, n where Wn is a wheel graph on n vertices.

γ(G) — the cover pebbling number of a graph

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

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.

γ(G) for families of graphs

\scriptstyle \gamma(K_n)\, =\, 2n - 1 where \scriptstyle K_n is a complete graph on n vertices.

\scriptstyle\gamma(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.

References

  1. ^ F.R.K. Chung (1989). "Pebbling in Hypercubes". SIAM Journal on Discrete Mathematics 2 (4): 467–472. doi:10.1137/0402041. 
  2. ^ 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. http://mingus.la.asu.edu/~hurlbert/pebbling/papers/CCFHPSZ_CPN.pdf. 
  3. ^ Annalies Vuong; M. Ian Wyckoff (18 October 2004). "Conditions for Weighted Cover Pebbling of Graphs". arXiv:math/0410410 [math.CO]. 
  4. ^ Sjöstrand, Jonas (2005). "The Cover Pebbling Theorem". Electronic Journal of Combinatorics 12 (1): N12. http://www.combinatorics.org/Volume_12/Abstracts/v12i1n22.html. Retrieved 2008-08-02. 

External links


Wikimedia Foundation. 2010.

Look at other dictionaries:

  • List of graph theory topics — This is a list of graph theory topics, by Wikipedia page. See glossary of graph theory for basic terminology Contents 1 Examples and types of graphs 2 Graph coloring 3 Paths and cycles 4 …   Wikipedia

  • Rook's graph — infobox graph name = Rook s graph image caption = 8x8 Rook s graph vertices = nm edges = nm ( n + m )/2 nm diameter = 2 chromatic number = max( n , m ) chromatic index = girth = 3 (if max( n , m ) ≥ 3) properties = regular, vertex transitive,… …   Wikipedia

  • List of mathematics articles (G) — NOTOC G G₂ G delta space G networks Gδ set G structure G test G127 G2 manifold G2 structure Gabor atom Gabor filter Gabor transform Gabor Wigner transform Gabow s algorithm Gabriel graph Gabriel s Horn Gain graph Gain group Galerkin method… …   Wikipedia

  • Mathematical game — This article is about using mathematics to study the inner workings of multiplayer games which, on the surface, may not appear mathematical at all. For games that directly involve mathematics in their play, see mathematical puzzle. Mathematical… …   Wikipedia

  • Pursuit-evasion — (variants of which are referred to as cops and robbers and graph searching) is a family of problems in mathematics and computer science in which one group attempts to track down members of another group in an environment. Early work on problems… …   Wikipedia