Before we move into the definition of the pebbling number of a graph G (here, the term graph refers to a simple graph without loops and multiple edges), we must know about the following terms:
Distribution
A distribution (configuration) D of pebbles on a graph G = (V,E) can be thought of as a function D: V(G) → N ∪ {0}. The value D(v) equals the number of pebbles placed at vertex v, and the size of the configuration is the number |D| = ∑v ∈ V (G) D(v) of pebbles placed in total on G.
Pebbling Move
Suppose D is a configuration of pebbles on a graph G. A pebbling move (step) consists of removing two pebbles from one vertex and then placing one pebble at an adjacent vertex. We say a pebble can be moved to a vertex v, the target vertex, if we can apply pebbling moves repeatedly (if necessary) so that in the resulting configuration the vertex v has at least one pebble.
An example of showing pebbling move
A distribution of four pebbles has shown in the below figure.
Clearly, we can move two pebbles to the cut vertex of the graph that has been shown in the above figure.
Now we are going to state the definition of pebbling number of a graph G. The pebbling number of a graph G, f(G), is the least n such that, for any configuration of n pebbles to the vertices of G, we can move one pebble to any vertex by a sequence of moves, each move taking two pebbles off one vertex and placing one on an adjacent vertex.
We here give some facts about f(G), most of which are quite straightforward (verify them yourself!):
Fact 1. The pebbling number of a graph G satisfies f(G) ≥ max{2diam(G), |V (G)|}
Fact 2. If G' is a spanning subgraph of G, then f(G') ≥ f(G).
Fact 3. For a path Pn on n vertices, f(Pn) = 2 n-1
Fact 4. For a complete graph Km, f(Km) = m.
To prove f(G) = k, for a graph G, we have to show that f(G) ≥ k (take a distribution of size k-1 and show that one pebble could not be moved to a vertex of G) and f(G) ≤ k (consider all the configurations of size k and show that we could move one pebble to any vertex of G).
For any two graphs G and H, we define the product G × H to be the graph with vertex set {(u,v): u ∈ V(G), v ∈ V(H)} and there is an edge between (u, v) and (u', v') if and only if (u = u' and {v,v'} ∈ E(H)) or ({u,u'} ∈ E(G) and v = v').
It is easy to see that the 1-cube is K2; the 2-cube is K2 × K2; and the n-cube Qn is Qn-1 × K2. Chung proved that f(Qn) = 2n. This result gave us the following question: what is the pebbling number of G × H? Graham gave an answer for this as a conjecture which many feel is the Holy Grail of the subject.
Conjecture (Graham's Conjecture) Every pair of graphs G and H satisfy f(G × H) ≤ f(G) f(H).
Many instances of this conjecture have been verified, including when G and H are both cycles or both trees, and when G is a tree, cycle, complete graph, or complete bipartite graph and H has 2-pebbling property (will see it after the next section).
t-pebbling number of a graph G
Instead of placing one pebble on any specified target vertex, if we place t pebbles then it is called the t-pebbling number of G. That is, the t-pebbling number of a graph G, ft(G), is the least m such that, for any configuration of m pebbles to the vertices of G, we can move t pebbles to any vertex by a sequence of moves. Clearly, f1(G) = f(G), the pebbling number of G.
There are many results on t-pebbling number of graphs (will see in the next Section). Lourdusamy generalized the Graham's conjecture as follows:
Conjecture: For connected graphs G and H, ft(G × H) ≤ f(G) ft(H).
Furthermore, Herscovici conjectured that fst(G × H) ≤ fs(G) ft(H) for any connected graphs G and H.
These conjectures have also been verified for some graphs.