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

Direct link
Counterexamples to a monotonicity conjecture for the threshold pebbling number
Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Mathematics, Algebra, Geometry and Logic.
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 nu, there is some list of pebbling moves that ends with nu 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 oft 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.
Keyword [en]
Graph theory, Graph pebbling, Pebbling number, Pebbling threshold
National Category
URN: urn:nbn:se:uu:diva-177840DOI: 10.1016/j.disc.2012.04.005ISI: 000305724900025OAI: oai:DiVA.org:uu-177840DiVA: diva2:541615
Available from: 2012-07-20 Created: 2012-07-19 Last updated: 2012-07-20Bibliographically approved

Open Access in DiVA

No full text

Other links

Publisher's full text
By organisation
Algebra, Geometry and Logic
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

Altmetric score

Total: 237 hits
ReferencesLink to record
Permanent link

Direct link