The 2-pebbling Property for Dense Graphs  

作　　者：Ze Tu GAO Jian Hua YIN 

机构地区：[1]Department of Mathematics, College of Information Science and Technology

出　　处：《Acta Mathematica Sinica,English Series》2013年第3期557-570,共14页数学学报（英文版）

基　　金：Supported by National Natural Science Foundation of China (Grant Nos. 11161016 and 10861006);Natural Science Foundation of Hainan Province of China (Grant No. 112004)

摘　　要：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）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）

关 键 词：Pebbling number 2-pebbling property bipartite graph 

分 类 号：O157.5[理学—数学] O152.7[理学—基础数学]