A note on optimal pebbling of hypercubes

A note on optimal pebbling of hypercubes

0.00 Avg rating0 Votes
Article ID: iaor20132800
Volume: 25
Issue: 4
Start Page Number: 597
End Page Number: 601
Publication Date: May 2013
Journal: Journal of Combinatorial Optimization
Authors: , ,
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 ( 4 3 ) n ) equ1 by a probabilistic argument.

Reviews

Required fields are marked *. Your email address will not be published.