2004/06/07 by Andrzej Czygrinow, Glenn Hurlbert
Mathematics · #math.CO #msc:05D05 #msc:05C35 #msc:05A20
published as Austral. J. Combin. 29 (2003), 201--208 · 10 pages
arxiv created 2004/06/07 · arxiv updated 2009/12/01
A configuration of pebbles on the vertices of a graph is solvable if one can place a pebble on any given root vertex via a sequence of pebbling steps. The pebbling number of a graph G is the minimum number pi(G) so that every configuration of pi(G) pebbles is solvable. A graph is Class 0 if its pebbling number equals its number of vertices. A function is a pebbling threshold for a sequence of graphs if a randomly chosen configuration of asymptotically more pebbles is almost surely solvable, while one of asymptotically fewer pebbles is almost surely not. Here we prove that graphs on n>=9 vertices having minimum degree at least floor(n/2) are Class 0, as are bipartite graphs with m>=336 vertices in each part having minimum degree at least floor(m/2)+1. Both bounds are best possible. In addition, we prove that the pebbling threshold of graphs with minimum degree d, with sqrtn << d, is O(n3/2/d), which is tight when d is proportional to n.