Previous issue ·  Next issue ·  Recently posted articles ·  Most recent issue · All issues   
Home Overview Authors Editorial Contact Subscribe

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