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

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 $$f_t(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$$ , $$f_1(G\times H)\leqslant f_1(G)f_1(H)$$ . Herscovici further conjectured that $$f_{st}(G\times H)\leqslant f_s(G)f_t(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.