Project Description: |
This summer we plan to investigate graph pebbling problem. It is relatively new area of combinatorics that studies a game on a connected graph. Suppose that pebbles are configured on vertices of a connected graph G. A pebbling step consists of removing two pebbles from a vertex v and placing one pebble on a neighbor of v. A configuration is called solvable if r-solvable if it is possible to move at least one pebble to vertex r by a sequence of pebbling steps. A configuration is called solvable if it r-solvable for any vertex of G. The smallest integer number t such that any configuration of t pebbles is solvable is called the pebbling number of G. For example, for a complete graph on n vertices pebbling number is n.
More information on pebbling problem can be found
at math.hope.edu/bekmetjev/pebbling.
We will look at open questions and new ideas in this area such as critical pebbling, cover pebbling and optimal pebbling as well as algorithmic aspects of the problem. One of our goals will be finding pebbling solutions for various types of graphs using some specific graph properties, heuristics and random algorithms. We will also consider probabilistic models in pebbling.
Background: Students should have a background in combinatorics and/or graph theory. Some knowledge in programming, probability theory/statistics, familiarity with computer algebra systems (such as MAPLE) is a plus. |
