2007/07/28 by Christopher Belford, Belford, Christopher, Nándor Sieben +1
Computer Science · #Advanced Graph Theory Research #Cellular Automata and Applications #Combinatorics (math.CO) #Computational Geometry and Mesh Generation #FOS: Mathematics
paper · pdf · doi:10.48550/arxiv.0707.4256
openalex publication_date 2007/07/28 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 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 of a graph 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 determine the rubbling and optimal rubbling number of some families of graphs including cycles.