Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
The cover pebbling theorem
KTH, School of Engineering Sciences (SCI), Mathematics (Dept.).
2005 (English)In: The Electronic Journal of Combinatorics, ISSN 1097-1440, E-ISSN 1077-8926, Vol. 12, no 1, N22- p.Article in journal (Refereed) Published
Abstract [en]

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 et cetera) 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.

Place, publisher, year, edition, pages
2005. Vol. 12, no 1, N22- p.
National Category
Mathematics
Identifiers
URN: urn:nbn:se:kth:diva-38466ISI: 000233258300001Scopus ID: 2-s2.0-27844605078OAI: oai:DiVA.org:kth-38466DiVA: diva2:437452
Note
QC 20110829Available from: 2011-08-29 Created: 2011-08-26 Last updated: 2017-12-08Bibliographically approved

Open Access in DiVA

No full text

Other links

ScopusThe Electronic Journal of Combinatorics

Search in DiVA

By author/editor
Sjöstrand, Jonas
By organisation
Mathematics (Dept.)
In the same journal
The Electronic Journal of Combinatorics
Mathematics

Search outside of DiVA

GoogleGoogle Scholar

urn-nbn

Altmetric score

urn-nbn
Total: 23 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf