Katona, Gyula Y. and Papp, László F. (2015) Upper Bound on the Optimal Rubbling Number in graphs with given minimum degree. In: The 9th Hungarian-Japanese Symposium on Discrete Mathematics and Its Applications, June 2 -- 5, 2015, Fukuoka, Japán.
This is the latest version of this item.
|
Text
katona_papp_ext_cz.pdf Download (171kB) | Preview |
Abstract
A pebbling move on a graph removes two pebbles at a vertex and adds one pebble at 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 is the smallest number $m$ needed to guarantee a pebble distribution of $m$ pebbles from which any vertex is reachable. Czygrinow proved that the optimal pebbling number of a graph is at most $\frac{4n}{\delta+1}$, where $n$ is the number of the vertices and $\delta$ is the minimum degree of the graph. We improve this result and show that the optimal pebbling number is at most $\frac{3.75n}{\delta+1}$.
| 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/25978 |
Available Versions of this Item
- Upper Bound on the Optimal Rubbling Number in graphs with given minimum degree. (deposited 27 Aug 2015 12:22) [Currently Displayed]
Actions (login required)
 |
Edit Item |
