Graham’s Pebbling Conjecture on the Middle Graphs of Even Cycles

Abstract

A pebbling move on a graph $G$ consists of taking two pebbles off one vertex and placing one on an adjacent vertex. The pebbling number of a graph $G$, denoted by $f(G)$, is the least integer $n$ such that, however $n$ pebbles are located on the vertices of $G$, we can move one pebble to any vertex by a sequence of pebbling moves. For any connected graphs $G$ and $H$, Graham conjectured that $f(G\times H)\le f(G)f(H)$. In this paper, we give the pebbling number of some graphs and prove that Graham’s conjecture holds for the middle graphs of some even cycles.