{
  "id": "math/0406123",
  "version": "v1",
  "published": "2004-06-07T16:45:50.000Z",
  "updated": "2004-06-07T16:45:50.000Z",
  "title": "Pebbling in Dense Graphs",
  "authors": [
    "Andrzej Czygrinow",
    "Glenn Hurlbert"
  ],
  "comment": "10 pages",
  "journal": "Austral. J. Combin. 29 (2003), 201--208",
  "categories": [
    "math.CO"
  ],
  "abstract": "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.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2004-06-07T16:45:50.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05D05",
      "05C35",
      "05A20"
    ],
    "keywords": [
      "dense graphs",
      "minimum degree",
      "minimum number pi",
      "pebbling threshold",
      "chosen configuration"
    ],
    "tags": [
      "journal article"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 10,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2004math......6123C"
    }
  }
}