Threshold and Complexity Results for the Cover Pebbling Game
Document Type
Article
Publication Date
6-6-2009
Description
Given a configuration of pebbles on the vertices of a graph, a pebbling move is defined by removing two pebbles from some vertex and placing one pebble on an adjacent vertex. The cover pebbling number of a graph, γ (G), is the smallest number of pebbles such that through a sequence of pebbling moves, a pebble can eventually be placed on every vertex simultaneously, no matter how the pebbles are initially distributed. We determine Bose-Einstein and Maxwell-Boltzmann cover pebbling thresholds for the complete graph. Also, we show that the cover pebbling decision problem is NP-complete.
Citation Information
Godbole, Anant P.; Watson, Nathaniel G.; and Yerger, Carl R.. 2009. Threshold and Complexity Results for the Cover Pebbling Game. Discrete Mathematics. Vol.309(11). 3609-3624. https://doi.org/10.1016/j.disc.2007.12.067 ISSN: 0012-365X