The cover pebbling theorem

MaRDI QIDQ2583674zbMATH OpenFDO

Authors Jonas Sjöstrand

Publication date 17 January 2006

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/math/0410129, https://eudml.org/doc/125580, http://www.emis.de/journals/EJC/Volume_12/Abstracts/v12i1n22.html

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

Pebbling coverWeighted pebbling cover

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Games involving graphs (91A43)

Abstract: For any configuration of pebbles on the nodes of a graph, a pebbling move replaces two pebbles on one node by one pebble on an adjacent node. A cover pebbling is a move sequence ending with no empty nodes. The number of pebbles needed for a cover pebbling starting with all pebbles on one node is trivial to compute and it was conjectured that the maximum of these simple cover pebbling numbers is indeed the general cover pebbling number of the graph. That is, for any configuration of this size, there exists a cover pebbling. In this note, we prove a generalization of the conjecture. All previously published results about cover pebbling numbers for special graphs (trees, hypercubes etcetera) are direct consequences of this theorem. We also prove that the cover pebbling number of a product of two graphs equals the product of the cover pebbling numbers of the graphs.

Review text

This very clearly written short paper gives a proof of the weighted pebbling cover problem: every vertex in the (directed or undirected) graph \(G\) is assigned a natural number \(w(v).\) At the beginning every vertex is populated a certain (probably different) number of pebbles. In every step at one vertex two pebbles are deleted and a new one is born at a neighbour. The general pebbling cover problem is: what is the minimum number of pebbles that for any distribution of them over the vertices one can find an algorithm to end up a configuration, where every vertex \(v\) contains at least \(w(v)\) pebbles. The original pebbling problem is the choice \(w(v)=1\) for all vertices. The problem has a fair size of literature: several papers determined the pebbling cover numbers of special graph classes. \textit{B. Crull} et al. [Discrete Math. 296, 15--23 (2005; Zbl 1066.05140)] conjectured that it is enough to solve the problem for cases where at the beginning all pebbles occupy the same vertex. This paper answers the conjecture affirmatively: giving new, short proofs for every previously known case.

Recommendations

• The cover pebbling number of graphs
• Cover pebbling numbers and bounds for certain families of graphs
• Weighted pebbling numbers on graphs
• Cover rubbling and stacking
• Generalizations of Graham's pebbling conjecture
• Domination cover pebbling: graph families
• A Graph Pebbling Algorithm on Weighted Graphs
• Threshold and complexity results for the cover pebbling game
• Cover pebbling hypercubes
• Cover pebbling number for square of a path

Cited in

(13)

• Threshold and complexity results for the cover pebbling game
• Rubbling and optimal rubbling of graphs
• Domination cover rubbling
• Cover rubbling and stacking
• The cover pebbling number of graphs
• Pebbling in powers of paths
• The PSPACE-Completeness of Black-White Pebbling
• General graph pebbling
• Generalizations of Graham's pebbling conjecture
• Cover pebbling hypercubes
• Pebble minimization: the last theorems
• On the target pebbling conjecture
• Target pebbling in trees

This page was built for publication: The cover pebbling theorem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2583674)