Cover Rubbling and Stacking
Document Type
Article
Publication Date
11-1-2020
Description
A pebble distribution places a nonnegative number of pebbles on the vertices of a graph G. In graph rubbling, the pebbles can be redistributed using pebbling and rubbling moves, typically with the goal of reaching some target pebble distribution. In graph pebbling, only the pebbling move is allowed. The cover pebbling number is the smallest k such that from any initial distribution of k pebbles, it is possible that after a series of pebbling moves there is at least one pebble on every vertex of G. The Cover Pebbling Theorem asserts that to determine the cover pebbling number of a graph, it is sufficient to consider the pebbling distributions that initially place all pebbles on a single vertex. In this paper, we prove a rubbling analogue of the Cover Pebbling Theorem, providing an answer to an open question of Belford and Sieben (2009). In addition, we prove a stronger version of the Cover Rubbling Theorem for trees.
Citation Information
Haynes, Teresa W.; and Keaton, Rodney. 2020. Cover Rubbling and Stacking. Discrete Mathematics. Vol.343(11). https://doi.org/10.1016/j.disc.2020.112080 ISSN: 0012-365X