Graph pebbling

Graph pebbling is a mathematical game played on a graph with zero or more pebbles on each of its vertices. 'Game play' is composed of a series of pebbling moves. A pebbling move on a graph consists of choosing a vertex with at least two pebbles, removing two pebbles from it, and adding one to an adjacent vertex (the second removed pebble is discarded from play). π(G), the pebbling number of a graph G, is the lowest natural number n that satisfies the following condition:

Given any target or 'root' vertex in the graph and any initial configuration of n pebbles on the graph, it is possible, after a possibly-empty series of pebbling moves, to reach a new configuration in which the designated root vertex has one or more pebbles.

For example, on a graph with 2 vertices and 1 edge connecting them, the pebbling number is 2. No matter how the two pebbles are placed on the vertices of the graph it is always possible to arrive at the desired result of the chosen vertex having a pebble; if the initial configuration is the configuration with one pebble per vertex, then the objective is trivially accomplished with zero pebbling moves. One of the central questions of graph pebbling is the value of π(G) for a given graph G.

Other topics in pebbling include cover pebbling, optimal pebbling, domination cover pebbling, bounds, and thresholds for pebbling numbers, as well as deep graphs.

One application of pebbling games is in the security analysis of memory-hard functions in cryptography.^[1]

π(G) — the pebbling number of a graph

The game of pebbling was first suggested by Lagarias and Saks, as a tool for solving a particular problem in number theory. In 1989 F.R.K. Chung introduced the concept in the literature^[2] and defined the pebbling number, π(G).

The pebbling number for a complete graph on n vertices is easily verified to be n: If we had n − 1 pebbles to put on the graph, then we could put one pebble on each vertex except the target. As no vertex has two or more pebbles, no moves are possible, so it is impossible to place a pebble on the target. Thus, the pebbling number must be greater than n − 1. Given n pebbles, there are two possible cases. If each vertex has one pebble, no moves are required. If any vertex is bare, at least one other vertex must have two pebbles on it, and one pebbling move allows a pebble to be added to any target vertex in the complete graph.^[2]

π(G) for families of graphs

The pebbling number is known for the following families of graphs:

• ${\displaystyle \pi (K_{n})=n}$, where ${\displaystyle K_{n}}$ is a complete graph on n vertices.^[2]
• ${\displaystyle \pi (P_{n})=2^{n-1}}$, where ${\displaystyle P_{n}}$ is a path graph on n vertices.^[2]
• ${\displaystyle \pi (W_{n})=n}$, where ${\displaystyle W_{n}}$ is a wheel graph on n vertices.

Graham's pebbling conjecture

Unsolved problem in mathematics:

Is the pebbling number of a Cartesian product of graphs at most the product of the pebbling number of the graphs?

(more unsolved problems in mathematics)

Chung (1989) credited Ronald Graham with the conjecture that the pebbling number of a Cartesian product of graphs is at most equal to the product of the pebbling numbers of the factors.^[3] This has come to be known as Graham's pebbling conjecture. It remains unsolved, although special cases are known.^[4]

γ(G) — the cover pebbling number of a graph

Crull et al. introduced the concept of cover pebbling. The cover pebbling number of a graph G, γ(G), is the minimum number of pebbles needed so that from any initial arrangement of the pebbles, after a series of pebbling moves, the graph is covered: there is at least one pebble on every vertex.^[5] A result called the stacking theorem finds the cover pebbling number for any graph.^[6][7]

The stacking theorem

According to the stacking theorem, the initial configuration of pebbles that requires the most pebbles to be cover solved happens when all pebbles are placed on a single vertex. Based on this observation, define

${\displaystyle s(v)=\sum _{u\in V(G)}2^{d(u,v)}}$

for every vertex v in G, where d(u,v) denotes the distance from u to v. Then the cover pebbling number is the largest s(v) that results.

γ(G) for families of graphs

The cover pebbling number is known for the following families of graphs:

• ${\displaystyle \gamma (K_{n})=2n-1}$, where ${\displaystyle K_{n}}$ is a complete graph on n vertices.
• ${\displaystyle \gamma (P_{n})=2^{n}-1}$, where ${\displaystyle P_{n}}$ is a path graph on n vertices.
• ${\displaystyle \gamma (W_{n})=4n-9}$, where ${\displaystyle W_{n}}$ is a wheel graph on n vertices.^[8]

See also

• Pebble game
• Proof of space

References

1. Alwen, Joël; Serbinenko, Vladimir (2014), High Parallel Complexity Graphs and Memory-Hard Functions, retrieved 2024-01-15
2. Chung, Fan R. K. (1989). "Pebbling in hypercubes". SIAM Journal on Discrete Mathematics. 2 (4): 467–472. doi:10.1137/0402041. MR 1018531.
3. See Chung (1989), question 3, page 472.
4. Pleanmani, Nopparat (2019). "Graham's pebbling conjecture holds for the product of a graph and a sufficiently large complete bipartite graph". Discrete Mathematics, Algorithms and Applications. 11 (6): 1950068, 7. doi:10.1142/s179383091950068x. MR 4044549. S2CID 204207428.
5. Crull, Betsy; Cundiff, Tammy; Feltman, Paul; Hurlbert, Glenn H.; Pudwell, Lara; Szaniszlo, Zsuzsanna; Tuza, Zsolt (2005), "The cover pebbling number of graphs" (PDF), Discrete Mathematics, 296 (1): 15–23, arXiv:math/0406206, doi:10.1016/j.disc.2005.03.009, MR 2148478, S2CID 5109099
6. Vuong, Annalies; Wyckoff, M. Ian (October 18, 2004). "Conditions for Weighted Cover Pebbling of Graphs". arXiv:math/0410410.
7. Sjöstrand, Jonas (2005). "The cover pebbling theorem". Electronic Journal of Combinatorics. 12: Note 22. doi:10.37236/1989. MR 2180807.
8. Watson, Nathaniel G.; Yerger, Carl R. (2006). "Cover pebbling numbers and bounds for certain families of graphs". Bulletin of the Institute of Combinatorics and Its Applications. 48: 53–62. arXiv:math/0409321. MR 2259702.

Further reading

• Chan, Melody; Godbole, Anant P. (2008). "Improved pebbling bounds". Discrete Mathematics. 308 (11): 2301–2306. arXiv:math/0510045. doi:10.1016/j.disc.2006.06.032. MR 2404560. S2CID 5501949.
• Hurlbert, Glenn H. (1999). "A survey of graph pebbling" (PDF). Proceedings of the Thirtieth Southeastern International Conference on Combinatorics, Graph Theory, and Computing (Boca Raton, FL, 1999). Congressus Numerantium. Vol. 139. pp. 41–64. MR 1744229.
• Pachter, Lior; Snevily, Hunter S.; Voxman, Bill (1995). "On pebbling graphs" (PDF). Proceedings of the Twenty-Sixth Southeastern International Conference on Combinatorics, Graph Theory and Computing (Boca Raton, FL, 1995). Congressus Numerantium. Vol. 107. pp. 65–80. MR 1369255. Archived from the original (PDF) on 2015-11-25.