Optimal pebbling of graphs

Jessica Muntz, Sivaram Narayan, Noah Streib, Kelly Van Ochten

Research output: Contribution to journalArticlepeer-review

6 Scopus citations

Abstract

Consider a distribution of pebbles on the vertices of a graph G. A pebbling move consists of the removal of two pebbles from a vertex and then placing one pebble at an adjacent vertex. The optimal pebbling number of G, denoted fopt (G), is the least number of pebbles, such that for some distribution of fopt (G) pebbles, a pebble can be moved to any vertex of G. We give sharp lower and upper bounds for fopt (G) for G of diameter d. For graphs of diameter two (respectively, three) we characterize the classes of graphs having fopt (G) equal to a value between 2 and 4 (respectively, between 3 and 8).

Original languageEnglish
Pages (from-to)2315-2321
Number of pages7
JournalDiscrete Mathematics
Volume307
Issue number17-18
DOIs
StatePublished - Aug 6 2007

Keywords

  • Bounds
  • Diameter
  • Optimal pebbling number
  • Simple graph

Fingerprint

Dive into the research topics of 'Optimal pebbling of graphs'. Together they form a unique fingerprint.

Cite this