A Survey of Graph Pebbling

2004/06/01 by Glenn Hurlbert · 4 citations
Mathematics · #math.CO #msc:05C35 #msc:05C99 #msc:05D05 #msc:06A07 #msc:11B75

paper · pdf

published as Congressus Numerantium 139 (1999), 41-64 · 24 pages

arxiv created 2004/06/01 · arxiv updated 2009/12/01

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.

Cited by

• Strong hub cover pebbling number
• Applying Hurlbert's Linear Optimization Technique to Establish Bounds on Pebbling Numbers
• The only Class 0 Flower snark is the smallest
• A Weight Function Lemma Heuristic for Graph Pebbling

Related

• Counterexamples to a Monotonicity Conjecture for the Threshold Pebbling\n Number
• On the Pebbling Threshold Spectrum
• An Exploration of Graph Pebbling
• Thresholds for families of multisets, with an application to graph pebbling
• The Pebbling Threshold of the Square of Cliques