An Introduction to Graph Pebbling

Graph pebbling is a mathematical game played over a fixed graph. It was invented in 1989 by Lagarias and Saks and used that same year by Chung as an alternate proof to a technical problem in additive number theory. Pebbles represent a discretely measured consumable resource and are nonnegative integer weights on the vertices of a graph. A pebbling distribution assigns pebbles to the vertices of a graph. A pebbling move removes two pebbles from one vertex and places one pebble on an adjacent vertex, thus a single pebble is lost with every pebbling move. A vertex is reachable under a distribution if it may receive a pebble at any time. A pebbling distribution is solvable if every vertex is reachable. In this thesis, we give first give a broad overview of the field of graph pebbling. We then discuss our work in the field and give a new complexity result. We conclude with a discussion of open problems related to our research and present avenues for future work.
Download pdf
Abstract/Description: Graph pebbling is a mathematical game played over a fixed graph. It was invented in 1989 by Lagarias and Saks and used that same year by Chung as an alternate proof to a technical problem in additive number theory. Pebbles represent a discretely measured consumable resource and are nonnegative integer weights on the vertices of a graph. A pebbling distribution assigns pebbles to the vertices of a graph. A pebbling move removes two pebbles from one vertex and places one pebble on an adjacent vertex, thus a single pebble is lost with every pebbling move. A vertex is reachable under a distribution if it may receive a pebble at any time. A pebbling distribution is solvable if every vertex is reachable. In this thesis, we give first give a broad overview of the field of graph pebbling. We then discuss our work in the field and give a new complexity result. We conclude with a discussion of open problems related to our research and present avenues for future work.
Subject(s): Graph theory
Date Issued: May 2014