Computing Bounds on Product-Graph Pebbling Numbers

Abstract

Given a distribution of pebbles to the vertices of a graph, a pebbling move removes two pebbles from a single vertex and places a single pebble on an adjacent vertex. The pebbling number $\pi (G)$ is the smallest number such that, for any distribution of $\pi (G)$ pebbles to the vertices of $G$ and choice of root vertex $r$ of $G$, there exists a sequence of pebbling moves that places a pebble on $r$. Computing $\pi (G)$ is provably difficult, and recent methods for bounding $\pi (G)$ have proved computationally intractable, even for moderately sized graphs. Graham conjectured that $\pi (G\square H)\le \pi (G)\pi (H)$, where $G\square H$ is the Cartesian product of $G$ and $H$ (1989). While the conjecture has been verified for specific families of graphs, in general it remains open. This study combines the focus of developing a computationally tractable, IP-based method for generating good bounds on $\pi (G\square H)$, with the goal of shedding light on Graham's conjecture.We provide computational results for a variety of Cartesian-product graphs, including some that are known to satisfy Graham's conjecture and some that are not. Our approach leads to a sizable improvement on the best known bound for $\pi (L\square L)$, where $L$ is the Lemke graph, and $L\square L$ is among the smallest known potential counterexamples to Graham's conjecture.

27 pages, 2 figures, 8 tables

References in corpus (1)

• Pebbling on Graph Products and other Binary Graph Constructions