Graham's Pebbling Conjecture

Definitions and mathematical statement

In the usual finite, connected, undirected graph setting, a pebble configuration on a graph $G$ is a function $c:V(G)\to{\mathbb{Z}}_{\geq0}$, with total size $|c|=\sum_{v\in V(G)}c(v)$. A pebbling move removes two pebbles from one vertex $u$ with $c(u)\geq2$ and adds one pebble to an adjacent vertex $v$; the other removed pebble is discarded. The pebbling number $\pi(G)$ is the least integer $m$ such that, for every configuration of total size $m$ and every target vertex $r\in V(G)$, some finite sequence of pebbling moves produces a configuration with a pebble at $r$.

The Cartesian product $G\mathbin{\square}H$ has vertex set $V(G)\times V(H)$; $(g,h)$ and $(g',h')$ are adjacent exactly when either $g=g'$ and $hh'\in E(H)$, or $h=h'$ and $gg'\in E(G)$. The literal inequality asked in the supplied statement and repeated in its background is \[\pi(G\mathbin{\square}H)\geq\pi(G)\pi(H).\] The direction is retained exactly. There is a naming/formulation issue: the customary formulation called Graham's pebbling conjecture is the upper product bound $\pi(G\mathbin{\square}H)\leq\pi(G)\pi(H)$. That distinction must be checked against an authoritative source before interpreting the imported lower-bound wording as the named conjecture. This draft does not silently replace $\geq$ by $\leq$, and does not claim either inequality has been proved or refuted here. The record also does not explicitly state finiteness and connectedness; those standard hypotheses are needed for the finite-valued definition above and are identified rather than silently generalized to disconnected graphs.

The supplied literature triage, checked 2026-08-17, labels the named conjecture open (OPEN-TRIAGE), reports many graph-family and product special cases, and says no universal product inequality was verified. The background mentions paths and cycles among the special cases. Because the review does not address the displayed direction issue, its general status cannot by itself verify that this exact imported lower-bound assertion is the intended conjecture.

Short English statement

Compare the pebbling number of a Cartesian graph product with the product of the two pebbling numbers. The source asks for a lower bound, while the customary named Graham conjecture is an upper bound; the direction and graph hypotheses need review before fixing the intended target.

Sources

• Local UnsolvedMath registry, permanent ID 1390, source code catalogue entry, "Graham's Pebbling Conjecture"; both the supplied statement and background say "at least."
• "Graham's pebbling conjecture" overview, supplied secondary reference: https://en.wikipedia.org/wiki/Graham%27s_pebbling_conjecture. The record cites it for special cases and general open status; no primary theorem or original conjecture citation is supplied.
• Supplied literature triage checked 2026-08-17, OPEN-TRIAGE. It records no source alteration and cautions that dated triage does not exclude later or unindexed work; it does not resolve the inequality-direction mismatch.