Graph pebbling

Last updated August 15, 2024

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:

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:

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

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:

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

Related Research Articles

In the mathematical field of graph theory, the Petersen graph is an undirected graph with 10 vertices and 15 edges. It is a small graph that serves as a useful example and counterexample for many problems in graph theory. The Petersen graph is named after Julius Petersen, who in 1898 constructed it to be the smallest bridgeless cubic graph with no three-edge-coloring.

In the mathematical field of graph theory, a bipartite graph is a graph whose vertices can be divided into two disjoint and independent sets $and, that is, every edge connects a vertex in to one in . Vertex sets and are usually called the parts of the graph. Equivalently, a bipartite graph is a graph that does not contain any odd-length cycles.$

In graph theory, two graphs $and are homeomorphic if there is a graph isomorphism from some subdivision of to some subdivision of . If the edges of a graph are thought of as lines drawn from one vertex to another, then two graphs are homeomorphic to each other in the graph-theoretic sense precisely if they are homeomorphic in the topological sense.$

In the mathematical discipline of graph theory, a graph labeling is the assignment of labels, traditionally represented by integers, to edges and/or vertices of a graph.

In graph theory, the Kneser graph $K (n, k)$ (alternatively $KG n, k$ ) is the graph whose vertices correspond to the $k$ -element subsets of a set of $n$ elements, and where two vertices are adjacent if and only if the two corresponding sets are disjoint. Kneser graphs are named after Martin Kneser, who first investigated them in 1956.

In graph theory, a book embedding is a generalization of planar embedding of a graph to embeddings in a book, a collection of half-planes all having the same line as their boundary. Usually, the vertices of the graph are required to lie on this boundary line, called the spine, and the edges are required to stay within a single half-plane. The book thickness of a graph is the smallest possible number of half-planes for any book embedding of the graph. Book thickness is also called pagenumber, stacknumber or fixed outerthickness. Book embeddings have also been used to define several other graph invariants including the pagewidth and book crossing number.

In the mathematical area of graph theory, the Mycielskian or Mycielski graph of an undirected graph is a larger graph formed from it by a construction of Jan Mycielski. The construction preserves the property of being triangle-free but increases the chromatic number; by applying the construction repeatedly to a triangle-free starting graph, Mycielski showed that there exist triangle-free graphs with arbitrarily large chromatic number.

In graph theory, Vizing's conjecture concerns a relation between the domination number and the cartesian product of graphs. This conjecture was first stated by Vadim G. Vizing (1968), and states that, if $γ(G)$ denotes the minimum number of vertices in a dominating set for the graph $G$ , then

<span class="mw-page-title-main">Handshaking lemma</span> Every graph has evenly many odd vertices

In graph theory, a branch of mathematics, the handshaking lemma is the statement that, in every finite undirected graph, the number of vertices that touch an odd number of edges is even. For example, if there is a party of people who shake hands, the number of people who shake an odd number of other people's hands is even. The handshaking lemma is a consequence of the degree sum formula, also sometimes called the handshaking lemma, according to which the sum of the degrees equals twice the number of edges in the graph. Both results were proven by Leonhard Euler in his famous paper on the Seven Bridges of Königsberg that began the study of graph theory.

In graph theory, the Laman graphs are a family of sparse graphs describing the minimally rigid systems of rods and joints in the plane. Formally, a Laman graph is a graph on n vertices such that, for all k, every k-vertex subgraph has at most 2k − 3 edges, and such that the whole graph has exactly 2n − 3 edges. Laman graphs are named after Gerard Laman, of the University of Amsterdam, who in 1970 used them to characterize rigid planar structures. However, this characterization, the Geiringer–Laman theorem, had already been discovered in 1927 by Hilda Geiringer.

In the study of graph coloring problems in mathematics and computer science, a greedy coloring or sequential coloring is a coloring of the vertices of a graph formed by a greedy algorithm that considers the vertices of the graph in sequence and assigns each vertex its first available color. Greedy colorings can be found in linear time, but they do not, in general, use the minimum number of colors possible.

In the mathematical field of graph theory, the windmill graph $Wd(k, n)$ is an undirected graph constructed for $k \geq 2$ and $n \geq 2$ by joining $n$ copies of the complete graph $K k$ at a shared universal vertex. That is, it is a 1-clique-sum of these complete graphs.

In mathematics, the Kontsevich quantization formula describes how to construct a generalized ★-product operator algebra from a given arbitrary finite-dimensional Poisson manifold. This operator algebra amounts to the deformation quantization of the corresponding Poisson algebra. It is due to Maxim Kontsevich.

Sumner's conjecture states that every orientation of every $-vertex tree is a subgraph of every -vertex tournament. David Sumner, a graph theorist at the University of South Carolina, conjectured in 1971 that tournaments are universal graphs for polytrees. The conjecture was proven for all large by Daniela Kühn, Richard Mycroft, and Deryk Osthus.$

In the mathematical field of graph theory, the intersection number of a graph $is the smallest number of elements in a representation of as an intersection graph of finite sets. In such a representation, each vertex is represented as a set, and two vertices are connected by an edge whenever their sets have a common element. Equivalently, the intersection number is the smallest number of cliques needed to cover all of the edges of .$

<span class="mw-page-title-main">Italo Jose Dejter</span>

Italo Jose Dejter is an Argentine-born American mathematician, a retired professor of mathematics and computer science from the University of Puerto Rico, and a researcher in algebraic topology, differential topology, graph theory, coding theory and combinatorial designs. He obtained a Licentiate degree in mathematics from University of Buenos Aires in 1967, arrived at Rutgers University in 1970 by means of a Guggenheim Fellowship and obtained a Ph.D. degree in mathematics in 1975 under the supervision of Professor Ted Petrie, with support of the National Science Foundation. He was a professor at the Federal University of Santa Catarina, Brazil, from 1977 to 1984, with grants from the National Council for Scientific and Technological Development, (CNPq).

In graph theory, a branch of mathematics, an indifference graph is an undirected graph constructed by assigning a real number to each vertex and connecting two vertices by an edge when their numbers are within one unit of each other. Indifference graphs are also the intersection graphs of sets of unit intervals, or of properly nested intervals. Based on these two types of interval representations, these graphs are also called unit interval graphs or proper interval graphs; they form a subclass of the interval graphs.

In graph theory, a universal vertex is a vertex of an undirected graph that is adjacent to all other vertices of the graph. It may also be called a dominating vertex, as it forms a one-element dominating set in the graph. A graph that contains a universal vertex may be called a cone, and its universal vertex may be called the apex of the cone. This terminology should be distinguished from the unrelated usage of these words for universal quantifiers in the logic of graphs, and for apex graphs.

In mathematics, the second neighborhood problem is an unsolved problem about oriented graphs posed by Paul Seymour. Intuitively, it suggests that in a social network described by such a graph, someone will have at least as many friends-of-friends as friends.

Hunter Snevily (1956–2013) was an American mathematician with expertise and contributions in Set theory, Graph theory, Discrete geometry, and Ramsey theory on the integers.

References

↑ Alwen, Joël; Serbinenko, Vladimir (2014), High Parallel Complexity Graphs and Memory-Hard Functions , retrieved 2024-01-15
1 2 3 4 Chung, Fan R. K. (1989). "Pebbling in hypercubes". SIAM Journal on Discrete Mathematics. 2 (4): 467–472. doi:10.1137/0402041. MR 1018531.
↑ See Chung (1989), question 3, page 472.
↑ 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.
↑ 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
↑ Vuong, Annalies; Wyckoff, M. Ian (October 18, 2004). "Conditions for Weighted Cover Pebbling of Graphs". arXiv: math/0410410 .
↑ Sjöstrand, Jonas (2005). "The cover pebbling theorem". Electronic Journal of Combinatorics. 12: Note 22. doi: 10.37236/1989 . MR 2180807.
↑ 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.