Physical Sciences and Mathematics Commons^™

The Complexity Of Pebbling In Diameter Two Graphs*, Charles A. Cusack, Timothy Lewis, Daniel Simpson, Samuel Taggart

Faculty Publications

Given a simple, connected graph, a pebbling configuration is a function from its vertex set to the nonnegative integers. A pebbling move between adjacent vertices removes two pebbles from one vertex and adds one pebble to the other. A vertex r is said to be reachable from a configuration if there exists a sequence of pebbling moves that places one pebble on r. A configuration is solvable if every vertex is reachable. We prove tight bounds on the number of vertices with two and three pebbles that an unsolvable configuration on a diameter two graph can have in terms of …