Pebbling and optimal pebbling in graphs

trees, and hypercubes, a new linear-time algorithm for computing H(G) on trees, and new results on Pi(OPT)(G). If G is connected and has n vertices, then Pi(OPT)(G) <= inverted right perpendicular 2n/3 inverted left perpendicular (sharp for paths and cycles). Let a(n,k) be the maximum of Pi(OPT)(G) when G is a connected n-vertex graph with delta(G) >= k. Always 2 inverted right perpendicular n/k+1 inverted left perpendicular <= a(n,k) <= 4 inverted right perpendicular n/k+1 inverted left perpendicular, with a better lower bound when k is a nontrivial multiple of 3. Better upper bounds hold for n-vertex graphs with minimum degree k having large girth; a special case is Pi(OPT)(G) <= 16n/(k(2) + 17) when G has girth at least 5 and k >= 4. Finally, we compute Pi(OPT)(G) in special families such as prisms and Mobius ladders. 0 2007 Wiley Periodicals, Inc.