On the Pebbling Threshold Spectrum

Thumbnail Image

Date

Authors

Journal Title

Journal ISSN

Volume Title

Publisher

Abstract

Description

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.
8 pages, preliminary version

Keywords

Combinatorics, 05D05, 05C35, 05A20

Citation

URI

http://salesiana.dossiersoluciones.com/handle/123456789/71467

Consulte el texto completo en el siguiente enlace:

https://arxiv.org/abs/math/0406124
 http://arxiv.org/abs/math/0406124

Collections

arXiv