A note on optimal pebbling of hypercubes

Hung-Lin Fu, Kuo Ching Huang*, Chin Lin Shiue

*Corresponding author for this work

Research output: Contribution to journalArticle

7 Scopus citations

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′(Qn) = O n3/2(4/3)n by a probabilistic argument.

Original languageEnglish
Pages (from-to)597-601
Number of pages5
JournalJournal of Combinatorial Optimization
Volume25
Issue number4
DOIs
StatePublished - 1 May 2013

Keywords

  • Hypercubes
  • Optimal pebbling

Fingerprint Dive into the research topics of 'A note on optimal pebbling of hypercubes'. Together they form a unique fingerprint.

Cite this