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

• Published in: Journal of the Operations Research Society of China (Internet) 2014-06, Vol.2 (2), p.263-269
• Main Authors: Hao, Dong-Lin, Gao, Ze-Tu, Yin, Jian-Hua
• Format: Article
• Language: English
• Subjects: Apexes; Graph theory; Graphs; Hypotheses
• ISSN: 2194-668X; 2194-6698
• DOI: 10.1007/s40305-014-0044-0

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 ft(G) of a simple connected graph G is the smallest positive integer such that for every distribution of ft(G) 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, f1(G×H)⩽f1(G)f1(H). Herscovici further conjectured that fst(G×H)⩽fs(G)ft(H) 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.