Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
6423967 | Electronic Notes in Discrete Mathematics | 2011 | 6 Pages |
A pebbling move on a graph removes two pebbles at a vertex and adds one pebble at an adjacent vertex. Rubbling is a version of pebbling where an additional move is allowed. In this new move, one pebble each is removed at vertices v and w adjacent to a vertex u, and an extra pebble is added at vertex u. A vertex is reachable from a pebble distribution if it is possible to move a pebble to that vertex using rubbling moves. The rubbling number is the smallest number m needed to guarantee that any vertex is reachable from any pebble distribution of m pebbles. The optimal rubbling number is the smallest number m needed to guarantee a pebble distribution of m pebbles from which any vertex is reachable. We give bounds for rubbling and optimal rubbling numbers.