Pebbling and Related Concepts in Graphs

Abstract

Suppose 2n pebbles are arbitrarily placed newlineon the vertices of an n-cube. Does there exist a method that allows us to newlinemake a sequence of moves, each move taking two pebbles off one vertex and newlineplacing one pebble on an adjacent vertex, in such a way that we can end newlineup with a pebble on any desired vertex? This question is answered in the newlineaffirmative by Chung [3]. Pebbling was first introduced into the literature by newlineChung [3]. newlineGiven a graph G, distribute k pebbles (indistinguishable markers) on its newlinevertices in some configuration C. Specifically, a configuration on a graph G is newlinea function from V (G) to N [ {0} representing an arrangement of pebbles on newlineG. For our purposes, we will always assume that G is connected. A pebbling newlinemove is defined as the removal of two pebbles from some vertex and the newlineplacement of one of these pebbles on an adjacent vertex. The pebbling newlinenumber of a connected graph G is the smallest number f(G) such that, newlinehowever f(G) pebbles are distributed on the vertices of G, we can move a newlinepebble to any root vertex by a sequence of pebbling moves [3]. Implicit in this newlinedefinition is the fact that if after moving to vertex v one desires to move to newlineanother root vertex, the pebbles reset to their original initial configuration. newline