TY - JOUR

T1 - On pebbling threshold functions for graph sequences

AU - Czygrinow, Andrzej

AU - Eaton, Nancy

AU - Huribert, Glenn

AU - Kayll, P. Mark

N1 - Funding Information:
∗Corresponding author. E-mail addresses: [email protected] (A. Czygrinow), [email protected] (N. Eaton), [email protected] (G. Hurlbert), [email protected] (P.M. Kayll). 1Visiting Professor. 2On sabbatical at Arizona State University. 3Partially supported by the Rocky Mountain Mathematics Consortium.

PY - 2002/3/28

Y1 - 2002/3/28

N2 - Given a connected graph G, and a distribution of / 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 /, 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 'S = (Gi,G2,...,G,...), where G has n vertices, is any function ta(n) such that almost all distributions of / pebbles are solvable when t>t0, and such that almost none are solvable when t<$to. We give bounds on pebbling threshold functions for the sequences of cliques, stars, wheels, cubes, cycles and paths.

AB - Given a connected graph G, and a distribution of / 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 /, 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 'S = (Gi,G2,...,G,...), where G has n vertices, is any function ta(n) such that almost all distributions of / pebbles are solvable when t>t0, and such that almost none are solvable when t<$to. We give bounds on pebbling threshold functions for the sequences of cliques, stars, wheels, cubes, cycles and paths.

KW - Pebbling number

KW - S0012-365X(01)00163-7

KW - Threshold function

UR - http://www.scopus.com/inward/record.url?scp=31244437193&partnerID=8YFLogxK

U2 - 10.1016/S0012-365X(01)00163-7

DO - 10.1016/S0012-365X(01)00163-7

M3 - Article

AN - SCOPUS:31244437193

SN - 0012-365X

VL - 247

SP - 93

EP - 105

JO - Discrete Mathematics

JF - Discrete Mathematics

IS - 1-3

ER -