Improved pebbling bounds

DOI10.1016/J.DISC.2006.06.032MaRDI QIDQ2483419zbMATH OpenOpenAlexFDO

Authors Melody Chan, Anant P. Godbole

Publication date 28 April 2008

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/math/0510045

zbMATH Keywords

dominating setefficient dominating setgraph pebblingpebbling number

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph theory (05C99)

Abstract: Consider a configuration of pebbles distributed on the vertices of a connected graph of order $n$. A pebbling step consists of removing two pebbles from a given vertex and placing one pebble on an adjacent vertex. A distribution of pebbles on a graph is called solvable if it is possible to place a pebble on any given vertex using a sequence of pebbling steps. The pebbling number of a graph, denoted $f(G)$, is the minimal number of pebbles such that every configuration of $f(G)$ pebbles on $G$ is solvable. We derive several general upper bounds on the pebbling number, improving previous results.

Recommendations

• Bounds for the pebbling number of product graphs
• scientific article; zbMATH DE number 1145909
• Optimal pebbling of graphs
• Maximum pebbling number of graphs of diameter three
• Pebbling graphs of diameter three and four

Cites work

• scientific article; zbMATH DE number 1095171 (Why is no real title available?)
• scientific article; zbMATH DE number 1145909 (Why is no real title available?)
• scientific article; zbMATH DE number 1439473 (Why is no real title available?)
• Maximum pebbling number of graphs of diameter three
• Pebbling graphs
• Pebbling in Hypercubes

Cited in

(13)

• Threshold and complexity results for the cover pebbling game
• Thresholds for families of multisets, with an application to graph pebbling
• Bounds on the rubbling and optimal rubbling numbers of graphs
• Modified linear programming and class 0 bounds for graph pebbling
• Bounds on the rubbling and optimal rubbling numbers of graphs
• On the Relative Strength of Pebbling and Resolution
• General graph pebbling
• Bounds for the pebbling number of product graphs
• Pebbling in semi-2-trees
• Pebbling graphs of fixed diameter
• Pebbling in Kneser graphs
• On the pebbling numbers of flower, Blanuša and Watkins snarks
• Target pebbling in trees

This page was built for publication: Improved pebbling bounds

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