Abstract:

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Þ 6 f1ðGÞf1ðHÞ. Herscovici further conjectured that fstðG  HÞ 6
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.

Key words: Thorn graph ｜ t-Pebbling number ｜ Graham&rsquo, s conjecture｜  Herscovici&rsquo, s conjecture