Pebbling Algorithms in Diameter Two Graphs
Airat Bekmetjev, Charles A. Cusack · SIAM Journal on Discrete Mathematics · 2009
Consider a connected graph and a configuration of pebbles on its vertices. A pebbling step consists of removing two pebbles from a vertex and placing one on an adjacent vertex. A configuration is called solvable if it is possible to place a pebble on any given vertex through a sequence of pebbling steps. A smallest number t such that any configuration with t pebbles is solvable is called the pebbling number of the graph. In this paper, we consider algorithms determining the solvability of a pebbling configuration on graphs of diameter two. We prove that if k is the vertex connectivity of a diameter two graph G, then a configuration is solvable if there are at least $c(k)=\min\{k+4,3k-1\}$ vertices in G with two or more pebbles. We use this result to construct an algorithm that has complexity $O(c(k)!\cdot n^{2c(k)-3}m)$, where n is the number of vertices and m is the number of edges. We also present an algorithm for diameter two graphs with pebbling number $n+1$, known as Class 1 graphs, which takes $O(nm)$ time.