The Graham’s Pebbling Conjecture for \(K_{r,s}^{-k_1} \times K_{m,n}^{-k_2}\).

Abstract

The pebbling number \(f(G)\) of a graph \(G\) is the smallest number \(k\) such that, however \(n\) pebbles are placed on the vertices of \(G\), we can move a pebble to any vertex by a sequence of moves, each move taking two pebbles off one vertex and placing one on an adjacent vertex. Graham conjectured that for any connected graphs \(G\) and \(H\), \(f(G \times H) \leq f(G)f(H)\), where \(G \times H\) represents the Cartesian product of \(G\) and \(H\). In this paper, we prove that \(f(G \times H) \leq f(G)f(H)\) when \(G\) has the two-pebbling property and \(H = K_{r,s}^{ – k}\), a graph obtained from the \(r \times s\) complete bipartite graph \(K_{r,s}\) by deleting \(k\) edges which form a matching. We also show that Graham’s conjecture holds for \(K_{r,s}^{-k_1} \times K_{m,n}^{-k_2}\).