Achievable pebbling numbers

04/14/2009 - 12:15pm
04/14/2009 - 1:10pm
Cindy Wyels (Cal State University Channel Islands)

Graph pebbling arose in a search for a "natural" proof of a number-theoretic conjecture of Erdös and Lemke, and has since taken on a life of its own. Begin with a distribution of pebbles on the vertices of a graph G. A pebbling move consists of taking two pebbles from a vertex and moving one to any adjacent vertex (while discarding the second). We say the distribution is solvable if at least one pebble may be placed on any target vertex, via a sequence of pebbling moves (possibly of length 0). The pebbling number of G is the smallest integer for which every distribution with that many pebbles is solvable. The pebbling number of a graph of order n must lie between n and 2{n-1}. We ask which integers may be realized as the pebbling number of a graph of order n. We specify sufficient conditions for an integer to be realized as a pebbling number, identify where certain gaps among potential pebbling numbers must occur, and obtain improved upper bounds for pebbling numbers.

ML 211