Improved Pebbling Bounds

Abstract

Consider a configuration of pebbles distributed on the vertices of a connected graph of order $n$. A pebbling step consists of removing two pebbles from a given vertex and placing one pebble on an adjacent vertex. A distribution of pebbles on a graph is called solvable if it is possible to place a pebble on any given vertex using a sequence of pebbling steps. The pebbling number of a graph, denoted $f(G)$, is the minimal number of pebbles such that every configuration of $f(G)$ pebbles on $G$ is solvable. We derive several general upper bounds on the pebbling number, improving previous results.

10 pages

Cited by in corpus (3)

• Recent Progress in Graph Pebbling
• Threshold and Complexity Results for the Cover Pebbling Game
• The Pebbling Threshold of the Square of Cliques