Graph pebbling

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.[1]
• ${\displaystyle \pi (P_{n})\,=\,2^{n-1}}$, where ${\displaystyle P_{n}}$ is a path graph on n vertices.[1]
• ${\displaystyle \pi (W_{n})\,=\,n}$, where ${\displaystyle W_{n}}$ is a wheel graph on n vertices.

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 in the product.[2] This has come to be known as Graham's pebbling conjecture. As of 2019, it remains unsolved, although special cases are known.[3]

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.

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 on n vertices.
• ${\displaystyle \gamma (W_{n})\,=\,4n-9}$, where ${\displaystyle W_{n}}$ is a wheel graph on n vertices.[7]