Cartesian Product

For any two graphs $G_1$ and $G_2$ we define the cartesian product $G_1 \times G_2$ to be the graph with vertex set $V(G_1 \times G_2) = \{(v_1,v_2) | v_1 \in V(G_1), v_2 \in V(G_2) \}$ and edge set $E(G_1 \times G_2) = \{\{(v_1,v_2),(w_1,w_2)\} | (v_1=w_1$ $and$ $(v_2,w_2) \in E(G_2))$ $or$ $(v_2=w_2$ $and$ $(v_1,w_1) \in E(G_1))\}$ The cube $Q^d$ can be built recursively from the cartesian product, and Chung's result [Chu] that $\pi(Q^d)=2^d$ (and more generally the Grid Theorem below) would follow easily from Graham's Conjecture, which has generated a great deal of interest.

Graham's Conjecture.  $\pi(G_1 \times G_2) \leq \pi(G_1) \pi(G_2)$.

Partial Results

It is worth mentioning that there are some results which verify Graham's Conjecture. Among these, the conjecture holds for a tree by a tree [Moe], a cycle by a cycle [Her, HeHi, PSV], and a clique by a graph with the 2-Pebbling Property [Chu]. Recently, Feng and Kim verified the conjecture for complete bipartite graphs [FeKi1] and for wheels or fans [FeKi2]. It is also proven in [Chu] that the conjecture holds when each $G_i$ is a path. Let $P_n$ be a path with $n$ vertices and for $\mathbf{d}= \langle d_1, \ldots, d_m \rangle$ let $P_{\mathbf{d}}$ denote the graph $P_{d_1+1} \times \cdots \times P_{d_m+1}$.

Grid Theorem  For nonnegative integers $d_1, \ldots, d_m,$ $\pi(P_{\mathbf{d}})=2^{d_1 + \cdots + d_m}.$

The conjecture was also verified recently [CzHu3] for graphs of high minimum degree, using the Diameter-Connectivity Theorem.

Min. Degree Product Theorem.  If $G_1$ and $G_2$ are connected graphs on $n$ vertices that satisfy $\delta(G_i) \geq k$ and $k \geq 2^{12n/k+15},$ then $\pi(G_1 \times G_2) \leq \pi(G_1) \times \pi(G_2).$

In particular, there is a constant $c$ so that if $k > cn/ \log n$ then $G_1 \times G_2$ is Class 0.

There is also a probabilistic version of Graham's Conjecture on the Random Pebbling page.

2-Pebbling Property

A graph G is said to have the 2-pebbling property (2PP) if two pebbles can be moved to any specified vertex when the initial configuration $C$ has size $2 \pi(G)-s(C)+1$, where $s(C)$ is the size of the support $S(C)$ This property is crucial in the proof of Grid Theorem. Graphs that are known to have 2PP include trees, cliques and cubes [Chu], as well as diameter $2$ graphs [PSV]. Also, Chung proved that if $G$ has 2PP and $\pi(G \times K_t)=t \pi(G)$ then $G \times K_t$ has 2PP.

Originally, only the Lemke graph was known not to have 2PP, although a family of related graphs were conjectured in [FoSn] not to have the property either. Although that conjecture is still unresolved, Wang [Wan] proved that a slight modification of Snevily's graphs yield an infinite family of graphs, none of which have 2PP. Also found in [FoSn] is the following conjecture.

Bipartite Conjecture.   All bipartite graphs have 2PP.

$q$-Pebbling

In order to describe the generalization employed by Chung to prove the Kleitman-Lemke theorem, we need to introduce generalized pebbling. A $q$-pebbling step in $G$ consists of removing $q$ pebbles from a vertex $u$, and placing one pebble on a neighbor $v$ of $u$. We say that a pebbling step from $u$ to $v$ is greedy (semi-greedy) if ${\rm dist}(v,r) < {\rm dist}(u,r)$ $(\leq)$, where $r$ is the root vertex, and that a graph $G$ is (semi) greedy if for any configuration of $\pi(G)$ pebbles on the vertices of $G$ we can move a pebble to any specified root vertex $r$, in such a way that each pebbling step is (semi) greedy.

Let $P_{\mathbf{d}}=P_{d_1+1} \times \cdots \times P_{d_m+1}$ be a product of paths, where $\mathbf{d}= \langle d_1, \ldots, d_m \rangle$, as above. Then each vertex $v \in V(P_{\mathbf{d}})$ can be represented by a vector $\mathbf{v}= \langle v_1, \ldots v_m \rangle$, with $0 \leq v_i \leq d_i$ for each $i \leq m$. Let $\mathbf{e}_i = \langle 0, \ldots, 1, \ldots, 0 \rangle$, be the $i^{th}$ standard basis vector. Denote the vector $\langle 0, \ldots, 0 \rangle$ by $\mathbf{0}$. Then two vertices $u$ and $v$ are adjacent in $P_{\mathbf{d}}$ if and only if $|\mathbf{u}-\mathbf{v}|=\mathbf{e}_i$ for some integer $1 \leq i \leq m$. If $\mathbf{q}=(q_1, \ldots, q_m)$, then we may define $q$-pebbling in $P_{\mathbf{d}}$ to be such that each pebbling step from $\mathbf{u}$ to $\mathbf{v}$ is a $q_i$-pebbling step whenever $|\mathbf{u}-\mathbf{v}|=\mathbf{e}_i$. We denote the $q$-pebbling number of $P_{\mathbf{d}}$ by $\pi_{\mathbf{q}}(P_{\mathbf{d}})$. Chungs's proof of the Grid Theorem uses the following theorem [Chu]. For integers $q_i,d_i \geq 1$, $1 \leq i \leq m$, we use $\mathbf{q^d}$ as shorthand for the product $q_1^{d_1} \times \cdots \times q_m^{d_m}$.

Greedy Grid Theorem.  Suppose that $\mathbf{q^d}$ pebbles are assigned to the vertices of $P_{\mathbf{d}}$ and that the root $r = \mathbf{0}$. Then it is possible to move one pebble to $r$ via greedy $q$-pebbling.

In addition, it was shown in [CHH] that $\pi_{\mathbf{q}}(P_{\mathbf{d}})=\mathbf{q^d}$, and, moreover that $P_{\mathbf{d}}$ is greedy. Also in [CHH] the following generalization of Graham's Conjecture to $q$-pebbling was made.

q-Product Conjecture.  $\pi_{\mathbf{q}}(G_1 \times G_2) \leq \pi_{q_1}(G_1) \pi_{q_2}(G_2).$