Return to search

An Improved Upper Bound for the Pebbling Threshold of the n-path

Given a configuration of t indistinguishable pebbles on the n vertices of a graph G, we say that a vertex v can be reached if a pebble can be placed on it in a finite number of "moves". G is said to be pebbleable if all its vertices can be thus reached. Now given the n-path Pn how large (resp. small) must t be so as to be able to pebble the path almost surely (resp. almost never)? It was known that the threshold th(Pn) for pebbling the path satisfies n2clgn≤th(Pn)≤n22lgn, where lg=log2 and c<1/2 is arbitrary. We improve the upper bound for the threshold function to th(Pn)≤n2dlgn, where d>1 is arbitrary.

Identiferoai:union.ndltd.org:ETSU/oai:dc.etsu.edu:etsu-works-19990
Date28 January 2004
CreatorsWierman, Adam, Salzman, Julia, Jablonski, Michael, Godbole, Anant P.
PublisherDigital Commons @ East Tennessee State University
Source SetsEast Tennessee State University
Detected LanguageEnglish
Typetext
SourceETSU Faculty Works

Page generated in 0.0019 seconds