Graph pebbling is a mathematical game played on a graph with zero or more pebbles on each of its vertices. 'Game play' is composed of a series of pebbling moves. A pebbling move on a graph consists of choosing a vertex with at least two pebbles, removing two pebbles from it, and adding one to 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 possibly-empty 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 arrive at the desired result of the chosen vertex having a pebble; if the initial configuration is the configuration with one pebble per vertex, then the objective is trivially accomplished with zero pebbling moves. 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, as well as deep graphs.
One application of pebbling games is in the security analysis of memory-hard functions in cryptography.[1]
^Alwen, Joël; Serbinenko, Vladimir (2014), High Parallel Complexity Graphs and Memory-Hard Functions, retrieved 2024-01-15
of a series of pebbling moves. A pebbling move on a graph consists of choosing a vertex with at least two pebbles, removing two pebbles from it, and adding...
mathematics, graph theory is the study of graphs, which are mathematical structures used to model pairwise relations between objects. A graph in this context...
Philosopher's football Rhythmomachy Tak Tic-tac-toe Tic-tac-toe variants Graphpebbling Hackenbush Chopsticks (hand game) Mancala Nim Sim Sprouts Four fours...
mathematics education, and who is known for her research in graphpebbling and radio coloring of graphs. She is a professor of mathematics at California State...
Graham–Pollak theorem and Graham's pebbling conjecture in graph theory, the Coffman–Graham algorithm for approximate scheduling and graph drawing, and the Graham...
algebra, but her more recent research concerns graph theory, including graphpebbling and line graphs. She is a professor of mathematics at the University...
In mathematics, a dense graph is a graph in which the number of edges is close to the maximal number of edges (where every pair of vertices is connected...
In graph theory, the Laman graphs are a family of sparse graphs describing the minimally rigid systems of rods and joints in the plane. Formally, a Laman...
minimum of information. One observer derided the concept as being "one view-graph deep" and "unencumbered by practical engineering considerations or the laws...
Laplacians of graphs in terms of their number of edges Graham's pebbling conjecture on the pebbling number of Cartesian products of graphs Meyniel's conjecture...
distinguish between a certain class of expander graphs called "small set expanders" and other graphs that are very far from being small set expanders...
The pebble motion problems, or pebble motion on graphs, are a set of related problems in graph theory dealing with the movement of multiple objects ("pebbles")...
One of his most cited papers is with Lior Pachter and Bill Voxman on Graphpebbling. This paper and Hunter's later paper with Foster added several conjectures...
In graph theory, a path decomposition of a graph G is, informally, a representation of G as a "thickened" path graph, and the pathwidth of G is a number...
showed that other than one exceptional graph on 7 vertices, it is possible to obtain all permutations unless the graph is bipartite, in which case exactly...
have different character graphs and sounds representing mythological and legendary birds of China. The Chinese characters or graphs used have varied over...
a graph that bounds the number of edges in any subgraph. The property of having a particular matroid as its density measure is invariant under graph isomorphisms...
different kinds of network graphs, such as undirected rings, unidirectional rings, complete graphs, grids, directed Euler graphs, and others. A general method...
In graph theory, the cutwidth of an undirected graph is the smallest integer k {\displaystyle k} with the following property: there is an ordering of...
StormCrawler, in particular: Crawling the German Health Web: Exploratory Study and Graph Analysis. The generation of a multi-million page corpus for the Persian...
Global Information