Optimal Pebbling on Grids

Carl Yerger
Davidson College

Chenxiao Xue
Davidson College

PDF

Minisymposium: GRAPH PRODUCTS

Content: Given a distribution of pebbles on the vertices of a connected graph $G$, a \textit{pebbling move} is defined as the removal of two pebbles from some vertex and the placement of one of these on an adjacent vertex. The \textit{pebbling number} of a graph $G$ is the smallest integer $k$ such that for each vertex $v$ and each distribution of $k$ pebbles on $G$ there is a sequence of pebbling moves that places at least one pebble on $v$. We say such a distribution is \textit{solvable}. The \textit{optimal pebbling number} of $G$, denoted $\Pi_{OPT}(G)$, is the least $k$ such that some particular distribution of $k$ pebbles is solvable. In this talk, we describe a strengthening of a result of Bunde et al relating to the optimal pebbling number of the 2 by $n$ square grid by describing all possible optimal configurations. We find the optimal pebbling number for the 3 by $n$ square grid and related structures. Finally, we describe a bound for the analogue of this question for the infinite square grid and suggest related open questions.

Back to all abstracts