Bounds on the Rubbling and Optimal Rubbling Numbers of Graphs

Details Bounds on the Rubbling and Optimal Rubbling Numbers of Graphs Bounds on the Rubbling and Optimal Rubbling Numbers of Graphs

2010-09-27

arxiv.org/abs/1009.5162v1

Mathematics

Combinatorics

Scientific paper

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 rubbling number 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 give bounds for rubbling and optimal rubbling numbers. In particular, we find an upper bound for the rubbling number of $n$-vertex, diameter $d$ graphs, and estimates for the maximum rubbling number of diameter 2 graphs. We also give a sharp upper bound for the optimal rubbling number, and sharp upper and lower bounds in terms of the diameter.

Affiliated with

Also associated with

No associations

Rating

Bounds on the Rubbling and Optimal Rubbling Numbers of Graphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Bounds on the Rubbling and Optimal Rubbling Numbers of Graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Bounds on the Rubbling and Optimal Rubbling Numbers of Graphs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-517608