Abstract | ||
---|---|---|
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 c1 is arbitrary. |
Year | DOI | Venue |
---|---|---|
2004 | 10.1016/j.disc.2002.10.001 | Discrete Mathematics |
Keywords | Field | DocType |
n-cycle,n-path,pebbling number,pebbling threshold,satisfiability,upper bound | Graph theory,Graph,Discrete mathematics,Combinatorics,Finite set,Vertex (geometry),Upper and lower bounds,Almost surely,Pebble,Mathematics,Threshold function | Journal |
Volume | Issue | ISSN |
275 | 1 | Discrete Mathematics |
Citations | PageRank | References |
5 | 0.55 | 3 |
Authors | ||
4 |
Name | Order | Citations | PageRank |
---|---|---|---|
Adam Wierman | 1 | 1635 | 106.57 |
Julia Salzman | 2 | 26 | 3.06 |
Michael Jablonski | 3 | 5 | 0.55 |
Anant P. Godbole | 4 | 95 | 16.08 |