Katona, Gyula Y. and Győri, Ervin and Papp, László F. (2015) Optimal pebbling of grids. In: 13th Cologne-Twente Workshop on Graphs & Combinatorial Optimization, May 26-28, 2015, Isztanbul.
|
Text
gykp.pdf Download (236kB) | Preview |
Abstract
A pebbling move on a graph removes two pebbles at a vertex and adds one pebble at an adjacent vertex. Rubbling is a version of pebbling where an additional move is allowed. In this new move, one pebble each is removed at vertices $v$ and $w$ adjacent to a vertex $u$, and an extra pebble is added at vertex $u$. A vertex is reachable from a pebble distribution if it is possible to move a pebble to that vertex using rubbling moves. The optimal pebbling (rubbling) number is the smallest number $m$ needed to guarantee a pebble distribution of $m$ pebbles from which any vertex is reachable using pebbling (rubbling) moves. We determine the optimal rubbling number of ladders ($P_n\square P_2$), prisms ($C_n\square P_2$) and M\"oblus-ladders. We also give upper and lower bounds for the optimal pebbling and rubbling numbers of large grids ($P_n\square P_n$).
Item Type: | Conference or Workshop Item (Lecture) |
---|---|
Subjects: | Q Science / természettudomány > QA Mathematics / matematika |
Depositing User: | dr. Gyula Y. Katona |
Date Deposited: | 27 Aug 2015 12:22 |
Last Modified: | 03 Apr 2023 08:30 |
URI: | http://real.mtak.hu/id/eprint/25979 |
Actions (login required)
![]() |
Edit Item |