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 small...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 t-pebbling number f_(t)(G)of a simple...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 t-pebbling number f_(t)(G)of a simple connected graph G is the smallest positive integer such that for every distribution of fteGT pebbles on the vertices of G,we can move t pebbles to any target vertex by a sequence of pebbling moves.Graham conjectured that for any connected graphs G and H,f_(1)(G×H)≤f1(G)f1(H).Herscovici further conjectured that fst(G×H)≤6 fseGTfteHT for any positive integers s and t.Wang et al.(Discret Math,309:3431–3435,2009)proved that Graham’s conjecture holds when G is a thorn graph of a complete graph and H is a graph having the 2-pebbling property.In this paper,we further show that Herscovici’s conjecture is true when G is a thorn graph of a complete graph and H is a graph having the 2t-pebbling property.展开更多
基金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 t-pebbling number f_(t)(G)of a simple connected graph G is the smallest positive integer such that for every distribution of fteGT pebbles on the vertices of G,we can move t pebbles to any target vertex by a sequence of pebbling moves.Graham conjectured that for any connected graphs G and H,f_(1)(G×H)≤f1(G)f1(H).Herscovici further conjectured that fst(G×H)≤6 fseGTfteHT for any positive integers s and t.Wang et al.(Discret Math,309:3431–3435,2009)proved that Graham’s conjecture holds when G is a thorn graph of a complete graph and H is a graph having the 2-pebbling property.In this paper,we further show that Herscovici’s conjecture is true when G is a thorn graph of a complete graph and H is a graph having the 2t-pebbling property.
