Pebbling in Dense Graphs

Details Pebbling in Dense Graphs Pebbling in Dense Graphs

2004-06-07

arxiv.org/abs/math/0406123v1

Austral. J. Combin. 29 (2003), 201--208

Mathematics

Combinatorics

10 pages

Scientific paper

A configuration of pebbles on the vertices of a graph is solvable if one can place a pebble on any given root vertex via a sequence of pebbling steps. The pebbling number of a graph G is the minimum number pi(G) so that every configuration of pi(G) pebbles is solvable. A graph is Class 0 if its pebbling number equals its number of vertices. A function is a pebbling threshold for a sequence of graphs if a randomly chosen configuration of asymptotically more pebbles is almost surely solvable, while one of asymptotically fewer pebbles is almost surely not. Here we prove that graphs on n>=9 vertices having minimum degree at least floor(n/2) are Class 0, as are bipartite graphs with m>=336 vertices in each part having minimum degree at least floor(m/2)+1. Both bounds are best possible. In addition, we prove that the pebbling threshold of graphs with minimum degree d, with sqrt{n} << d, is O(n^{3/2}/d), which is tight when d is proportional to n.

Affiliated with

Also associated with

No associations

Rating

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

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-594900