Thresholds for random distributions on graph sequences with applications to pebbling

DOI10.1016/S0012-365X(02)00445-4MaRDI QIDQ1861202zbMATH OpenFDO

Authors Jeffrey Boyle

Publication date 16 March 2003

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/S0012-365X(02)00445-4

Mathematics Subject Classification ID

Graph theory (05C99) Combinatorial probability (60C05)

Review text

Let \(G= (G_1,\dots, G_n)\) be a sequence of graphs with \(G_n\) having \(n\) vertices with a random distribution of \(t(n)\) pebbles to its vertices. A function \(f\) is called threshold for \(G\) if \(\lim_{n\to\infty} P_G(n,t)= 1\) (with \(P_G(n,t)\) the proportion of all distributions of \(t\) pebbles onto \(G_n\) that are solvable) for \(\lim_{n\to\infty} {f(n)\over t(n)}= 0\), and \(\lim_{n\to\infty} P_G(n,t)= 0\) for \(\lim_{n\to\infty} {t(n)\over f(n)}= 0\). For a survey of definitions and known results see, i.e., \textit{A. Czygrinow}, \textit{N. Eaton}, \textit{G. Hurlbert} and \textit{P. M. Kayll} [Discrete Math. 247, 93-105 (2002; Zbl 1002.05037)]. Here the author proves that for all \(n\) and some \(p\in (0,1]\), if for some \(d\) with \(\text{diameter}(G_n)\leq d\) the maximum degree of \(G_n\subseteq \Omega(n^p)\), then the threshold of \(G\) for the solvability of \(G\) is in \(O(n^{1-0.5p})\).

Recommendations

• On pebbling threshold functions for graph sequences
• On the pebbling threshold of paths and the pebbling threshold spectrum
• Thresholds for families of multisets, with an application to graph pebbling
• scientific article; zbMATH DE number 1439473
• Counterexamples to a monotonicity conjecture for the threshold pebbling number

Cited in

(8)

• Thresholds for families of multisets, with an application to graph pebbling
• An improved upper bound for the pebbling threshold of the n-path
• On pebbling threshold functions for graph sequences
• General graph pebbling
• Counterexamples to a monotonicity conjecture for the threshold pebbling number
• scientific article; zbMATH DE number 7650133 (Why is no real title available?)
• On the pebbling threshold of paths and the pebbling threshold spectrum
• The pebbling threshold of the square of cliques

This page was built for publication: Thresholds for random distributions on graph sequences with applications to pebbling

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1861202)