Herscovici’s Conjecture on the Product of the Thorn Graphs of the Complete Graphs  

作　　者：Dong-Lin Hao Ze-Tu Gao Jian-Hua Yin 

机构地区：[1]Department of Mathematics,College of Information Science and Technology,Hainan University,Haikou 570228,China

出　　处：《Journal of the Operations Research Society of China》2014年第2期263-269,共7页中国运筹学会会刊（英文）

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

关 键 词：Thorn graph t-Pebbling number Graham’s conjecture Herscovici’s conjecture 

分 类 号：O15[理学—数学]