A note on optimal pebbling of hypercubes |
| |
Authors: | Hung-Lin Fu Kuo-Ching Huang Chin-Lin Shiue |
| |
Institution: | 1. Department of Applied Mathematics, National Chiao Tung University, Hsinchu, 30050, Taiwan 2. Department of Financial and Computational Mathematics, Providence University, Shalu, 43301, Taichung, Taiwan 3. Department of Applied Mathematics, Chung Yuan Christian University, Chung Li, Taiwan
|
| |
Abstract: | A pebbling move consists of removing two pebbles from one vertex and then placing one pebble at an adjacent vertex. If a distribution δ of pebbles lets us move at least one pebble to each vertex by applying pebbling moves repeatedly(if necessary), then δ is called a pebbling of G. The optimal pebbling number f′(G) of G is the minimum number of pebbles used in a pebbling of G. In this paper, we improve the known upper bound for the optimal pebbling number of the hypercubes Q n . Mainly, we prove for large n, $f'(Q_{n})=O(n^{3/2}(\frac {4}{3})^{n})$ by a probabilistic argument. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|