A Survey of Graph Pebbling
arXiv:math/0406024
Abstract
We survey results on the pebbling numbers of graphs as well as their historical connection with a number-theoretic question of Erd\H os and Lemke. We also present new results on two probabilistic pebbling considerations, first the random graph threshold for the property that the pebbling number of a graph equals its number of vertices, and second the pebbling threshold function for various natural graph sequences. Finally, we relate the question of the existence of pebbling thresholds to a strengthening of the normal property of posets, and show that the multiset lattice is not supernormal.
24 pages
Cited by in corpus (30)
- Recent Progress in Graph Pebbling
- Sierpi\' nski Gasket Graphs and Some of Their Properties
- Conditions for Weighted Cover Pebbling of Graphs
- Cover pebbling numbers and bounds for certain families of graphs
- The Optimal Rubbling Number of Ladders, Prisms and Möbius-ladders
- The Complexity of Pebbling and Cover Pebbling
- Domination Cover Pebbling: Graph Families
- Cover Pebbling Hypercubes
- A linear optimization technique for graph pebbling
- Cover pebbling cycles and certain graph products
- On a combinatorial problem of Erdos, Kleitman and Lemke
- Graph pegging numbers
- Generalizations of Graham's Pebbling Conjecture
- The Pebbling Threshold of the Square of Cliques
- Weighted pebbling numbers on graphs
- On an inverse problem of Erd\H os, Kleitman, and Lemke
- Threshold and Complexity Results for the Cover Pebbling Game
- The Pi-Pebbling Function
- Pegging Numbers For Various Tree Graphs
- Bounds on the Rubbling and Optimal Rubbling Numbers of Graphs
- The Game of Blocking Pebbles
- Thresholds for families of multisets, with an application to graph pebbling
- On the Assignment Graphs of Oriented Graphs
- Critical Pebbling Numbers of Graphs
- Pebbling in Dense Graphs
- Girth, Pebbling, and Grid Thresholds
- Rubbling and Optimal Rubbling of Graphs
- On the Pebbling Threshold Spectrum
- Counterexamples to a Monotonicity Conjecture for the Threshold Pebbling Number
- The Cover Pebbling Number of Graphs