Computer Sciences Commons^™

Graph Pebbling: Doppelgangers And Lemke Graphs, Mark Powers

17th Annual Celebration of Undergraduate Research and Creative Performance (2018)

Graph pebbling is a mathematical game played on a connected graph. A configuration places a nonnegative number of pebbles on each vertex. A move between a pair of adjacent vertices removes two pebbles from one vertex and places one pebble on the other. A configuration is solvable if a sequence of pebbling moves can be made to place a pebble on any given vertex. The pebbling number of a graph is the minimum number of pebbles so that any configuration is solvable. A graph satisfies the two-pebbling property if any configuration of more than twice the pebbling number minus the …