Girth, Pebbling, and Grid Thresholds

Details Girth, Pebbling, and Grid Thresholds Girth, Pebbling, and Grid Thresholds

2004-06-08

arxiv.org/abs/math/0406156v1

Mathematics

Combinatorics

17 pages. Submitted to SIAM Journal on Discrete Mathematics

Scientific paper

In this note we answer a question of Hurlbert about pebbling in graphs of high girth. Specifically we show that for every g there is a Class 0 graph of girth at least g. The proof uses the so-called Erdos construction and employs a recent result proved by Czygrinow, Hurlbert, Kierstead and Trotter. We also use the Czygrinow et al. result to prove that Graham's pebbling product conjecture holds for dense graphs. Finally, we consider a generalization of Graham's conjecture to thresholds of graph sequences and find reasonably tight bounds on the pebbling threshold of the sequence of d-dimensional grids, verifying an important instance the generalization.

Affiliated with

Also associated with

No associations

Rating

Girth, Pebbling, and Grid Thresholds 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 Girth, Pebbling, and Grid Thresholds, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Girth, Pebbling, and Grid Thresholds will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-376127