Monir Elias Bounadi: The Foundations of Graph Pebbling

Graph pebbling modeling started as a method for solving a combinatorial number theory conjecture by Erdős and Lemke. Using this method, Chung proved the conjecture in 1989. Since then, the literature has grown considerably. Several variations and possible applications have been discussed, in graph theory, computer science and network optimization.

The main focus in graph pebbling is graphs, mathematical structures modeling binary relations between vertices. To every vertex in some graph we assign a number of pebbles. If two pebbles are moved across an edge joining two distinct vertices, one pebble arrives and one pebble is lost. This is called a pebbling step.

The basic question in graph pebbling asks if one may from a given distribution of pebbles on a set of vertices move to another distribution on the same set via a series of pebbling steps.

In this Master's thesis we approach the above question using two models: a deterministic, which includes the notion of a pebbling number, and a probabilistic, which includes the notion of a threshold.

For both these models we clarify earlier proofs, and provide new proofs, of foundational theorems in graph pebbling. These results constitute the backbone for our discussion on recent research, which concentrates on generalizing and extending central notions in graph pebbling, for example the generalized idea of a pebbling number: the pi-pebbling function. Simultaneously, a corollary to the so called cover pebbling theorem is derived. This corollary lets us prove established, and newly found, theorems.

Regarding applications in graph pebbling, we argue that one should generalize existing results, and incorporate directed graphs into a bigger part of the theory. We suggest how this can be done.