The 2-pebbling property and a conjecture of Graham's (Q1576576)

Assume that a set of ``pebbles'' are distributed onto the vertices of an undirected graph \(G\) (where a vertex may receive one or more pebbles, or none). A move consists in removing two pebbles from a given vertex and to place one pebble at an adjacent vertex. We say that a pebble can be moved to a vertex \(v\) when there is a sequence of moves such that in the final configuration \(v\) has at least one pebble. The pebbling number \(f(G)\) of \(G\) is the least \(m\) such that for every distribution of \(m\) pebbles a pebble can be moved to any vertex. A graph \(G\) has the 2-pebbling property if two pebbles can be moved to any vertex, provided that originally there are at least \(2f(G)- q+1\) pebbles, where \(q\) is the number of vertices having at least one pebble. All cycles (as shown in this paper) and all trees satisfy this property, while few graphs not fulfilling it are known. The Graham conjecture states that \(f(G\times H)\leq f(G)f(H)\), where \(\times\) denotes the Cartesian product. The authors prove this conjecture when (1) \(G\) and \(H\) are cycles (up a finite number of unsettled cases) and (2) \(G\) has the 2-pebbling property and \(H\) is a tree.