On pebbling threshold functions for graph sequences

Given a connected graph G, and a distribution of t pebbles to the vertices of G, a pebbling step consists of removing two pebbles from a vertex v and placing one pebble on a neighbor of v. For a particular vertex r, the distribution is r-solvable if it is possible to place a pebble on r after a finite number of pebbling steps, The distribution is solvable if it is r-solvable for every r. The pebbling number of G is the least number t, so that every distribution of t pebbles is solvable. In this paper we are not concerned with such an absolute guarantee but rather an almost sure guarantee. A threshold function for a sequence of graphs G = (G(1), G(2),..., G(n),...), where G(n) has n vertices, is any function t(0)(n) such that almost all distributions of t pebbles are solvable when t much greater than t(0), and such that almost none are solvable when t much less than t(0). We give bounds on pebbling threshold functions for the sequences of cliques, stars, wheels, cubes, cycles and paths. (C) 2002 Elsevier Science B.V. All rights reserved.