1-restricted optimal rubbling on graphs
Author(s) -
Robert A. Beeler,
Teresa W. Haynes,
Kyle Murphy
Publication year - 2018
Publication title -
discussiones mathematicae graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.476
H-Index - 19
eISSN - 2083-5892
pISSN - 1234-3099
DOI - 10.7151/dmgt.2102
Subject(s) - pebble , vertex (graph theory) , combinatorics , mathematics , cartesian product , graph , discrete mathematics , geomorphology , geology
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.
Accelerating Research
Robert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom
Address
John Eccles HouseRobert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom