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.
Read more about Graph Pebbling: π(G) — The Pebbling Number of A Graph, γ(G) — The Cover Pebbling Number of A Graph
Famous quotes containing the word graph:
“When producers want to know what the public wants, they graph it as curves. When they want to tell the public what to get, they say it in curves.”
—Marshall McLuhan (1911–1980)