Geodesic
1-Restricted Optimal Rubbling on Graphs
Discussiones Mathematicae. Graph Theory, Tome 39 (2019) no. 2, pp. 575-588.

Voir la notice de l'article provenant de la source Library of Science

Let G be a graph with vertex set V and a distribution of pebbles on the vertices of V. A pebbling move consists of removing two pebbles from a vertex and placing one pebble on a neighboring vertex, and a rubbling move consists of removing a pebble from each of two neighbors of a vertex v and placing a pebble on v. We seek an initial placement of a minimum total number of pebbles on the vertices in V, so that no vertex receives more than one pebble and for any given vertex v ∈ V, it is possible, by a sequence of pebbling and rubbling moves, to move at least one pebble to v. This minimum number of pebbles is the 1-restricted optimal rubbling number. We determine the 1-restricted optimal rubbling numbers for Cartesian products. We also present bounds on the 1-restricted optimal rubbling number.
Keywords: graph pebbling, graph rubbling, optimal rubbling, t -restricted optimal pebbling 
@article{DMGT_2019_39_2_a19,
     author = {Beeler, Robert A. and Haynes, Teresa W. and Murphy, Kyle},
     title = {1-Restricted {Optimal} {Rubbling} on {Graphs}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {575--588},
     publisher = {mathdoc},
     volume = {39},
     number = {2},
     year = {2019},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2019_39_2_a19/}
}
TY  - JOUR
AU  - Beeler, Robert A.
AU  - Haynes, Teresa W.
AU  - Murphy, Kyle
TI  - 1-Restricted Optimal Rubbling on Graphs
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2019
SP  - 575
EP  - 588
VL  - 39
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2019_39_2_a19/
LA  - en
ID  - DMGT_2019_39_2_a19
ER  - 
%0 Journal Article
%A Beeler, Robert A.
%A Haynes, Teresa W.
%A Murphy, Kyle
%T 1-Restricted Optimal Rubbling on Graphs
%J Discussiones Mathematicae. Graph Theory
%D 2019
%P 575-588
%V 39
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2019_39_2_a19/
%G en
%F DMGT_2019_39_2_a19
Beeler, Robert A.; Haynes, Teresa W.; Murphy, Kyle. 1-Restricted Optimal Rubbling on Graphs. Discussiones Mathematicae. Graph Theory, Tome 39 (2019) no. 2, pp. 575-588. http://geodesic.mathdoc.fr/item/DMGT_2019_39_2_a19/

[1] R.A. Beeler, T.W. Haynes and K. Murphy, An introduction to t-restricted optimal rubbling, Congr. Numer., to appear.

[2] C. Belford and N. Sieben, Rubbling and optimal rubbling of graphs, Discrete Math. 309 (2009) 3436–3446. doi:10.1016/j.disc.2008.09.035

[3] T.A. Clarke, R.A. Hochberg and G.H. Hurlbert, Pebbling in diameter two graphs and products of paths, J. Graph Theory 25 (1997) 119–128. doi:10.1002/(SICI)1097-0118(199706)25:2⟨119::AID-JGT3⟩3.0.CO;2-P

[4] R. Feng and J.Y. Kim, Graham’s pebbling conjecture on product of complete bipartite graphs, Sci. China Ser. A–Math. 44 (2001) 817–822. doi:10.1007/BF02880130

[5] H.-L. Fu and C.-L. Shiue, The optimal pebbling number of the complete m-ary tree, Discrete Math. 222 (2000) 89–100. doi:10.1016/S0012-365X(00)00008-X

[6] D.S. Herscovici, Graham’s pebbling conjecture on products of cycles, J. Graph Theory 42 (2003) 141–154. doi:10.1002/jgt.10080

[7] G.Y. Katona and L.F. Papp, The optimal rubbling number of ladders, prisms and Möbius-ladders, Discrete Appl. Math. 209 (2016) 227–246. doi:10.1016/j.dam.2015.10.026

[8] G.Y. Katona and N. Sieben, Bounds on the rubbling and optimal rubbling numbers of graphs, Graphs Combin. 29 (2013) 535–551. doi:10.1007/s00373-012-1146-2

[9] S.S. Wang, Pebbling and Graham’s conjecture, Discrete Math. 226 (2001) 431–438. doi:10.1016/S0012-365X(00)00177-1