The optimal pebbling number of the complete \(m\)-ary tree (Q1579551)

A distribution \(\delta\) of pebbles onto the vertices of a graph \(G\) is called a configuration of \(G\) where \(\delta_G\) denotes the number of pebbles of \(\delta\). A pebbling move consists of removing two pebbles from a vertex and placing one pebble on an adjacent vertex. If, for any vertex \(v\) of \(G\), there exists a sequence of pebbling moves, starting from the configuration \(\delta\), which allows us to place at least one pebble on \(v\), then \(\delta\) is called a pebbling of \(G\). The optimal pebbling number \(f'(G)\) of \(G\) is given by \(f'(G)= \min\{\delta_G\mid\delta\) is a pebbling of \(G\}\). The optimal pebbling number of a path was determined by \textit{L. Pachter}, \textit{H. S. Snevily} and \textit{B. Voxman} [Congr. Numerantium 107, 65-80 (1995; Zbl 0895.05063)]. Let \(T^m_h\) denote the complete \(m\)-ary tree of height \(h\). In this paper, the authors show that \(f'(T^m_h)= 2^h\) for \(m\geq 3\) and that \[ f'(T^2_h)= \min \sum^h_{i=0} 2^i x_i\quad\text{subject to}\quad \sum^h_{i=0} \Biggl(2^i-{1\over 3}\Biggr) x_i\geq {2^{h+1}\over 3}, \] where \(x_0\in \{0,1,2,3\}\) and \(x_i\in \{0,2\}\) for \(1\leq i\leq h\). An efficient algorithm solving this last integer linear programming problem is also given.