Back to Search Start Over

Optimal pebbling and rubbling of graphs with given diameter

Authors :
Győri, Ervin
Katona, Gyula Y.
Papp, László F.
Publication Year :
2017

Abstract

A pebbling move on a graph removes two pebbles from a vertex and adds one pebble to an adjacent vertex. A vertex is reachable from a pebble distribution if it is possible to move a pebble to that vertex using pebbling moves. The optimal pebbling number $\pi_{opt}$ is the smallest number $m$ needed to guarantee a pebble distribution of $m$ pebbles from which any vertex is reachable. A rubbling move is similar to a pebbling move, but it can remove the two pebbles from two different vertex. The optimal rubbling number $\rho_{opt}$ is defined analogously to the optimal pebbling number. In this paper we give lower bounds on both the optimal pebbling and rubbling numbers by the distance $k$ domination number. With this bound we prove that for each $k$ there is a graph $G$ with diameter $k$ such that $\rho_{opt}(G)=\pi_{opt}(G)=2^k$.

Subjects

Subjects :
Mathematics - Combinatorics

Details

Database :
arXiv
Publication Type :
Report
Accession number :
edsarx.1708.09177
Document Type :
Working Paper