| Autor: |
Győri, Ervin, Katona, Gyula Y., Papp, László F. |
| Rok vydání: |
2017 |
| Předmět: |
|
| Druh dokumentu: |
Working Paper |
| Popis: |
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$. |
| Databáze: |
arXiv |
| Externí odkaz: |
|
