A Graph Pebbling Algorithm on Weighted Graphs

DOI10.7155/JGAA.00205MaRDI QIDQ3075605zbMATH OpenOpenAlexFDO

Authors Nándor Sieben

Publication date 16 February 2011

Published in Journal of Graph Algorithms and Applications (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

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

Mathematics Subject Classification ID

Connectivity (05C40) Graph algorithms (graph-theoretic aspects) (05C85)

Abstract: A pebbling move on a weighted graph removes some pebbles at a vertex and adds one pebble at an adjacent vertex. The number of pebbles removed is the weight of the edge connecting the vertices. A vertex is reachable from a pebble distribution if it is possible to move a pebble to that vertex using pebbling moves. The pebbling number of a weighted graph is the smallest number $m$ needed to guarantee that any vertex is reachable from any pebble distribution of $m$ pebbles. Regular pebbling problems on unweighted graphs are special cases when the weight on every edge is 2. A regular pebbling problem often simplifies to a pebbling problem on a simpler weighted graph. We present an algorithm to find the pebbling number of weighted graphs. We use this algorithm together with graph simplifications to find the regular pebbling number of all connected graphs with at most nine vertices.

Recommendations

• Weighted pebbling numbers on graphs
• The weight function lemma for graph pebbling
• Graph pebbling algorithms and Lemke graphs
• A note on graph pebbling
• scientific article; zbMATH DE number 1439473
• Pebbling and optimal pebbling in graphs
• The Complexity of Graph Pebbling
• Optimal pebbling of graphs
• Pebbling Algorithms in Diameter Two Graphs
• Graph pebbling: a blend of graph theory, number theory, and optimization

Cited in

(11)

• On the pebbling number of \(\mathcal{C}_m \times \mathcal{C}_n\) in case of even parity
• On properties of pebble assignment graphs
• Bounds on the rubbling and optimal rubbling numbers of graphs
• The weight function lemma for graph pebbling
• Graph pebbling algorithms and Lemke graphs
• The complexity of pebbling reachability and solvability in planar and outerplanar graphs
• The cover pebbling theorem
• Cycles and girth in pebble assignment graphs
• Bounds on the rubbling and optimal rubbling numbers of graphs
• Weighted pebbling numbers on graphs
• Automating weight function generation in graph pebbling

This page was built for publication: A Graph Pebbling Algorithm on Weighted Graphs

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