The 2-pebbling property for dense graphs.

Given a distribution of pebbles on the vertices of a connected graph G, a pebbling move on G consists of taking two pebbles off one vertex and placing one on an adjacent vertex. The pebbling number f( G) is the smallest number m such that for every distribution of m pebbles and every vertex v, a pebble can be moved to v. A graph G is said to have the 2- pebbling property if for any distribution with more than 2 f( G)- q pebbles, where q is the number of vertices with at least one pebble, it is possible, using pebbling moves, to get two pebbles to any vertex. Snevily conjectured that G( s, t) has the 2-pebbling property, where G( s, t) is a bipartite graph with partite sets of size s and t ( s ≥ t). Similarly, the ℓ-pebbling number f( G) is the smallest number m such that for every distribution of m pebbles and every vertex v, ℓ pebbles can be moved to v. Herscovici et al. conjectured that f( G) ≤ 1.5 n + 8 ℓ −6 for the graph G with diameter 3, where n = | V ( G)|. In this paper, we prove that if s ≥ 15 and G( s, t) has minimum degree at least $\left\lceil {\tfrac{{s + 1}} {2}} \right\rceil $ , then f( G( s, t)) = s + t, G( s, t) has the 2-pebbling property and f( G( s, t)) ≤ s + t + 8( ℓ − 1). In other words, we extend a result due to Czygrinow and Hurlbert, and show that the above Snevily conjecture and Herscovici et al. conjecture are true for G( s, t) with s ≥ 15 and minimum degree at least $\left\lceil {\tfrac{{s + 1}} {2}} \right\rceil $ . [ABSTRACT FROM AUTHOR]