کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4650551 | 1342492 | 2008 | 11 صفحه PDF | دانلود رایگان |
![عکس صفحه اول مقاله: On the pebbling threshold of paths and the pebbling threshold spectrum On the pebbling threshold of paths and the pebbling threshold spectrum](/preview/png/4650551.png)
A configuration of pebbles on the vertices of a graph is solvable if one can place a pebble on any given root vertex via a sequence of pebbling steps. A function is a pebbling threshold for a sequence of graphs if a randomly chosen configuration of asymptotically more pebbles is almost surely solvable, while one of asymptotically fewer pebbles is almost surely not. In this paper we tighten the gap between the upper and lower bounds for the pebbling threshold for the sequence of paths in the multiset model. We also find the pebbling threshold for the sequence of paths in the binomial model. Finally, we show that the spectrum of pebbling thresholds for graph sequences in the multiset model spans the entire range from n1/2n1/2 to n, answering a question of Czygrinow, Eaton, Hurlbert and Kayll. What the spectrum looks like above n remains unknown.
Journal: Discrete Mathematics - Volume 308, Issue 15, 6 August 2008, Pages 3297–3307