Skip to Main Content

Graph Pebbling: A Blend of Graph Theory, Number Theory, and Optimization

Glenn Hurlbert
Franklin Kenter

Communicated by Notices Associate Editor Emilie Purvine

Article cover

1. Introduction

There are many graph-theoretic subjects that could go under the umbrella of “Moving Things Around on Graphs.” For example, in network optimization, one moves packages from supplies at some vertices to demands at others, with costs accrued per package across edges, attempting to do so most cheaply. In network flow, one tries to maximize the amount of material that can move from a source to a sink, subject to the capacities along edges and the conservation of flow at other vertices along the way. In various versions of pursuit and evasion, cops and robbers take turns moving along edges with the cops trying to capture robbers by landing on them; one tries to minimize the number of cops necessary to always capture the robbers. Zero forcing, black pebbling, chip firing, black and white pebbling, graph pegging, and rigid pebbling are other examples, all with different rules for moving, different objectives, and different constraints and/or costs. While some of these topics model real-world problems, others model pure mathematical problems such as space-time tradeoffs in computational complexity, efficient matrix storage during Cholesky factorization, rigid structures in computational geometry, and matrix rank and nullity computation. The graph pebbling model we discuss here is used to translate a number-theoretic problem into graph theory. It has also developed into a rich subject in its own right.

In this article, we present a range of paradigms within this field and, for each one, share some of the major results, conjectures, and open problems. Many of these problems are accessible to those both at many levels, from undergraduate (e.g., 78919) to seasoned emeritus, and from various backgrounds, from algebra and graph theory to probability and discrete optimization. In fact, many well-known professionals (e.g., Bukh, Elledge, Gibbons, Herscovici, Moews, Pachter, Pudwell, Tomova, Wierman, Xue, Yerger, and others) have produced great graph pebbling results during their time as undergraduates. For interested readers, the two resources 1213 contain references for most of the results not cited below.

2. Number-Theoretic Origins

2.1. Zero-sum subsequences

The story of graph pebbling begins with Erdős and zero-sum problems. Zero-sum problems are combinatorial problems in the context of finite abelian groups that determine how large a set (or sequence) of elements must be such that some subset (or subsequence) with prescribed constraints has a zero sum.

Theorem 1 (Erdős-Ginzburg-Ziv, 1961).

Let be a positive integer. Any sequence of length of elements from has a subsequence of length exactly that sums to .

This is best possible; consider the sequence of “0”s and “1”s, which has no nonempty subsequence of length that sums to .

More generally, one can ask all sorts of questions regarding the length of a sequence before the sum of some (nonempty) subsequence has a specified property. For instance, if is a sequence of elements of a group , then the pigeonhole principle implies that there is a nonempty zero-sum subsequence. The minimum such length for which a zero-sum subsequence is guaranteed is called the Davenport constant of . For , is best possible (consider a sequence of “1”s), so the Davenport constant of is .

Erdős and Lemke conjectured that there is a nonempty zero-sum subsequence of with the additional condition that . A stronger condition is that , which can be written as , where we write for the order of an element in a group (in this case ). This sum is often referred to as the cross number of the subsequence , which plays a vital role in factorization theory. Kleitman and Lemke answered this stronger question in the affirmative.

Theorem 2 (Lemke-Kleitman, 1989).

Let be a positive integer. Let be a sequence of with length . Then there is some subsequence of such that both

The natural extension of their work is to arbitrary groups, which remains open for nonabelian .

Conjecture 3 (Lemke-Kleitman, 1989).

Let be a finite additive group. Let be a sequence of with length . Then there is some subsequence of such that both

2.2. Chung’s proof of the Lemke-Kleitman Theorem

The original proof of the Lemke-Kleitman Theorem relied on an inductive argument based on a multitude of possible interactions between elements. Lagarias and Saks proposed a simplified approach to the Erdős-Lemke problem, and Chung was the first one to introduce it to the literature 6. The main concept is to combine elements with like prime factorizations. Let be the prime factorization of . For each element in the sequence , write , where is relatively prime to .

Choose any exponents and let be a subsequence of containing elements of the form (where is not necessarily relatively prime to ). If, for some , , then there is a subsequence of , of size at most , such that the sum of the elements in necessarily has the form . Furthermore, if each satisfies

then

Thereafter, we will treat as a single entity, where the value of is , and the notation is taken to denote . Note that these definitions are applied recursively, as an element may itself be a set, rather than a number. By iteratively and strategically applying such groupings, one can find a zero-sum subsequence of that also obeys the cross number condition. This is exactly how Chung’s proof of the Lemke-Kleitman Theorem works. In this sense, her proof can be viewed as an abstract puzzle game. That game is graph pebbling!

The translation of the Erdős-Lemke problem into graph pebbling is not trivial. The essence of the proof is to (1) build the divisor lattice , (2) view the given numbers as pebbles, placed naturally in according to common factors with , (3) observe that each pebble obeys local versions of the two required conditions, (4) model certain movements of the pebbles in the lattice by “pebbling steps” (to be defined later), (5) show that those steps preserve the two local conditions as illustrated above, (6) observe that any pebble that reaches the bottom represents a solution to the Erdős-Lemke problem, and finally (7) prove that it is always possible to move a pebble to the minimal vertex via pebbling steps, given any configuration of pebbles. A detailed translation is given by Elledge and Hurlbert, who gave a Chung-like pebbling proof of the Lemke-Kleitman conjecture for abelian groups (originally resolved by Geroldinger).

Figure 1.

The upside-down divisor lattice of , with the number placed as a pebble at .

We now illustrate the pebbling movement of this approach with a specific example as seen in Figure 1. Consider a sequence of five pebbles that are placed at , such as . Because these are all multiples of , it is simpler to represent them just as those multiples, and simpler still to reduce them modulo 5, becoming the sequence . Now it is easier to spot a zero sum in , such as the final three numbers (4,2,4). Then we can move, as a pebbling step, the corresponding subsequence down the red edge to as a single “superpebble,” labeled by the sequence . Notice that , and that . This is the essence of how pebbling models both sums. Any superpebble that reaches the bottom will be a zero sum with cross number at most 1.

Figure 2.

Embedding the divisor lattice into as a retract. The thick edges display . Then the thin edges can be mapped to the thick ones (of the same color) in an adjacency-preserving manner.

The final stage (7) above is handled by reducing to the square-free case. That is, if , we reduce the proof on to that on , where is any product of distinct primes with , often referred to as , the lattice subsets of . One can see that is the product of paths, having lengths , while is the product of paths, each of length 1. Because is a sublattice of (see Figure 2)—in fact, it is a retract: a homomorphic image of —homomorphic images of pebbling steps in are pebbling steps in . Chung then uses the stronger recursive nature of to solve the problem there more easily. We will illustrate her technique in Section 3.4.

3. Lagarias-Saks Pebbling

We will assume basic familiarity with graphs as sets of vertices and edges (unordered pairs of vertices), and use the notation for the number of vertices of a graph . All graphs we consider are connected. Common notation for graphs on vertices includes the complete graph in which every pair of vertices is adjacent, the path in which only consecutive vertices are adjacent, and the cycle which adds an edge between the endpoints of . For two vertices and , the distance function measures the fewest number of edges in a path from to . The eccentricity of a vertex of is defined , while the diameter of a graph is defined . Sometimes we drop the subscript when the context is clear. We write for the base 2 logarithm. Additionally, we write (resp., ) if (resp., ) for some and all large enough ; and . We also use to mean that as .

3.1. Pebbling basics

A configuration of pebbles on the vertices of a connected graph is a function (the nonnegative integers), so that counts the number of pebbles placed on the vertex . We write for the size of ; i.e., the number of pebbles in the configuration. A pebbling step from a vertex to one of its neighbors (denoted ) reduces by two and increases by one. Given a specified target vertex we say that is -fold -solvable if some sequence of pebbling steps places pebbles on . Conversely, if no such steps exist, then is -unsolvable. We are concerned with determining , the minimum positive integer such that every configuration of size on the vertices of is -fold -solvable. The invariant is well defined since, for large enough , the pigeonhole principle guarantees that some vertex will contain at least pebbles, which can by itself solve . The -fold pebbling number of is defined to be . When , we simply write , which is the pebbling number of .

The configuration with a single pebble on every vertex except the target shows that , the number of vertices of the graph , while the configuration with pebbles on the farthest vertex from , and no pebbles elsewhere, shows that when is chosen to have .

One can also view as the graph on all binary -tuples, pairs of which that differ in exactly one coordinate are joined by an edge. In this guise, is often referred to as the -dimensional hypercube. As part of her work on the Lemke-Kleitman Theorem, Chung proves the following.

Theorem 4 (Chung 6).

.

In particular, both of the previous bounds are simultaneously tight, as .

To provide an alternative solution to the Erdős-Lemke problem, Chung actually showed more. Given a positive integer , let its factorization be and define . Alter the pebbling step rule so that, in of the dimensions of , pebbles (instead of 2) must be removed from a vertex to move one pebble in those dimensions. Chung showed in this case that the pebbling number of with these generalized pebbling steps is , and so the Lemke-Kleitman Theorem holds.

Figure 3.

The pyramid graph, with -unsolvable configuration shown.

3.2. Class 0 graphs: When does ?

Returning to the two-to-one pebbling rule, graphs that, like , have have come to be known as Class 0. The terminology comes from a lovely theorem of Pachter, Snevily, and Voxman, which states that if , then ; thus there are two classes of diameter-two graphs—Class 0 and Class 1. If is disconnected for some vertex , then . Let and be different connected components of with , and define the configuration by , , and for all other vertices . Then, is -unsolvable of size . The minimum number of vertices whose removal disconnects a graph is called its connectivity. Thus, Class 0 graphs are 2-connected.

There are other properties that Class 0 graphs must have. For example, denote by the set of vertices of distance at most from vertex . Cranston et al. 7 observe that if is Class 0 and and are vertices with for some and , then —otherwise the configuration with pebbles on , no pebbles on other vertices of , and 1 pebble on each remaining vertex is -unsolvable of size at least . They use this Neighborhood Lemma to prove that every Class 0 graph with vertices has at least edges. At present, the Class 0 graph with the fewest edges known is the wheel, a cycle with a central vertex adjacent to every cycle vertex, having edges. Are there Class 0 graphs with fewer edges?

The family of 2-connected Class 1 diameter-2 graphs were later characterized by Clarke, Hochberg, and Hurlbert, the main property of which is the induced containment of the (Class 1) pyramid shown in Figure 3. The other important property is that every vertex not in the pyramid lives geometrically inside one of its triangles, and vertices from different triangle interiors are not adjacent. In a probabilistic sense, almost all graphs have diameter two—think of the probability that some two vertices don’t have a common neighbor. Now consider how unlikely it is to fit into this restrictive pyramid structure: at best of all graphs are like this since, if there is a pyramid, each of the nonpyramid vertices have at least three nonneighbors. Thus, almost all graphs are Class 0.

One can say more. As shown by Postle et al. 20, graphs of diameter three can have pebbling numbers as high as , but no more, while graphs of diameter four have pebbling numbers at most . The techniques used to achieve these results include “discharging” which is the main technique used in the proof of the celebrated Four-Color Theorem. A higher diameter can push pebbling numbers to the exponential range (e.g., ). In general, Postle showed that a graph with diameter has pebbling number at most

On the other hand, high connectivity (ensuring many paths to the target) can keep pebbling numbers low. Czygrinow et al. 10 proved that for all , there is a such that every graph with diameter and connectivity at least is Class 0. The Erdős-Renyi random graph model places edges independently with probability between pairs of vertices (the counting above is for the model ). The authors proved that (it was shown by Clarke et al. to be at least ), and used the result to prove that a random graph with edge probability is almost surely Class 0. The proof used known theorems about the thresholds for having connectivity at least and diameter at most . It is interesting how close this value is to the connectivity threshold of , yet there is plenty of room for improvement in the upper and lower bounds for .

Figure 4.

The Petersen graph .

One nice application of the diameter-connectivity theorem is to Kneser graphs, known for their importance in many subareas of graph theory and combinatorics, including graph coloring, graph embedding, and extremal set theory, among others. For , the Kneser graph has all -subsets of for vertices, with edges joining disjoint pairs. is the complete graph , and the famous Petersen graph in Figure 4 is the smallest example for . Readers should find it an enjoyable puzzle to prove that the Petersen graph is Class 0. (There are at least five distinct proofs in the literature, one of which follows from the diameter-two classification above; two others appear below.) In fact, it was shown in 12 that is Class 0 for all . Furthermore, with the diameter-connectivity result in hand, they prove that, for any constant , there is an integer such that, for all and , is Class 0. With this evidence, one cannot help but believe that is Class 0 for all , and that some clever idea to prove it lies in wait. The subject could use more Class 0 sufficiency conditions.

Figure 5.

A configuration of weight on the path with target .

3.3. Weight functions: An optimization approach

Along these lines, there is an opportunity to use weight functions. One can think of pebbles sitting on a target as having weight 1, on a target’s neighbors as having weight , ..., and sitting on a vertex at distance from the target as having weight . The weight of a configuration is then the sum of the weights of its pebbles (see Figure 5). It is not difficult to prove, for example, that a configuration on a path can solve the target at one of its endpoints if and only if its weight is at least one. By rescaling to make all the weights integral, we can rephrase the characterization as: a configuration on a path cannot solve the target at one of its endpoints if and only if its weight is less than ; i.e., at most . Interestingly, this bound equals the sum of the weights.

This can be generalized at the cost of equivalence, and the notion leads us to techniques involving linear and integer optimization. Suppose that is a tree, with one of its leaves as target, and that . Define the weight function by , where . The pair is called a basic strategy. The Weight Function Lemma 14 says that if is an -unsolvable configuration on , then

One can extend this to all graphs as follows. Given a target in a graph , consider any tree in with as a leaf. Extend to all of by setting when ; then the Weight Function Lemma still holds. The collection of all inequalities from basic strategies gives rise to an integer optimization problem by maximizing (the size of ) over these constraints. If is the optimum value, then it shows that every -unsolvable configuration has size at most ; in other words, . This gives rise to the following integer program formulation of this graph pebbling upper bound:

There are some drawbacks to the approach, as you might imagine. Of course, integer optimization is typically exponential in the input size, but the input size (the number of such trees) is typically exponential (or worse!) in the number of vertices. Furthermore, consider the unsolvability polytope of an -vertex graph with target : the convex hull of all -unsolvable configurations on (viewing configurations as nonnegative vectors in ). The Weight Function Lemma implies that the feasible polytope of the linear optimization problem contains the unsolvability polytope—but it can be a very slack containment. To tighten that slack, Cranston et al. 7 developed additional constraints based on certain nontree subgraphs called lollipops (a path with a cycle attached to an endpoint). For instance, the tree strategies only yield , while the addition of lollipops proves .

Figure 6.

A tree constraint in the Petersen graph .

In practice, however, one can have surprisingly good success by restricting the input to a random collection of polynomially many breadth-first subtrees of depth at most , for example, and then stop with just linear optimization and the inequality . The resulting approximation can be very close, even exact, especially when the diameter of the graph is not large. We can illustrate this on the Petersen graph in Figure 6. The tree shown in blue corresponds (using the labeling from Figure 4) to the inequality

Using the symmetries yields two other trees and . These produce similar constraints, and the sum of all three constraints reveals that

so , and hence . Combined with the lower bound from having 10 vertices, this shows (with the symmetry that all vertices look the same) that the Petersen graph is Class 0. This example also illustrates the following lemma.

Lemma 5 (Uniform Covering Lemma 14).

Let be a target vertex in a graph , and let be a set of -strategies. If there is some such that for all in , then is Class 0 at .

This holds because the right-hand side of inequality 1 is the sum of the coefficients, so the same is true of any sum of such weight functions. Therefore, in a uniform sum such as inequality 2, the right-hand side, after dividing by , equals , the number of nontarget vertices. The left-hand side, with uniform coefficients, always becomes the size of after this division.

In some cases the method of weight functions offers the simplest proof of a graph’s pebbling number (or the best upper bound of it). The set of strategies used in such a proof is called a certificate. Changing the weighting system by reducing weights by more than half as we traverse the edges of a tree, proceeding away from the target, yields nonbasic strategies—it turns out that these are conic (i.e., nonnegative linear) combinations of basic strategies, and so satisfy the Weight Function Lemma as well. Thus, nonbasic strategies do not need to be included in the optimization constraints, but they can be used in a certificate. From the geometrical point of view of the unsolvability polytope, certificates will involve at most strategies. However, in practice, most certificates have size because two strategies using the same neighbor of can often be combined. Hence, finding certificates for a particular graph can even be quicker to do by hand than by computer, especially when symmetry is present, and finding them for an infinite family of graphs is really a hands-only activity.

A good example of this is powers of cycles 14. For a graph , define the th power of , denoted , by adding the edge for every pair of vertices satisfying . The pebbling exponent of , denoted , is defined to be the minimum for which is Class 0. For instance, for every on vertices, and so . Because Class 0 graphs must have , we need that . This provides the lower bound on the result for -vertex cycles that

where the upper bound comes from a certificate of carefully constructed strategies.

The following problem is an interesting question from 14 regarding the approximability of graph pebbling with weight functions. Let be the set of all tree -strategies in a graph . Is the resulting linear optimization solution a reasonable approximation to ? That is, does there exist some constant such that ? Is ?

Optimization perspectives of graph pebbling are an active area of research. For instance, Kenter et al. 15 presents optimization approaches specific to graph products. In general, describing the actual facets of the unsolvability polytopes of these approaches also remains illusive.

3.4. Graham’s conjecture: Pebbling on graph products

Chung’s proof that is inductive, but for the induction to work, it requires also proving that has the 2-Pebbling Property (2PP): two pebbles can be placed on any target of from any configuration of size at least , where is the set of vertices having at least one pebble (the support of ) and .

As a toy example of Chung’s proof technique, we prove again that the Petersen graph is Class 0, mimicking her three cases. Observe that splits into two 5-cycles and with a matching between them, suppose by symmetry that , and let be a configuration of size 10. If contains at least five pebbles, then we are done because , so assume not. Let be the neighbor of in . If contains a pebble, then the other five pebbles in can place a second pebble on , subsequently solving , so presume otherwise. If contains exactly four (resp., three) pebbles, then the six (resp., seven) pebbles in can move at least one (resp., two) pebble(s) across to , thus solving from the resulting five. If contains at most two pebbles, then has at least eight, from which we can place two pebbles on , then one on .

Figure 7.

Graphs (top left),