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 2f（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 fl（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 fl（G） ≤ 1.5n ＋ 8l -- 6 for the graph G with diameter 3, where n = IV（G）I. In this paper, we prove that if s ≥ 15 and G（s,t）