What is Graph pebbling?
Graph pebbling is a combinatorial game played on a directed acyclic graph, where the goal is to pub a pebble on the sink of the graph.
What makes this task non-trivial is that you are only allowed to put a pebble on a node if all its parent nodes are pebbled. We consider the classical “black pebbling” game where you can remove pebbles at any time, and the goal is to pebble the sink using as few pebbles as possible.
TODO: (could put picture with a legal and non legal pebbling here)
The path shown below can be pebbled with only 2 pebbles, press the Pebble button below to see how this is done.
Competition: construct a graph with high pebbling complexity?
At the open campus day we have a competition where you can construct and submit a graph. The graph which is hardest to pebble wins! We will announce the winners when and where
With being hardest to pebble we mean the graph requires the highest number of pebbles. If two graphs need the same number of pebbles, the graph which needs more pebbling steps is considered the winner.
You can construct a graph by adding edges to the path graph below, click on a node to see which edges containing this node can be added or removed. The only constraint is that the indegree of any node in the graph can be at most two. Click the Pebble button to see how many pebbles and steps your graphs needs, and click submit to submit your answer.