The Optimal Rubbling Number of Ladders, Prisms and Möbius-ladders

Gyula Y. Katona; László F. Papp

doi:10.1016/j.dam.2015.10.026

paper

The Optimal Rubbling Number of Ladders, Prisms and Möbius-ladders

arXiv:1411.0923 · doi:10.1016/j.dam.2015.10.026

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 $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 optimal rubbling number is the smallest number $m$ needed to guarantee a pebble distribution of $m$ pebbles from which any vertex is reachable. We determine the optimal rubbling number of ladders ( $P_{n} □ P_{2}$ ), prisms ( $C_{n} □ P_{2}$ ) and Möblus-ladders.

References in corpus (2)

Cited by in corpus (1)

A note on the optimal rubbling in ladders and prisms