کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4647856 | 1342380 | 2012 | 5 صفحه PDF | دانلود رایگان |
![عکس صفحه اول مقاله: Counterexamples to a monotonicity conjecture for the threshold pebbling number Counterexamples to a monotonicity conjecture for the threshold pebbling number](/preview/png/4647856.png)
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)).
Journal: Discrete Mathematics - Volume 312, Issue 15, 6 August 2012, Pages 2401–2405