Optimally \(t\)-pebbling graphs (Q2811833)

A distribution of pebbles of a graph \(G\) is a function \(\delta: V(G)\rightarrow N\cup \{0\}\). In a graph with a distribution of pebbles, a pebbling move consists of removing two pebbles from one vertex and then placing one pebble an an adjacent vertex. A pebbling type \(\alpha\) of \(G\) is a mapping from \(V(G)\) to \(N\cup \{0\}\). A distribution \(\delta\) of pebbles of \(G\) is said to be an \(\alpha\)-pebbling distribution if whenever we choose a target vertex \(v\) in \(G\), we can move \(\alpha(v)\) pebbles to \(v\) by applying pebbling moves successively (if necessary). For any positive integer \(t\), a \(t\)-pebbling distribution of \(G\) is an \(\alpha\)-pebbling distribution of \(G\) where \(\alpha(v)=t\) for each \(v\in V(G)\). The optimal \(\alpha\)-pebbling number \(\pi^\ast(G)\) of \(G\) is the minimum number of pebbles required in an \(\alpha\)-pebbling distribution of \(G\). In the case where \(\alpha(v)=t\), for each \(v\in V(G)\), \(\pi_t(G)\) for \(\pi_{\alpha}(G)\) and say the optimal \(\alpha\)-pebbling number to be the optimal \(t\)-pebbling number. In this paper, the authors determine the optimal \(t\)-pebbling numbers for paths and complete graphs for each integer \(t\geq 2\). Subsequently, by using the idea of \(t\)-pebbling distribution, they show that \(\pi^*(G\square H)\leq \pi^*(G)\pi^\ast(H)\) for any two graphs \(G\) and \(H\) where \(G\square H\) is the Cartesian product of \(G\) and \(H\). Consequently, they prove that \(\pi^\ast (Q_n)\leq 3.27(1.3763356)^n\) where \(Q_n\) is the \(n\)-cube. This upper bound is better than that of Moews for \(n\leq 354\).