Journal of the Ramanujan Mathematical Society

Volume 36, Issue 4, December 2021 pp. 261–265.

Herscovici's conjecture on products of shadow graphs of paths

Authors: A. Lourdusamy and S. Saratha Nellainayaki
Author institution:Department of Mathematics, St. Xaviers College (Autonomous), Palayamkottai, Tamilnadu, India

Summary: Given a connected graph G, a distribution on a graph G is an assignment of pebbles on the vertices of the graph G. A pebbling move is defined as for any given distribution of pebbles on the vertices of a connected graph G, a removal of two pebbles from some vertex and the placement of one of those pebbles 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 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 shadow graph of path and H is a graph satisfying the 2t-pebbling property.

Contents Full-Text PDF