Graham's Pebbling Conjecture Holds for the Product of a Graph and a Sufficiently Large Complete Graph

Abstract

For connected graphs $G$ and $H$, Graham conjectured that $\pi(G\square H)\leq\pi(G)\pi(H)$ where $\pi(G), \pi(H)$, and $\pi(G\square H)$ are the pebbling numbers of $G$, $H$, and the Cartesian product $G\square H$, respectively. In this paper, we show that the inequality holds when $H$ is a complete graph of sufficiently large order in terms of graph parameters of $G$.

Keywords

• graph pebbling
• cartesian product graph
• graham's conjecture