Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4647856 | Discrete Mathematics | 2012 | 5 Pages |
Graph pebbling considers the problem of transforming configurations of discrete pebbles to certain target configurations on the vertices of a graph, using the so-called pebbling move , in which two pebbles are removed from a vertex and one is placed on a neighbouring vertex. Given a graph GG, the pebbling number π(G)π(G) is the least tt such that every initial distribution of tt pebbles at the vertices of GG is solvable , that is for every target vertex vv, there is some list of pebbling moves that ends with vv having a pebble. Given a graph sequence (Gn)(Gn), the pebbling threshold τ(Gn)τ(Gn) is a sequence (an)(an) such that t=ant=an is the smallest number of pebbles such that a random configuration of tt pebbles on the vertices of GnGn is solvable with probability at least 1/21/2, in the probabilistic model where each configuration of tt pebbles on the vertices of GnGn is selected uniformly at random. This paper provides counterexamples to the following monotonicity conjecture stated by Hurlbert et al.: If (Gn)(Gn) and (Hn)(Hn) are graph sequences such that π(Gn)≤π(Hn)π(Gn)≤π(Hn), then it holds that τ(Gn)∈O(τ(Hn))τ(Gn)∈O(τ(Hn)).