The Herscovici’s Conjecture for $C_m\mathrm{<img\; draggable="false"\; role="img"\; class="emoji"\; alt="◻"\; src="https://s.w.org/images/core/emoji/15.0.3/svg/25fb.svg">}{C}_n$

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 ${\pi }_t(G)$ is the smallest positive integer such that for every distribution of ${\pi }_t(G)$ pebbles and every vertex $v$, $t$ pebbles can be moved to $v$. For $t=1$, Graham conjectured that ${\pi }_1(G\mathrm{<img\; draggable="false"\; role="img"\; class="emoji"\; alt="◻"\; src="https://s.w.org/images/core/emoji/15.0.3/svg/25fb.svg">}H)\le {\pi }_1(G){\pi }_1(H)$ for any connected graphs $G$ and $H$, where $G\mathrm{<img\; draggable="false"\; role="img"\; class="emoji"\; alt="◻"\; src="https://s.w.org/images/core/emoji/15.0.3/svg/25fb.svg">}H$ denotes the Cartesian product of $G$ and $H$. Herscovici further conjectured that ${\pi }_{st}(G\mathrm{<img\; draggable="false"\; role="img"\; class="emoji"\; alt="◻"\; src="https://s.w.org/images/core/emoji/15.0.3/svg/25fb.svg">}H)\le {\pi }_s(G){\pi }_t(H)$ for any positive integers $s$ and $t$. Lourdusamy [A. Lourdusamy, “$t$-pebbling the product of graphs”, Acta Ciencia Indica, XXXII(1)(2006), 171-176] also conjectured that ${\pi }_t(C_m\mathrm{<img\; draggable="false"\; role="img"\; class="emoji"\; alt="◻"\; src="https://s.w.org/images/core/emoji/15.0.3/svg/25fb.svg">}{C}_n)\le {\pi }_1(C_m){\pi }_t(C_n)$ for cycles $C_m$ and $C_n$. In this paper, we show that ${\pi }_{st}(C_m\mathrm{<img\; draggable="false"\; role="img"\; class="emoji"\; alt="◻"\; src="https://s.w.org/images/core/emoji/15.0.3/svg/25fb.svg">}{C}_n)\le {\pi }_s(C_m){\pi }_t(C_n)$, which confirms this conjecture due to Lourdusamy.