Article ID Journal Published Year Pages File Type
4650989 Discrete Mathematics 2007 7 Pages PDF
Abstract

Consider a distribution of pebbles on the vertices of a graph GG. 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 GG, denoted fopt(G)fopt(G), is the least number of pebbles, such that for some distribution of fopt(G)fopt(G) pebbles, a pebble can be moved to any vertex of GG.We give sharp lower and upper bounds for fopt(G)fopt(G) for GG of diameter dd. For graphs of diameter two (respectively, three) we characterize the classes of graphs having fopt(G)fopt(G) equal to a value between 2 and 4 (respectively, between 3 and 8).

Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Authors
, , , ,