• HERSCOVICI’s CONJECTURE ON THE PRODUCTS OF PATHS, COMPLETE GRAPHS

Abstract

Given a connected graph G, distribute k pebbles on its vertices in some configuration C. Specifically a configuration on a graph G is a function f from V(G) to NU{0} representing an assignment of  pebbles on G. We call the total number of pebbles, k, the size of the configuration. A pebbling move is defined as the removal of two pebbles from a vertex and addition of one of those pebbles on an adjacent vertex. The pebbling number of a connected graph G is the smallest number f(G) such that, however  f(G) pebbles are distributed on the vertices of G, we can move a pebble to any vertex by a sequence of pebbling moves. 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(G×H) ≤ f(G) f(H). Herscovici further conjectured that f_st(G×H) ≤ f_s(G) f_t(H) for any positive integers s and t. In this paper we show that Herscovici’s conjecture is true when G is a path, complete graph and H is a graph satisfying the 2t- pebbling property.