Rubbling and optimal rubbling of graphs

DOI10.1016/J.DISC.2008.09.035zbMATH Open1188.05098arXiv0707.4256OpenAlexW2075903162MaRDI QIDQ1025979FDOQ1025979

Authors: Christopher Belford, Nándor Sieben 

Publication date: 23 June 2009

Published in: Discrete Mathematics (Search for Journal in Brave)

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 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.

Full work available at URL: https://arxiv.org/abs/0707.4256

Recommendations

• Bounds on the rubbling and optimal rubbling numbers of graphs
• Bounds on the rubbling and optimal rubbling numbers of graphs
• The optimal rubbling number of ladders, prisms and Möbius-ladders
• Optimal pebbling and rubbling of graphs with given diameter
• 1-restricted optimal rubbling on graphs

zbMATH Keywords

pebblingrubblingoptimal pebblingrubbling number

Mathematics Subject Classification ID

Structural characterization of families of graphs (05C75)

Cites Work

• Pebbling in Hypercubes
• Pebbling graphs
• Optimally pebbling hypercubes and powers
• Title not available (Why is that?)
• Title not available (Why is that?)
• Pebbling and optimal pebbling in graphs
• The Complexity of Graph Pebbling
• The optimal pebbling number of the complete \(m\)-ary tree
• The cover pebbling number of graphs
• The cover pebbling theorem

Cited In (13)

• An introduction to \(t\)-restricted optimal rubbling
• Optimal pebbling and rubbling of graphs with given diameter
• Domination cover rubbling
• Total domination cover rubbling
• Cover rubbling and stacking
• Merging peg solitaire on graphs
• The optimal rubbling number of ladders, prisms and Möbius-ladders
• Cycles and girth in pebble assignment graphs
• Optimal t-rubbling on complete graphs and paths
• Bounds on the rubbling and optimal rubbling numbers of graphs
• Bounds on the rubbling and optimal rubbling numbers of graphs
• Strict optimal rubbling of graphs
• 1-restricted optimal rubbling on graphs

This page was built for publication: Rubbling and optimal rubbling of graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1025979)