The Foundations of Graph Pebbling

Graph pebbling modeling started as a method for solving a combinatorialnumber theory conjecture by Erdös and Lemke. Using thismethod, Chung proved the conjecture in 1989. Since then, the literaturehas grown considerably. Several variations and possible applicationshave been discussed, in graph theory, computer science andnetwork optimization. The main focus in graph pebbling is graphs, mathematical structuresmodeling binary relations between vertices. To every vertex insome graph we assign a number of pebbles. If two pebbles are movedacross an edge joining two distinct vertices, one pebble arrives andone pebble is lost. This is called a pebbling step. The basic question in graph pebbling asks if one may from a givendistribution of pebbles on a set of vertices move to another distributionon the same set via a series of pebbling steps. In this Master’s thesis we approach the above question using twomodels: a deterministic, which includes the notion of a pebblingnumber, and a probabilistic, which includes the notion of a threshold. For both these models we clarify earlier proofs, and provide newproofs, of foundational theorems in graph pebbling. These resultsconstitute the backbone for our discussion on recent research, whichconcentrates on generalizing and extending central notions in graphpebbling, for example the generalized idea of a pebbling number:the pi-pebbling function. Simultaneously, a corollary to the so calledcover pebbling theorem is derived. This corollary lets us prove established,and newly found, theorems. Regarding applications in graph pebbling, we argue that one shouldgeneralize existing results, and incorporate directed graphs into abigger part of the theory. We suggest how this can be done.Min handledare, Cecilia Holmgren, var tidigare anställd vid Matematiska institutionen, Stockholms universitet, men arbetar numera vid Matematiska institutionen, Uppsala universitet.