Return to search

Threshold and Complexity Results for the Cover Pebbling Game

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.

Identiferoai:union.ndltd.org:ETSU/oai:dc.etsu.edu:etsu-works-18301
Date06 June 2009
CreatorsGodbole, Anant P., Watson, Nathaniel G., Yerger, Carl R.
PublisherDigital Commons @ East Tennessee State University
Source SetsEast Tennessee State University
Detected LanguageEnglish
Typetext
SourceETSU Faculty Works

Page generated in 0.0019 seconds