uu.seUppsala University Publications
Change search
ReferencesLink to record
Permanent link

Direct link
Counterexamples to a monotonicity conjecture for the threshold pebbling number
University of Cambridge.
2012 (English)In: Discrete Mathematics, ISSN 0012-365X, E-ISSN 1872-681X, Vol. 312, no 15, 2401-2405 p.Article in journal (Refereed) Published
Abstract [en]

Graph pebbling considers the problem of transforming configurations of discrete pebbles to certain target configurations on the vertices of a graph, using the so-called pebbling move, in which two pebbles are removed from a vertex and one is placed on a neighbouring vertex. Given a graph G, the pebbling number pi (G) is the least t such that every initial distribution of t pebbles at the vertices of G is solvable, that is for every target vertex v, there is some list of pebbling moves that ends with v having a pebble. Given a graph sequence (G(n)), the pebbling threshold tau (G(n)) is a sequence (a(n)) such that t = a(n) is the smallest number of pebbles such that a random configuration of t pebbles on the vertices of G(n) is solvable with probability at least 1/2, in the probabilistic model where each configuration of t pebbles on the vertices of G(n) is selected uniformly at random. This paper provides counterexamples to the following monotonicity conjecture stated by Hurlbert et al.: If (G(n)) and (H(n)) are graph sequences such that pi(G(n)) <= pi(H(n)), then it holds that tau(G(n)) is an element of O(tau(H(n)).

Place, publisher, year, edition, pages
2012. Vol. 312, no 15, 2401-2405 p.
National Category
Research subject
URN: urn:nbn:se:uu:diva-260489OAI: oai:DiVA.org:uu-260489DiVA: diva2:847302
Swedish Research Council
Available from: 2015-08-19 Created: 2015-08-19 Last updated: 2015-08-19

Open Access in DiVA

No full text

Search in DiVA

By author/editor
Holmgren, Cecilia
In the same journal
Discrete Mathematics

Search outside of DiVA

GoogleGoogle Scholar
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Total: 178 hits
ReferencesLink to record
Permanent link

Direct link