scientific article; zbMATH DE number 1998296
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)\).
- Thresholds for families of multisets, with an application to graph pebbling
- On pebbling threshold functions for graph sequences
- The 2-pebbling property for dense graphs
- General graph pebbling
- Pebbling dynamic graphs in minimal space
- scientific article; zbMATH DE number 1775412 (Why is no real title available?)
- Target pebbling in trees
- Rubbling and optimal rubbling of dense bipartite graphs
This page was built for publication:
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4432941)
