No label defined (Q4432941)

The pebbling number of a graph \(G\) is the minimum number \(\pi(G)\) such that every configuration of \(\pi(G)\) pebbles on the vertices of \(G\) is solvable. A graph is class \(0\) if its pebbling number equals its number of vertices [see i.e. \textit{T. A. Clarke}, \textit{R. A. Hochberg} and \textit{G. H. Hurlbert}, J. Graph Theory 25, 119--128 (1997; Zbl 0881.05109)]. The authors prove that graphs on \(n\geq 9\) vertices having minimum degree at least \(\lfloor n/2\rfloor\) are class \(0\), as are bipartite graphs with \(m\geq 336\) vertices in each part having minimum degree at least \(\lfloor m/2\rfloor+ 1\). Both results are best possible. The pebbling threshold is a function for a sequence of graphs if a randomly chosen configuration of asymptotically more pebbles is almost surely solvable, while one of asymptotically fewer pebbles is almost surely not [see i.e. \textit{A. Czygrinow}, \textit{V. Eaton}, \textit{G. Hurlbert} and \textit{P. M. Kayll}, Discrete Math. 247, 93--105 (2002; Zbl 1002.05037)]. The authors of the present paper prove that the pebbling threshold of graphs with minimum degree \(\delta\), with \(\sqrt{n}\ll\delta\), is \(O(n^{3/2}/\delta)\).