Rubbling and optimal rubbling of graphs

DOI10.1016/J.DISC.2008.09.035MaRDI QIDQ1025979zbMATH OpenOpenAlexFDO

Authors Christopher Belford, Nándor Sieben

Publication date 23 June 2009

Published in Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

pebblingrubblingoptimal pebblingrubbling number

Mathematics Subject Classification ID

Structural characterization of families of graphs (05C75)

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.

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

Cites work

• scientific article; zbMATH DE number 1145909 (Why is no real title available?)
• scientific article; zbMATH DE number 1439473 (Why is no real title available?)
• Optimally pebbling hypercubes and powers
• Pebbling and optimal pebbling in graphs
• Pebbling graphs
• Pebbling in Hypercubes
• The Complexity of Graph Pebbling
• The cover pebbling number of graphs
• The cover pebbling theorem
• The optimal pebbling number of the complete \(m\)-ary tree

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
• The optimal rubbling number of ladders, prisms and Möbius-ladders
• Merging peg solitaire on graphs
• Cycles and girth in pebble assignment graphs
• Bounds on the rubbling and optimal rubbling numbers of graphs
• Optimal t-rubbling on complete graphs and paths
• 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)