Article ID Journal Published Year Pages File Type
418471 Discrete Applied Mathematics 2016 20 Pages PDF
Abstract

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 vv and ww adjacent to a vertex uu, and an extra pebble is added at vertex uu. A vertex is reachable from a pebble distribution if it is possible to move a pebble to that vertex using rubbling moves. The optimal rubbling number is the smallest number mm needed to guarantee a pebble distribution of mm pebbles from which any vertex is reachable. We determine the optimal rubbling number of ladders (Pn□P2Pn□P2), prisms (Cn□P2Cn□P2) and Möbius-ladders.

Keywords
Related Topics
Physical Sciences and Engineering Computer Science Computational Theory and Mathematics
Authors
, ,