Pebbling C5× C5using linear programming
A. Lourdusamy, S. Somasundaram · Journal of Discrete Mathematical Sciences and Cryptography · 2001
The pebbling number, f(G), of a connected graph G is the least positive integer such that from any distribution of f(G) pebbles on the vertices of G, we can move a pebble to any vertex by a sequence of moves, each move taking two pebbles off a vertex and placing one on an adjacent vertex. Graham conjectured that for any connected graphs G and H, f(G × H) ≤ f(G) f(H). David S. Herscovici and Aparna W. Higgins [DA 98] proved this conjecture when G = H = C 5. We use linear programming to prove this result.