Pebbling Graphs of Diameter Three
by
Carl Yerger
Georgia Institute of Technology
Coauthors: Luke Postle, Noah Streib

Given a configuration of pebbles on the vertices of a connected graph G, a pebbling move is defined as the removal of two pebbles from some vertex, and the placement of one of these on an adjacent vertex. A graph is called pebbleable if for each vertex v there is a sequence of pebbling moves so that at least one pebble can be placed on vertex v. The pebbling number of a graph G is the smallest integer k such that G is pebbleable given any configuration of k vertices on G. We improve on the bound of Bukh by showing that the pebbling number of a graph of diameter 3 on n vertices is at most ⌊[3/2]n⌋+ 2. In addition, this technique allows us to characterize the pebbling number of graphs with diameter 2 in a simple manner.

Date received: April 11, 2008