Integer-Programming Bounds on Pebbling Numbers of Cartesian-Product Graphs

Graph pebbling, as introduced by Chung, is a two-player game on a graph G. Player one distributes “pebbles” to vertices and designates a root vertex. Player two attempts to move a pebble to the root vertex via a sequence of pebbling moves, in which two pebbles are removed from one vertex in order to place a single pebble on an adjacent vertex. The pebbling number of a simple graph G is the smallest number \(\pi _G\) such that if player one distributes \(\pi _G\) pebbles in any configuration, player two can always win. Computing \(\pi _G\) is provably difficult, and recent methods for bounding \(\pi _G\) have proved computationally intractable, even for moderately sized graphs.