Title

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.

Share

COinS