Optimal pebbling number of graphs with given minimum degree

A. Czygrinow, G. Hurlbert, G. Y. Katona, L. F. Papp

Research output: Contribution to journalArticlepeer-review


Consider a distribution of pebbles on a connected graph G. A pebbling move removes two pebbles from a vertex and places one to an adjacent vertex. A vertex is reachable under a pebbling distribution if it has a pebble after the application of a sequence of pebbling moves. The optimal pebbling number π (G) is the smallest number of pebbles that we can distribute in such a way that each vertex is reachable. It was known that the optimal pebbling number of any connected graph is at most [Formula presented], where δ is the minimum degree of the graph. We strengthen this bound by showing that equality cannot be attained and that the bound is sharp. If diam(G)≥3 then we further improve the bound to π (G)≤[Formula presented]. On the other hand, we show that, for arbitrary large diameter and any ϵ>0, there are infinitely many graphs whose optimal pebbling number is bigger than [Formula presented]−ϵ[Formula presented].

Original languageEnglish (US)
Pages (from-to)117-130
Number of pages14
JournalDiscrete Applied Mathematics
StatePublished - May 15 2019


  • Given minimum degree
  • Graph pebbling
  • Optimal pebbling

ASJC Scopus subject areas

  • Discrete Mathematics and Combinatorics
  • Applied Mathematics


Dive into the research topics of 'Optimal pebbling number of graphs with given minimum degree'. Together they form a unique fingerprint.

Cite this