Paper Info
Title
On pebbling threshold functions for graph sequences
Abstract
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 = (G1, G2,...,Gn,...), where Gn has n vertices, is any function t0(n) such that almost all distributions of t pebbles are solvabe when t » t0, and such that almost none are solvable when t « t0. We give bounds on pebbling threshold functions for the sequences of cliques, stars, wheels, cubes, cycles and paths.
Year
DOI
Venue
2002
10.1016/S0012-365X(01)00163-7
Discrete Mathematics
Keywords
Field
DocType
absolute guarantee,n vertex,graph sequence,pebbling step,threshold function,pebbling number,pebbling threshold function,finite number,particular vertex,function t0,sure guarantee,connected graph
Discrete mathematics,Graph,Combinatorics,Finite set,Vertex (geometry),Pebble,Connectivity,Mathematics,Threshold function,Cube
Journal
Volume
Issue
ISSN
247
1-3
Discrete Mathematics
Citations 
PageRank 
References 
13
1.60
6
Authors
4
Name
Order
Citations
PageRank
Andrzej Czygrinow122725.81
Nancy Eaton2223.20
Glenn Hurlbert313619.35
P. Mark Kayll4658.34