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) \leq 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.