Pebbling and Optimal Pebbling in Graphs

Details Pebbling and Optimal Pebbling in Graphs Pebbling and Optimal Pebbling in Graphs

2005-10-28

arxiv.org/abs/math/0510621v1

Journal of Graph Theory. Vol. 57, March 2008, pp. 215-238

Mathematics

Combinatorics

26 pages

Scientific paper

Given a distribution of pebbles on the vertices of a graph G, a {\it pebbling move} takes two pebbles from one vertex and puts one on a neighboring vertex. The {\it pebbling number} \Pi(G) is the minimum k such that for every distribution of k pebbles and every vertex r, it is possible to move a pebble to r. The {\it optimal pebbling number} \Pi_{OPT}(G) is the minimum k such that some distribution of k pebbles permits reaching each vertex. We give short proofs of prior results on these parameters for paths, cycles, trees, and hypercubes, a new linear-time algorithm for computing \Pi(G) on trees, and new results on \Pi_{OPT}(G). If G is a connected n-vertex graph, then \Pi_{OPT}(G)\le\ceiling{2n/3}, with equality for paths and cycles. If \bf{G} is the family of n-vertex connected graphs with minimum degree k, then 2.4\le \max_{G\in \bf{G}} \Pi_{OPT}(G) \frac{k+1}{n}\le 4 when k>15 and k is a multiple of 3. Finally, \Pi_{OPT}(G)\le 4^tn/((k-1)^t+4^t) when G is a connected n-vertex graph with minimum degree k and girth at least 2t+1. For t=2, a more precise version of this last bound is \Pi_{OPT}(G)\le 16n/(k^2+17).

Affiliated with

Also associated with

No associations

Rating

Pebbling and Optimal Pebbling in Graphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Pebbling and Optimal Pebbling in Graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Pebbling and Optimal Pebbling in Graphs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-500610