Pebbling in Hypercubes

Fan Chung · SIAM Journal on Discrete Mathematics · 1989

This paper considers the following game on a hypercube, first suggested by Lagarias and Saks. Suppose $2^n$ pebbles are distributed onto vertices of an n-cube (with $2^n$ vertices). A pebbling step is to remove two pebbles from some vertex and then place one pebble at an adjacent vertex. The question of interest is to determine if it is possible to get one pebble to a specified vertex by repeatedly using the pebbling steps from any starting distribution of $2^n$ pebbles. This question is answered affirmatively by proving several stronger and more general results.

Cited by 173 works. doi:10.1137/0402041

Authors

References