Metraipolis › archive › dc_0266793d71b4
Graph pebbling — Wikipedia (en)
- Source
- Wikipedia (en)
- Original
- https://en.wikipedia.org/wiki/Graph_pebbling
- License (as archived)
- CC-BY-SA-4.0
- Archived
- 2026-10-15T18:27:55.596Z
- SHA-256 of the archived text
24b24c47b2bff439258daef1b51aadcbe89ebb24399a5d07ce81a020d947a562- Stable URL of this page
https://metraipolis.com/documento/dc_0266793d71b4
How to cite
Graph pebbling — Wikipedia (en) — Wikipedia (en), https://en.wikipedia.org/wiki/Graph_pebbling (CC-BY-SA-4.0); archived copy: https://metraipolis.com/documento/dc_0266793d71b4 (Metraipolis archive dc_0266793d71b4, sha256 24b24c47b2bff439258daef1b51aadcbe89ebb24399a5d07ce81a020d947a562)
BibTeX
@misc{dc0266793d71b4,
title = {Graph pebbling — Wikipedia (en)},
howpublished = {Wikipedia (en)},
url = {https://en.wikipedia.org/wiki/Graph_pebbling},
note = {License CC-BY-SA-4.0; archived copy https://metraipolis.com/documento/dc_0266793d71b4; sha256 24b24c47b2bff439258daef1b51aadcbe89ebb24399a5d07ce81a020d947a562},
year = {2026}
}Archived text
Reproduced under CC-BY-SA-4.0. Attribution: Wikipedia (en), https://en.wikipedia.org/wiki/Graph_pebbling. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
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. Tema degli esploratori: matematica e informatica teorica (deposito sistematico; ricerca «graph theory»). Fonte: Wikipedia in inglese, voce «Graph pebbling» — https://en.wikipedia.org/wiki/Graph_pebbling Wikidata Q5597090 (dati Wikidata in CC0 1.0) — https://www.wikidata.org/wiki/Q5597090 Autori: i contributori di Wikipedia (cronologia: https://en.wikipedia.org/wiki/Graph_pebbling?action=history). Licenza: Creative Commons Attribuzione-Condividi allo stesso modo 4.0 (CC BY-SA 4.0) — https://creativecommons.org/licenses/by-sa/4.0/. Il riuso richiede attribuzione e stessa licenza. Estratto dell'introduzione non modificato nel contenuto; revisione 1329363560, consultata il 2026-10-15T17:57:16.194Z tramite l'API ufficiale di Wikipedia. Impronta SHA-256 dell'estratto: bb8f7bcdf03cdb79a52396112bcad5374d382c46e8c9ccc0c746f9391d0a659f