Graph Rubbling Numbers
Rubbling moves
One of the following:
Pebbling Move (v, v → u):
One can move two pebbles from a given vertex to one of its neighbors. However, only one pebble reaches the neighbor since the other is paid as a toll along the edge.
before

during

after




p(v, u) = (2, 0)


p_{(v, v → u)}(v, u) = (0, 1)




Strict rubbling move (v, w → u):
The two pebbles can come from different neighbors.
before

during

after




p(v, w, u) = (1, 1, 0)


p_{(v, w → u)}(v, w, u) = (0, 0, 1)




Connie & Peter
Peter the Pebbler and Connie the Configurer play the following game on a graph G. Peter buys t very expensive pebbles and gives them to Connie. Of course, Peter doesn’t want to spend too much money if he can avoid it. Connie distributes a configuration p:V_{G} → ℕ of pebbles onto the vertices of G and chooses a root vertex r. Peter will win the game if he can place a pebble on r after a sequence of rubbling moves; otherwise, Connie wins the game.
Solvability
In the case that Peter wins we say that p is rsolvable (otherwise runsolvable). If p is rsolvable for every r then p is called solvable.
rsolvable

runsolvable



Rubbling number
The pebbling number of G is denoted ρ(G) and equals the fewest number of pebbles Peter must buy in order to guarantee victory. That is, if Peter buys ρ(G) pebbles then every possible configuration of Connie’s is solvable, while if Peter buys ρ(G) − 1 pebbles then Connie can find a configuration that is runsolvable for some r.
ρ(G) = 4, π(G) = 5


http://www.cefns.nau.edu/~ns46/pebbling/census.html
Bounds
d = diameter, n = number of vertices

More options upper bound. ρ(G) ≤ π(G) It is easier to reach a vertex with more move options.

Depth lower bound. 2^{d} ≤ ρ(G) Connie can place all the pebbles on a vertex as distance d from r.

Pigeon whole upper bound.ρ(G) ≤ (n − d + 1)(2^{d − 1} − 1) + 2 [3].

ρ(G) < n is possible.
First Results

Paths. ρ(P_{n}) = 2^{n − 1}

Cliques. ρ(K_{n}) = 2

Wheels. ρ(W_{n}) = 4

Complete bipartite graphs. ρ(K_{m, n}) = 4

Cubes. ρ(Q_{n}) = 2^{n}

Petersen. ρ(P) = 5

Lemke. ρ(L) = 8
Trees
ρ(T) = 2^{p1} + ∑^{m}_{i = 2}2^{pi − 1} − m + 1 where (p_{1}, …, p_{m}) is the length sequence of a maximum path partition for T.
ρ(T) = (2^{4} − 1) + (2^{1} − 1) + (2^{0} − 1) + 1 = 17 where (4, 2, 1) is the length sequence.
Cycle graphs
ρ(C_{2k}) = 2^{k} and ρ(C_{2k + 1}) = ⌊(7⋅2^{k − 1} − 2)/(3)⌋ + 1 where C_{n} is the cycle graph with n vertices. [1]
Graham’s conjecture
The conjecture fails for rubbling.

Example: ρ(C_{3}□C_{3}) = 5 > 4 = 2⋅2 = ρ(C_{3})ρ(C_{3})
C_{3}□C_{3}

C_{3}



Complexity
The decision problem whether a vertex is reachable from a given configuration is NPcomplete.
Optimal Rubbling Numbers
Minimum number ρ_{opt}(G) of pebbles in a chosen pebble distribution from which any vertex is reachable is called the optimal rubbling number.

Example: ρ_{opt}(P_{6}) = 4
Results

Paths. ρ_{opt}(P_{n}) = ⌈(n + 1)/(2)⌉

Cycles. ρ_{opt}(C_{n}) = ⌈(n)/(2)⌉

Cliques. ρ_{opt}(K_{n}) = 2

Wheels. ρ_{opt}(W_{n}) = 2

Complete bipartite graphs. ρ_{opt}(K_{m, n}) = 3

Petersen. ρ_{opt}(P) = 4

Prisms ad Ladders. ρ_{opt}(P_{3k + r}□P_{2}) = 2k + 1 + ⌈(r)/(3)⌉ [5]

Caterpillars. [4]

Question: ρ_{opt}(Q_{n}) = ? We have ρ_{opt}(Q_{2}) = 2, ρ_{opt}(Q_{3}) = 3, ρ_{opt}(Q_{4}) = 4, ρ_{opt}(Q_{5}) = 6.

Question: ρ_{opt}(P_{n}□P_{m}) = ?

Question: ρ_{opt}(C_{n}□C_{m}) = ?

Question: How does optimal rubbling change if we only allow strict rubbling moves?
Cover Rubbling Conjecture
The cover pebbling and cover rubbling numbers are the same for all graphs. Stacking Lemma remains true.
tRubbling Numbers
Minimum number ρ_{t}(G) of pebbles to make any vertex reachable with t pebbles no matter how the pebbles are distributed is the trubbling number.
Results

Trees. ρ_{t}(T) = t2^{p1} + ∑^{m}_{i = 2}2^{pi − 1} − m + 1

mary trees. [2]

Conjecture: Cycle. ρ_{t}(C_{2k + 1}) = (2^{k − 1}7 + ( − 1)^{k})/(3) + (t − 1)2^{k} and ρ_{t}(C_{2k}) = t2^{k}.

Question: What is ρ_{t}(G) for simple graph families?
References

Christopher Belford and Nándor Sieben, Rubbling and optimal rubbling of graphs, Discrete Math. 2009, volume 309, number 10 , p. 34363446,

Lisa Danz, Optimal trubbling of complete mary trees. 2010. REU project report, University of Minnesota Duluth, Department of Mathematics and Statistics.

Gyula Y. Katona and Nándor Sieben, Bounds on the Rubbling and Optimal Rubbling Numbers of Graphs, Graphs and Combinatorics 29(3): 535551 (2013)

László Papp, Optimal rubbling numbers of graphs (in Hungarian). 2010. thesis, Budapest University of Technology and Economics, Department of Computer Science and Information Theory.

László Papp, Optimal rubbling numbers of prisms and ladders (in Hungarian). 2011. preprint, Budapest University of Technology and Economics, Department of Computer Science and Information Theory.

Gyula Y. Katona and László Papp, The Optimal Rubbling Number of Ladders, Prisms and Möbiusladders http://arxiv.org/abs/1411.0923
Links