On the pebbling threshold of paths and the pebbling threshold spectrum

DOI10.1016/J.DISC.2007.06.045MaRDI QIDQ932604zbMATH OpenOpenAlexFDO

Authors Andrzej Czygrinow, Glenn H. Hurlbert

Publication date 11 July 2008

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/math/0406124

zbMATH Keywords

pathspebblingspectrumthreshold

Mathematics Subject Classification ID

Combinatorial inequalities (05A20) Extremal problems in graph theory (05C35) Extremal set theory (05D05)

Abstract: A configuration of pebbles on the vertices of a graph is solvable if one can place a pebble on any given root vertex via a sequence of pebbling steps. A function is a pebbling threshold 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. In this note we show that the spectrum of pebbling thresholds for graph sequences spans the entire range from n^{1/2} to n. This answers a question of Czygrinow, Eaton, Hurlbert and Kayll. What the spectrum looks like above n remains unknown.

Recommendations

• An improved upper bound for the pebbling threshold of the n-path
• On pebbling threshold functions for graph sequences
• Thresholds for families of multisets, with an application to graph pebbling
• scientific article; zbMATH DE number 1439473
• Thresholds for random distributions on graph sequences with applications to pebbling

Cites work

• An improved upper bound for the pebbling threshold of the n-path
• scientific article; zbMATH DE number 3809592 (Why is no real title available?)
• scientific article; zbMATH DE number 1439473 (Why is no real title available?)
• On pebbling threshold functions for graph sequences
• Thresholds for families of multisets, with an application to graph pebbling

Cited in

(13)

• Threshold and complexity results for the cover pebbling game
• 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
• Thresholds for random distributions on graph sequences with applications to pebbling
• The weight function lemma for graph pebbling
• Cover Pebbling Thresholds for the Complete Graph
• General graph pebbling
• Counterexamples to a monotonicity conjecture for the threshold pebbling number
• Girth, Pebbling, and Grid Thresholds
• Thresholds for zero-sums with small cross numbers in abelian groups
• Thresholds for pebbling on grids
• The pebbling threshold of the square of cliques

This page was built for publication: On the pebbling threshold of paths and the pebbling threshold spectrum

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