First, let me explain a little bit about what graph pebbling is. In short, it's a game played on a graph. By graph, I mean any object with some number vertices and some number of edges connecting those vertices, but in this context, a graph is assumed to be connected (i.e., you can get to any vertex you want by moving along edges, regardless of the vertex you start at).
Now for the pebbles.
In order to play the game, take a bunch of pebbles (make sure you count them) and distribute them among the vertices of the graph. When you are satisfied with the distribution of pebbles, the game begins. At this point, you may only add or remove pebbles from vertices via what we call a pebbling move. A pebbling move may be executed in the following way:
- If you have at least two pebbles on some vertex, you may execute a pebbling move on that vertex.
- Take exactly two pebbles from that vertex.
- Remove the first from play, and move the other away from that vertex along a single edge to be placed on another vertex.
However, the game isn't like most others in that there isn't exactly an established win condition, per se. Instead, the study of the game typically focuses on what can be done — or what cannot. In many cases, certain objectives within the game are set, and it is asked how certain conditions regarding the original distribution of pebbles affect whether or not the objective can be achieved within the span of the game.
In particular, my research is mainly concerned with relating one fundamental property of graphs and one fundamental property of the game, known as minimum degree and the optimal pebbling number respectively. To understand the minimum degree, we have to talk about the degree of a single vertex, which is the number of edges incident to that vertex. The minimum degree of the graph is the least degree of its vertices.
Meanwhile, the optimal pebbling number of a graph is the fewest number of pebbles needed to ensure that there is some way to distribute those pebbles among the vertices so that any vertex can be occupied by a pebble in the course of the game. To elaborate a little, that doesn't mean every vertex can be occupied in the course of a single game, but that, at the start of a game, you could decide on any one currently unoccupied vertex and subsequently place a pebble on that vertex by using pebbling moves. Exploring this relationship further won't just help us understand more about how to play the game, but also to understand the ways in which complicated systems and networks function.
As the start of my project approaches, I am looking forward to begin more focused research under the guidance of a professor, and to be able to delve further into this topic. For more information on my project, please visit the link below to my official research project proposal:
Research Proposal