Abstract | ||
---|---|---|
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, @c(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. |
Year | DOI | Venue |
---|---|---|
2009 | 10.1016/j.disc.2007.12.067 | Discrete Mathematics |
Keywords | Field | DocType |
complete graph,solvable,cover pebbling,threshold,bose einstein,decision problem | Discrete mathematics,Complete graph,Graph,Combinatorics,NP-complete,Decision problem,Vertex (geometry),Neighbourhood (graph theory),Pebble,Mathematics | Journal |
Volume | Issue | ISSN |
309 | 11 | Discrete Mathematics |
Citations | PageRank | References |
0 | 0.34 | 15 |
Authors | ||
3 |
Name | Order | Citations | PageRank |
---|---|---|---|
Anant P. Godbole | 1 | 95 | 16.08 |
Nathaniel G. Watson | 2 | 1 | 0.70 |
Carl R. Yerger | 3 | 2 | 1.75 |