An Introduction to Graph Pebbling
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 
Title:  An Introduction to Graph Pebbling.  

Name(s): 
Mohorn, Matthew, creator Yerger, Carl, Thesis advisor Peachey, James, Thesis reader Davidson College. Mathematics Department 

Type of Resource:  text  
Genre:  Thesis  
Copyright Date:  May 2014  
Date Created:  May 2014  
Date Issued:  May 2014  
Other Date:  May 2014  
Publisher:  Davidson College  
Extent:  74 pages  
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  
Restrictions on Access:  Copyright held by author.  
In Collections: 