Home | Issues | About JGAA | Instructions for Authors |
DOI: 10.7155/jgaa.00205
A Graph Pebbling Algorithm on Weighted Graphs
Vol. 14, no. 2, pp. 221-244, 2010. Regular paper.
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.
|
Submitted: April 2009.
Reviewed: August 2009.
Revised: December 2009.
Accepted: January 2010.
Final: January 2010.
Published: February 2010.
Communicated by
Giuseppe Liotta
|
Journal Supporters
|