Carl Yerger
Davidson College

Graph pebbling, discharging, and branches on low-diameter graphs

Abstract: 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. The pebbling number of a graph G is the smallest integer k such that given any configuration of k pebbles on G and any specified vertex v in V(G), we can send a pebble to v. We will give insights behind the proof that the maximum pebbling number of a graph of diameter three on n vertices is the floor of 3n/2 + 2, and explain why this bound is best possible. In addition we will discuss the discharging-based proof that the maximum pebbling number of a graph of diameter four is 3n/2 + O(1) and explain how this is also asymptotically best possible. This work generalizes a result of Bukh on graphs of diameter three. Further, we will give an asymptotic bound for pebbling graphs of arbitrary diameter, namely that if f(n,d) denotes the maximum pebbling number for a graph on n vertices with diameter d, f(n,d) <=(2d/2 - 1)n + O(1). This also improves another bound of Bukh. This is joint work with Noah Streib and Luke Postle, of Georgia Institute of Technology.