A Survey of Graph Pebbling

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 (13)

• Recent Progress in Graph Pebbling
• Conditions for Weighted Cover Pebbling of Graphs
• Cover pebbling numbers and bounds for certain families of graphs
• Domination Cover Pebbling: Graph Families
• The Complexity of Pebbling and Cover Pebbling
• Cover Pebbling Hypercubes
• Cover pebbling cycles and certain graph products
• The Pi-Pebbling Function
• The Cover Pebbling Number of Graphs
• Girth, Pebbling, and Grid Thresholds
• Pebbling in Dense Graphs
• On the Pebbling Threshold Spectrum
• Thresholds for families of multisets, with an application to graph pebbling